{ "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": [ "
Make this Notebook Trusted to load map: File -> Trust Notebook
" ], "text/plain": [ "" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Units of each product available at each depot\n", "depot_product_availabilities = {'D1':{'P1':3, 'P2': 5, 'P3': 3, 'P4':0},\n", " 'D2':{'P1':2, 'P2': 4, 'P3': 0, 'P4':4}}\n", "\n", "# The volume (cubic feet) required per unit of each product\n", "product_volumes = {'P1':12, 'P2':8, 'P3':9, 'P4':16}\n", "\n", "# Truck data (capacity is cubic feet available).\n", "trucks = {'T1':{'base':'D1', 'capacity':50, 'cost_per_mile':0.47}, \n", " 'T2':{'base':'D1', 'capacity':40, 'cost_per_mile':0.41}, \n", " 'T3':{'base':'D2', 'capacity':30, 'cost_per_mile':0.35},\n", " 'T4':{'base':'D2', 'capacity':90, 'cost_per_mile':0.55}}\n", "\n", "# Number of units of each product ordered by each customer.\n", "customer_orders = {'C1':{'P1':0, 'P2':1, 'P3':1, 'P4':0},\n", " 'C2':{'P1':0, 'P2':0, 'P3':0, 'P4':1},\n", " 'C3':{'P1':1, 'P2':0, 'P3':0, 'P4':0},\n", " 'C4':{'P1':0, 'P2':0, 'P3':0, 'P4':2},\n", " 'C5':{'P1':2, 'P2':0, 'P3':0, 'P4':0},\n", " 'C6':{'P1':0, 'P2':2, 'P3':1, 'P4':0},\n", " 'C7':{'P1':0, 'P2':1, 'P3':1, 'P4':0},\n", " 'C8':{'P1':1, 'P2':1, 'P3':0, 'P4':0}}\n", "\n", "# Labels for trucks, depots, customers, and products.\n", "truck_labels = sorted(trucks.keys())\n", "depot_labels = sorted(depot_product_availabilities.keys())\n", "customer_labels = sorted(customer_orders.keys())\n", "product_labels = sorted(product_volumes.keys())\n", "\n", "# These is the scenario node (i.e., locations of depots and customers) data, initially generated by the Veroviz sketch tool. \n", "# The leafletIconType was then manually set to 'home' for depot nodes and 'star' for customer nodes.\n", "nodesArray = [ \n", " {'id': 0, 'lat': 38.3064174, 'lon': -77.5188606, 'altMeters': 0.0, 'nodeName': 'D1', 'nodeType': 'Depot', 'popupText': 'D1', 'leafletIconPrefix': 'glyphicon', 'leafletIconType': 'home', 'leafletColor': 'blue', 'leafletIconText': '0', 'cesiumIconType': 'pin', 'cesiumColor': 'blue', 'cesiumIconText': '0', 'elevMeters': None},\n", " {'id': 1, 'lat': 38.1876887, 'lon': -77.619984, 'altMeters': 0.0, 'nodeName': 'D2', 'nodeType': 'Depot', 'popupText': 'D2', 'leafletIconPrefix': 'glyphicon', 'leafletIconType': 'home', 'leafletColor': 'blue', 'leafletIconText': '1', 'cesiumIconType': 'pin', 'cesiumColor': 'blue', 'cesiumIconText': '1', 'elevMeters': None},\n", " {'id': 2, 'lat': 38.2510008, 'lon': -77.5844244, 'altMeters': 0.0, 'nodeName': 'C1', 'nodeType': 'Customer', 'popupText': 'C1', 'leafletIconPrefix': 'glyphicon', 'leafletIconType': 'star', 'leafletColor': 'orange', 'leafletIconText': '2', 'cesiumIconType': 'pin', 'cesiumColor': 'orange', 'cesiumIconText': '2', 'elevMeters': None},\n", " {'id': 3, 'lat': 38.3494599, 'lon': -77.6573983, 'altMeters': 0.0, 'nodeName': 'C2', 'nodeType': 'Customer', 'popupText': 'C2', 'leafletIconPrefix': 'glyphicon', 'leafletIconType': 'star', 'leafletColor': 'orange', 'leafletIconText': '3', 'cesiumIconType': 'pin', 'cesiumColor': 'orange', 'cesiumIconText': '3', 'elevMeters': None},\n", " {'id': 4, 'lat': 38.3706877, 'lon': -77.5007117, 'altMeters': 0.0, 'nodeName': 'C3', 'nodeType': 'Customer', 'popupText': 'C3', 'leafletIconPrefix': 'glyphicon', 'leafletIconType': 'star', 'leafletColor': 'orange', 'leafletIconText': '4', 'cesiumIconType': 'pin', 'cesiumColor': 'orange', 'cesiumIconText': '4', 'elevMeters': None},\n", " {'id': 5, 'lat': 38.3199284, 'lon': -77.4104575, 'altMeters': 0.0, 'nodeName': 'C4', 'nodeType': 'Customer', 'popupText': 'C4', 'leafletIconPrefix': 'glyphicon', 'leafletIconType': 'star', 'leafletColor': 'orange', 'leafletIconText': '5', 'cesiumIconType': 'pin', 'cesiumColor': 'orange', 'cesiumIconText': '5', 'elevMeters': None},\n", " {'id': 6, 'lat': 38.1691186, 'lon': -77.8724912, 'altMeters': 0.0, 'nodeName': 'C5', 'nodeType': 'Customer', 'popupText': 'C5', 'leafletIconPrefix': 'glyphicon', 'leafletIconType': 'star', 'leafletColor': 'orange', 'leafletIconText': '6', 'cesiumIconType': 'pin', 'cesiumColor': 'orange', 'cesiumIconText': '6', 'elevMeters': None},\n", " {'id': 7, 'lat': 38.5123587, 'lon': -78.0333479, 'altMeters': 0.0, 'nodeName': 'C6', 'nodeType': 'Customer', 'popupText': 'C6', 'leafletIconPrefix': 'glyphicon', 'leafletIconType': 'star', 'leafletColor': 'orange', 'leafletIconText': '7', 'cesiumIconType': 'pin', 'cesiumColor': 'orange', 'cesiumIconText': '7', 'elevMeters': None},\n", " {'id': 8, 'lat': 38.4804832, 'lon': -77.4413181, 'altMeters': 0.0, 'nodeName': 'C7', 'nodeType': 'Customer', 'popupText': 'C7', 'leafletIconPrefix': 'glyphicon', 'leafletIconType': 'star', 'leafletColor': 'orange', 'leafletIconText': '8', 'cesiumIconType': 'pin', 'cesiumColor': 'orange', 'cesiumIconText': '8', 'elevMeters': None},\n", " {'id': 9, 'lat': 38.5125157, 'lon': -77.7038413, 'altMeters': 0.0, 'nodeName': 'C8', 'nodeType': 'Customer', 'popupText': 'C8', 'leafletIconPrefix': 'glyphicon', 'leafletIconType': 'star', 'leafletColor': 'orange', 'leafletIconText': '9', 'cesiumIconType': 'pin', 'cesiumColor': 'orange', 'cesiumIconText': '9', 'elevMeters': None},\n", "]\n", "nodesDF = pd.DataFrame(nodesArray)\n", "\n", "# Get the raw distance matrix from Veroviz. NOTE: This takes ~ 30 seconds - not instantaneous.\n", "[_, dist] = vrv.getTimeDist2D(nodes = nodesDF,\n", " matrixType = 'all2all',\n", " routeType = 'fastest',\n", " dataProvider = 'OSRM-online',\n", " outputDistUnits = 'miles')\n", "\n", "# This is the \"Big M\" in linear programming terminology - a large constant\n", "# used to impose prohibitively high costs on infeasible choices.\n", "BIG_M = 9999.9 \n", "\n", "# Set distances from each node to itself as BIG_M to ensure these paths are \n", "# never taken.\n", "dist = {(nodesArray[i]['nodeName'], nodesArray[j]['nodeName']):dist[i,j] if i != j else BIG_M\n", " for i in range(len(nodesArray)) for j in range(len(nodesArray))}\n", "\n", "\n", "# View the nodes on a map - blue/home markers are depots and orange/star markers are customers.\n", "vrv.createLeaflet(nodes=nodesDF, mapBackground='Arcgis Topo')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 2: Create the Model\n", "\n", "Since we want this to be generic and able to be reused with different data, we will construct a function to create the IP model using PuLP. " ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "# The inputs for this function are as follows:\n", "# trucks: A list of distinct truck labels (e.g., ['T1', 'T2', ...])\n", "# depots: A list of distinct depot labels (e.g., ['D1', 'D2', ...])\n", "# customers: A list of distinct customer labels (e.g., ['C1', 'C2', ...])\n", "# products: A list of distinct product labels (e.g., ['C1', 'C2', ...])\n", "# prod_availability: A dict of form {:{:, ...}, ...}\n", "# prod_volume: A dict of form {:}\n", "# truck_cap: A dict of form {:}\n", "# demand: A dict of form {}:{:, ...}, ...}\n", "# cost_per_mile: A dict of form {:}\n", "# dist_matrix: dict of form {(, ):, ...}. Locations are depots + customers\n", "# truck_base: A dict of form {:}\n", "# big_m: An arbitrarily large constant.\n", "def build_model(trucks, depots, customers, products, prod_availability,\n", " prod_volume, truck_cap, demand, cost_per_mile,\n", " dist_matrix, truck_base, big_m):\n", " H = trucks\n", " I = depots\n", " J = customers\n", " K = products\n", " L = I + J # Set of all distinct locations\n", " a = prod_availability\n", " e = prod_volume\n", " E = truck_cap\n", " r = demand\n", " d = dist_matrix\n", " c = cost_per_mile\n", " b = {h:{i:1 if truck_base[h] == i else 0 for i in I} for h in H}\n", " \n", " # u[h][j][k] = Units of product k delivered to customer j on truck h\n", " u = LpVariable.dicts(\"u\", (H, J, K), 0, None, LpInteger) \n", " \n", " # x[h][i][j] == 1 if truck h travels directly from location i to j, 0 otherwise\n", " x = LpVariable.dicts(\"x\", (H, L, L), 0, 1, LpInteger)\n", " \n", " prob = LpProblem(\"MultiDepot_VRP\", LpMinimize)\n", " prob += (lpSum([c[h] * d[i,j] * x[h][i][j] for h in H for i in L for j in L]), \n", " 'Total_Cost') # Objective Function\n", " for h in H:\n", " prob += (lpSum([e[k] * u[h][j][k] for j in J for k in K]) <= E[h]) # Ensure no truck capacity exceeded\n", " for i in L:\n", " prob += (lpSum([x[h][j][i] for j in L]) == lpSum([x[h][i][j] for j in L])) # For each loc, truck in -> truck out\n", " for i in I:\n", " prob += (lpSum([x[h][i][j] for j in L]) <= b[h][i]) # Ensure no truck leaves a non-base depot\n", " for W in allcombinations(J, len(J)): \n", " prob += (lpSum([x[h][i][j] for i in W for j in W]) <= len(W) - 1) # Ensure no subset of customers contains a circuit.\n", " \n", " for k in K:\n", " for i in I:\n", " prob += (lpSum([b[h][i] * u[h][j][k] for h in H for j in J]) <= a[i][k]) # No depot ships more of a product than it has\n", " for j in J:\n", " prob += (lpSum(u[h][j][k] for h in H) == r[j][k]) # Each customer gets the products they ordered\n", " for h in H:\n", " prob += (u[h][j][k] <= big_m * lpSum(x[h][i][j] for i in L)) # No truck carries products for a customer unless it visits the customer.\n", " return prob\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 3: Solve the Model\n", "\n", "Below we first construct the IP model and solve it. If you are using the CBC solver that comes with PuLP, it may take 15-30 seconds to find a solution. If you have access to the CPLEX solver, solutions can be obtained in a couple of seconds - just comment out the model.solve() line and uncomment the two below it." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Total Cost of Transportation = 105.69849876346827\n", "Computational Time = 24.2 seconds\n" ] } ], "source": [ "# Construct the model\n", "model = build_model(truck_labels, \n", " depot_labels, \n", " customer_labels, \n", " product_labels,\n", " depot_product_availabilities, \n", " product_volumes, \n", " {t:trucks[t]['capacity'] for t in trucks.keys()},\n", " customer_orders, \n", " {t:trucks[t]['cost_per_mile'] for t in trucks.keys()}, \n", " dist, \n", " {t:trucks[t]['base'] for t in trucks.keys()},\n", " BIG_M)\n", "\n", "# Set the initial time\n", "start_time = time.time()\n", "\n", "# Solve the model using the CBC solver that comes with PuLP\n", "model.solve()\n", "\n", "# If you have the faster CPLEX solver and want to use it, uncomment the two\n", "# lines below and comment out the one above.\n", "# solver = getSolver('CPLEX_CMD') \n", "# model.solve(solver) \n", "\n", "# Compute the elapsed time\n", "elapsed_time = time.time() - start_time\n", "\n", "\n", "# Output the total cost of transportation and computational time\n", "print(\"Total Cost of Transportation = \", value(model.objective))\n", "print(\"Computational Time = \", round(elapsed_time, 1), 'seconds')\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 4: Extract and View the Truck Itineraries\n", "\n", "In this step we need to extract the truck itineraries from the decision variables. For each truck, we want to know its stops and which products to deliver at each stop. To get this information, we need to sift through the non-zero decision variables from the solved model. " ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
TruckStop NumberCustomerDelivery (Product, Quantity)
0T11C6(P2, 2.0), (P3, 1.0)
1T12C8(P1, 1.0), (P2, 1.0)
2T21C1(P3, 1.0)
3T22C3(P1, 1.0)
4T23C7(P2, 1.0), (P3, 1.0)
5T31C5(P1, 2.0)
6T41C4(P4, 2.0)
7T42C2(P4, 1.0)
8T43C1(P2, 1.0)
\n", "
" ], "text/plain": [ " Truck Stop Number Customer Delivery (Product, Quantity)\n", "0 T1 1 C6 (P2, 2.0), (P3, 1.0)\n", "1 T1 2 C8 (P1, 1.0), (P2, 1.0)\n", "2 T2 1 C1 (P3, 1.0)\n", "3 T2 2 C3 (P1, 1.0)\n", "4 T2 3 C7 (P2, 1.0), (P3, 1.0)\n", "5 T3 1 C5 (P1, 2.0)\n", "6 T4 1 C4 (P4, 2.0)\n", "7 T4 2 C2 (P4, 1.0)\n", "8 T4 3 C1 (P2, 1.0)" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Populate truck path and customer order dicts by extracting variable values\n", "# from the solved model.\n", "path, order = {}, {}\n", "for v in model.variables():\n", " var, truck, i, j, val = v.name.split('_') + [v.varValue]\n", " if var == 'x' and val == 1:\n", " if not(truck in path):\n", " path[truck] = {}\n", " path[truck][i] = j\n", " if i.startswith('D'):\n", " path[truck]['depot'] = i\n", " elif var == 'u' and val > 0:\n", " if not(truck in order):\n", " order[truck] = {}\n", " if not(i in order[truck]):\n", " order[truck][i] = []\n", " order[truck][i].append((j, val))\n", " \n", "\n", "# Utility function - given a truck label, build its route as a list (excluding the depot).\n", "def build_truck_route(truck):\n", " h = path[truck]\n", " depot = h['depot']\n", " curr_loc = depot\n", " route = []\n", " while h[curr_loc] != depot:\n", " route.append(h[curr_loc])\n", " curr_loc = h[curr_loc]\n", " return route\n", "\n", "# Build a dict for all truck routes including the depots. We will use this later.\n", "truck_routes = {}\n", " \n", "# Build Itinerary Table\n", "itinerary_list = []\n", "for t in truck_labels:\n", " if t in path :\n", " depot = path[t]['depot']\n", " route = build_truck_route(t)\n", " truck_routes[t] = [depot] + route + [depot]\n", " stop_num = 1\n", " for stop in route:\n", " delivery = str(order[t][stop]).replace('[', '').replace(']', '').replace(\"'\", '')\n", " itinerary_list.append({'Truck':t, 'Stop Number':str(stop_num), \n", " 'Customer':stop, 'Delivery (Product, Quantity)':delivery})\n", " stop_num += 1 \n", "\n", "# Create a data frame to hold the truck iteneraries and show it\n", "itinerary_df = pd.DataFrame(itinerary_list)\n", "itinerary_df" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Step 5: Build and Display the Truck Route Visualizations\n", "\n", "Below we use VeRoViz to build the route visualizations." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Message: The destination point (lat: 38.3706877, lon: -77.5007117) is 12.8 meters away from the road. You might find a gap between destination point and the route.\n", "Message: The origin point (lat: 38.3706877, lon: -77.5007117) is 12.8 meters away from the road. You might find a gap between the origin point and the route.\n" ] }, { "data": { "text/html": [ "
Make this Notebook Trusted to load map: File -> Trust Notebook
" ], "text/plain": [ "" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Construct a mapping from node labels (depots + customers) to node objects\n", "node_dict = {x['nodeName']:x for x in nodesArray}\n", "\n", "# Specify the truck colors\n", "truck_colors = {'T1':'blue', 'T2':'red', 'T3':'black', 'T4':'green'}\n", "\n", "# Construct an empty data frame to hold the routes\n", "assignmentsDF = vrv.initDataframe('assignments')\n", "\n", "# For each truck, add each one of its stops in order to the assignmentsDF\n", "for t in truck_routes:\n", " for i in range(1, len(truck_routes[t])):\n", " start_node = truck_routes[t][i - 1]\n", " end_node = truck_routes[t][i]\n", " shapepointsDF = vrv.getShapepoints2D(\n", " objectID = t, \n", " modelFile = 'veroviz/models/ub_truck.gltf',\n", " startLoc = [node_dict[start_node]['lat'], node_dict[start_node]['lon']],\n", " endLoc = [node_dict[end_node]['lat'], node_dict[end_node]['lon']],\n", " routeType = 'fastest',\n", " leafletColor = truck_colors[t], \n", " dataProvider = 'OSRM-online') \n", " assignmentsDF = pd.concat([assignmentsDF, shapepointsDF], \n", " ignore_index=True, sort=False)\n", "\n", "# Construct the leaflet map and view. NOTE: This also takes a little time - not instantaneous.\n", "vrv.createLeaflet(nodes=nodesDF, arcs=assignmentsDF, mapBackground='Arcgis Topo')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.3" } }, "nbformat": 4, "nbformat_minor": 4 }