{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Multi-Depot Last Mile Delivery Routing\n", "\n", "In this notebook we examine the problem of last mile delivery routing with multiple depots and a heterogeneous vehicle fleet. In this problem, each customer has ordered a specific quantity of each product, and each depot has a certain quantity of each product type available. There is a single, heterogeneous fleet of trucks available for shipping, and each truck is based at exactly one depot (meaning its route always begins and ends at its base depot). Each truck may have a different volume capacity and cost per mile. We also note that since not all products may be available at the same depot, customer orders may need to be split and fulfilled by multiple depots. The objective is to simultaneously determine 1) the products to be shipped from each depot to each customer, 2) how to assign trucks to customers, and 3) how to route each truck to its customers, all in a way that achieves lowest total delivery cost possible.\n", "\n", "This notebook will demonstrate how to model and solve the problem using [integer programming](https://medium.com/hackernoon/mixed-integer-programming-a-straight-forward-tutorial-41cc50fb9c23) (IP). We will use the [PuLP](https://coin-or.github.io/pulp/) library to build and solve the IP model, and [VeRoViz](https://veroviz.org) to visualize the truck routes." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# Import the libraries needed.\n", "from pulp import *\n", "import pandas as pd\n", "import veroviz as vrv\n", "import time" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 1: Prepare the Scenario Data\n", "\n", "In this scenario, we will assume a furniture company has two depots in the Fredericksburg, VA area with eight customer orders to be delivered. The scenario location and transportation data was prepared with the [VeRoViz Sketch Tool](https://veroviz.org/sketch.html). To save time, we have pre-computed the distance matrix and saved it to a pickle file. However, the code to build this matrix using VeRoViz is shown commented out. " ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", " | Truck | \n", "Stop Number | \n", "Customer | \n", "Delivery (Product, Quantity) | \n", "
---|---|---|---|---|
0 | \n", "T1 | \n", "1 | \n", "C6 | \n", "(P2, 2.0), (P3, 1.0) | \n", "
1 | \n", "T1 | \n", "2 | \n", "C8 | \n", "(P1, 1.0), (P2, 1.0) | \n", "
2 | \n", "T2 | \n", "1 | \n", "C1 | \n", "(P3, 1.0) | \n", "
3 | \n", "T2 | \n", "2 | \n", "C3 | \n", "(P1, 1.0) | \n", "
4 | \n", "T2 | \n", "3 | \n", "C7 | \n", "(P2, 1.0), (P3, 1.0) | \n", "
5 | \n", "T3 | \n", "1 | \n", "C5 | \n", "(P1, 2.0) | \n", "
6 | \n", "T4 | \n", "1 | \n", "C4 | \n", "(P4, 2.0) | \n", "
7 | \n", "T4 | \n", "2 | \n", "C2 | \n", "(P4, 1.0) | \n", "
8 | \n", "T4 | \n", "3 | \n", "C1 | \n", "(P2, 1.0) | \n", "