Demonstrates a solution for the simple multi-vehicle routing problem (VRP) using a combination of Google libraries and services. Sample depot and shipment locations randomly chosen in the San Antonio, TX metro area. Distances and times are based on Google's road network.
You will need a Google Maps Platform API Key.
pip install jupyterlab
pip install -r requirements.txt
jupyter nbextension enable --py --sys-prefix gmaps
jupyter notebook
| #!/bin/bash | |
| jupyter nbextension enable --py --sys-prefix gmaps |
| gmaps==0.9.0 | |
| googlemaps==3.0.2 | |
| ortools==7.3.7083 | |
| pandas==0.25.0 |
| { | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "## Simple VRP with Google Developer Resources\n", | |
| "#### OR-Tools + Google Maps Services\n", | |
| "* https://developers.google.com/optimization/routing/vrp\n", | |
| "* https://github.com/googlemaps/google-maps-services-python\n", | |
| "* https://jupyter-gmaps.readthedocs.io/en/latest/index.html" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Configure Google Maps API key\n", | |
| "\n", | |
| "To run the notebook, you must bring our own Maps Platform API key. See https://developers.google.com/maps/gmp-get-started to get started." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 1, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "import os\n", | |
| "import gmaps\n", | |
| "\n", | |
| "API_KEY = 'YOUR_API_KEY'\n", | |
| "gmaps.configure(api_key=API_KEY)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Create Depot\n", | |
| "The first step is to create the depot and shipment locations. The depot is the home-base for delivery vehicles and the shipment locations are delivery destinations. These locations are chosen randomly on the map with fairly uniform spread across the city." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 2, | |
| "metadata": { | |
| "scrolled": true | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "depot = {\n", | |
| " 'location': (29.399013114383962, -98.52633476257324)\n", | |
| "}\n", | |
| "\n", | |
| "depot_layer = gmaps.symbol_layer(\n", | |
| " [depot['location']], hover_text='Depot', info_box_content='Depot', \n", | |
| " fill_color='white', stroke_color='red', scale=8\n", | |
| ")" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Set Number of Vehicles\n", | |
| "The number of vehicles is set to 3. After running through the entire notebook, come back and vary this value to observe its impact on the generated routes." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 3, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "num_vehicles = 3" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Create Shipments" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 4, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "shipments = [\n", | |
| " { \n", | |
| " 'name': 'Santa\\'s Place',\n", | |
| " 'location': (29.417361, -98.437544)\n", | |
| " },\n", | |
| " {\n", | |
| " 'name': 'Los Barrios',\n", | |
| " 'location': (29.486833, -98.508355)\n", | |
| " },\n", | |
| " {\n", | |
| " 'name': 'Jacala',\n", | |
| " 'location': (29.468601, -98.524849),\n", | |
| " },\n", | |
| " {\n", | |
| " 'name': 'Nogalitos',\n", | |
| " 'location': (29.394394, -98.530070)\n", | |
| " },\n", | |
| " {\n", | |
| " 'name': 'Alamo Molino',\n", | |
| " 'location': (29.351701, -98.514740)\n", | |
| " },\n", | |
| " {\n", | |
| " 'name': 'Jesse and Sons',\n", | |
| " 'location': (29.435115, -98.593962)\n", | |
| " },\n", | |
| " {\n", | |
| " 'name': 'Walmart',\n", | |
| " 'location': (29.417867, -98.680534)\n", | |
| " },\n", | |
| " {\n", | |
| " 'name': 'City Base Entertainment',\n", | |
| " 'location': (29.355400, -98.445857)\n", | |
| " },\n", | |
| " { \n", | |
| " 'name': 'Combat Medic Training',\n", | |
| " 'location': (29.459497, -98.434057)\n", | |
| " }\n", | |
| "]\n", | |
| "\n", | |
| "shipment_locations = [shipment['location'] for shipment in shipments]\n", | |
| "shipment_labels = [shipment['name'] for shipment in shipments]\n", | |
| "\n", | |
| "shipments_layer = gmaps.symbol_layer(\n", | |
| " shipment_locations, hover_text=shipment_labels, \n", | |
| " fill_color='white', stroke_color='black', scale=4\n", | |
| ")" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Map Depot and Shipments" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "fig = gmaps.figure()\n", | |
| "fig.add_layer(depot_layer)\n", | |
| "fig.add_layer(shipments_layer)\n", | |
| "\n", | |
| "fig" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Build Distance Matrix\n", | |
| "The Distance Matrix API builds the cost matrix. Distance Matrix API returns both the distance and duration for each origin-destination pair. For the first solution example, we generate the cost matrix using distance. The cost matrix consists of real-world road distances (based on the Google Maps road network) between each depot and shipment pair and serves as a key input into the VRP solver. API calls are made with the Python client for Google Maps Services (https://github.com/googlemaps/google-maps-services-python)." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 6, | |
| "metadata": { | |
| "scrolled": false | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "text/html": [ | |
| "<div>\n", | |
| "<style scoped>\n", | |
| " .dataframe tbody tr th:only-of-type {\n", | |
| " vertical-align: middle;\n", | |
| " }\n", | |
| "\n", | |
| " .dataframe tbody tr th {\n", | |
| " vertical-align: top;\n", | |
| " }\n", | |
| "\n", | |
| " .dataframe thead th {\n", | |
| " text-align: right;\n", | |
| " }\n", | |
| "</style>\n", | |
| "<table border=\"1\" class=\"dataframe\">\n", | |
| " <thead>\n", | |
| " <tr style=\"text-align: right;\">\n", | |
| " <th></th>\n", | |
| " <th>0</th>\n", | |
| " <th>1</th>\n", | |
| " <th>2</th>\n", | |
| " <th>3</th>\n", | |
| " <th>4</th>\n", | |
| " <th>5</th>\n", | |
| " <th>6</th>\n", | |
| " <th>7</th>\n", | |
| " <th>8</th>\n", | |
| " <th>9</th>\n", | |
| " </tr>\n", | |
| " </thead>\n", | |
| " <tbody>\n", | |
| " <tr>\n", | |
| " <th>0</th>\n", | |
| " <td>0</td>\n", | |
| " <td>12392</td>\n", | |
| " <td>13229</td>\n", | |
| " <td>11197</td>\n", | |
| " <td>992</td>\n", | |
| " <td>8114</td>\n", | |
| " <td>12130</td>\n", | |
| " <td>19940</td>\n", | |
| " <td>11664</td>\n", | |
| " <td>14336</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>1</th>\n", | |
| " <td>12144</td>\n", | |
| " <td>0</td>\n", | |
| " <td>16865</td>\n", | |
| " <td>14833</td>\n", | |
| " <td>12877</td>\n", | |
| " <td>14900</td>\n", | |
| " <td>21045</td>\n", | |
| " <td>28855</td>\n", | |
| " <td>12141</td>\n", | |
| " <td>7606</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>2</th>\n", | |
| " <td>13298</td>\n", | |
| " <td>15549</td>\n", | |
| " <td>0</td>\n", | |
| " <td>3964</td>\n", | |
| " <td>14095</td>\n", | |
| " <td>17630</td>\n", | |
| " <td>23603</td>\n", | |
| " <td>24133</td>\n", | |
| " <td>19908</td>\n", | |
| " <td>12383</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>3</th>\n", | |
| " <td>11002</td>\n", | |
| " <td>14677</td>\n", | |
| " <td>3903</td>\n", | |
| " <td>0</td>\n", | |
| " <td>11799</td>\n", | |
| " <td>15333</td>\n", | |
| " <td>21307</td>\n", | |
| " <td>22482</td>\n", | |
| " <td>18883</td>\n", | |
| " <td>14619</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>4</th>\n", | |
| " <td>988</td>\n", | |
| " <td>12681</td>\n", | |
| " <td>13810</td>\n", | |
| " <td>11779</td>\n", | |
| " <td>0</td>\n", | |
| " <td>6822</td>\n", | |
| " <td>12876</td>\n", | |
| " <td>20685</td>\n", | |
| " <td>11953</td>\n", | |
| " <td>14917</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>5</th>\n", | |
| " <td>8747</td>\n", | |
| " <td>15349</td>\n", | |
| " <td>17925</td>\n", | |
| " <td>15893</td>\n", | |
| " <td>6868</td>\n", | |
| " <td>0</td>\n", | |
| " <td>17533</td>\n", | |
| " <td>25342</td>\n", | |
| " <td>7267</td>\n", | |
| " <td>19032</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>6</th>\n", | |
| " <td>10191</td>\n", | |
| " <td>21314</td>\n", | |
| " <td>22493</td>\n", | |
| " <td>20430</td>\n", | |
| " <td>10373</td>\n", | |
| " <td>16895</td>\n", | |
| " <td>0</td>\n", | |
| " <td>10334</td>\n", | |
| " <td>20586</td>\n", | |
| " <td>24847</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>7</th>\n", | |
| " <td>17993</td>\n", | |
| " <td>29116</td>\n", | |
| " <td>24048</td>\n", | |
| " <td>21985</td>\n", | |
| " <td>18175</td>\n", | |
| " <td>26145</td>\n", | |
| " <td>10097</td>\n", | |
| " <td>0</td>\n", | |
| " <td>28388</td>\n", | |
| " <td>32649</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>8</th>\n", | |
| " <td>11998</td>\n", | |
| " <td>12265</td>\n", | |
| " <td>20956</td>\n", | |
| " <td>19324</td>\n", | |
| " <td>12730</td>\n", | |
| " <td>7790</td>\n", | |
| " <td>20899</td>\n", | |
| " <td>28708</td>\n", | |
| " <td>0</td>\n", | |
| " <td>17215</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>9</th>\n", | |
| " <td>14599</td>\n", | |
| " <td>8016</td>\n", | |
| " <td>16997</td>\n", | |
| " <td>14965</td>\n", | |
| " <td>15396</td>\n", | |
| " <td>18930</td>\n", | |
| " <td>24904</td>\n", | |
| " <td>32713</td>\n", | |
| " <td>17548</td>\n", | |
| " <td>0</td>\n", | |
| " </tr>\n", | |
| " </tbody>\n", | |
| "</table>\n", | |
| "</div>" | |
| ], | |
| "text/plain": [ | |
| " 0 1 2 3 4 5 6 7 8 9\n", | |
| "0 0 12392 13229 11197 992 8114 12130 19940 11664 14336\n", | |
| "1 12144 0 16865 14833 12877 14900 21045 28855 12141 7606\n", | |
| "2 13298 15549 0 3964 14095 17630 23603 24133 19908 12383\n", | |
| "3 11002 14677 3903 0 11799 15333 21307 22482 18883 14619\n", | |
| "4 988 12681 13810 11779 0 6822 12876 20685 11953 14917\n", | |
| "5 8747 15349 17925 15893 6868 0 17533 25342 7267 19032\n", | |
| "6 10191 21314 22493 20430 10373 16895 0 10334 20586 24847\n", | |
| "7 17993 29116 24048 21985 18175 26145 10097 0 28388 32649\n", | |
| "8 11998 12265 20956 19324 12730 7790 20899 28708 0 17215\n", | |
| "9 14599 8016 16997 14965 15396 18930 24904 32713 17548 0" | |
| ] | |
| }, | |
| "execution_count": 6, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "import googlemaps\n", | |
| "import pandas as pd\n", | |
| "\n", | |
| "\n", | |
| "def build_distance_matrix(depot, shipments, measure='distance'):\n", | |
| "\n", | |
| " gmaps_services = googlemaps.Client(key=API_KEY)\n", | |
| " origins = destinations = [item['location'] for item in [depot] + shipments]\n", | |
| " dm_response = gmaps_services.distance_matrix(origins=origins, destinations=destinations)\n", | |
| " dm_rows = [row['elements'] for row in dm_response['rows']]\n", | |
| " distance_matrix = [[item[measure]['value'] for item in dm_row] for dm_row in dm_rows]\n", | |
| " return distance_matrix\n", | |
| "\n", | |
| "try:\n", | |
| " objective = 'distance' # distance or duration\n", | |
| " # Distance Matrix API takes a max 100 elements = (origins x destinations), limit to 10 x 10\n", | |
| " distance_matrix = build_distance_matrix(depot, shipments[0:9], objective)\n", | |
| " df = pd.DataFrame(distance_matrix)\n", | |
| "\n", | |
| "except:\n", | |
| " print('Something went wrong building distance matrix.')\n", | |
| "\n", | |
| "df" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Solution Logic\n", | |
| "The VRP solver is an OR-Tools component (https://developers.google.com/optimization/routing/vrp). Additional documentation on the algorithm and computation options are available in OR-Tools." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 7, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "\"\"\"Vehicles Routing Problem (VRP).\"\"\"\n", | |
| "from ortools.constraint_solver import routing_enums_pb2\n", | |
| "from ortools.constraint_solver import pywrapcp\n", | |
| "\n", | |
| "\n", | |
| "def create_data_model(distance_matrix, num_vehicles):\n", | |
| " \"\"\"Stores the data for the problem.\"\"\"\n", | |
| " data = {}\n", | |
| " data['distance_matrix'] = distance_matrix\n", | |
| " data['num_vehicles'] = num_vehicles\n", | |
| " data['depot'] = 0\n", | |
| " return data\n", | |
| "\n", | |
| "def extract_routes(num_vehicles, manager, routing, solution):\n", | |
| " routes = {}\n", | |
| " for vehicle_id in range(num_vehicles):\n", | |
| " routes[vehicle_id] = []\n", | |
| " index = routing.Start(vehicle_id)\n", | |
| " while not routing.IsEnd(index):\n", | |
| " routes[vehicle_id].append(manager.IndexToNode(index))\n", | |
| " previous_index = index\n", | |
| " index = solution.Value(routing.NextVar(index))\n", | |
| " routes[vehicle_id].append(manager.IndexToNode(index))\n", | |
| " return routes\n", | |
| "\n", | |
| "def print_solution(num_vehicles, manager, routing, solution):\n", | |
| " \"\"\"Prints solution on console.\"\"\"\n", | |
| " max_route_distance = 0\n", | |
| " for vehicle_id in range(num_vehicles):\n", | |
| " index = routing.Start(vehicle_id)\n", | |
| " plan_output = 'Route for vehicle {}:\\n'.format(vehicle_id)\n", | |
| " route_distance = 0\n", | |
| " while not routing.IsEnd(index):\n", | |
| " plan_output += ' {} -> '.format(manager.IndexToNode(index))\n", | |
| " previous_index = index\n", | |
| " index = solution.Value(routing.NextVar(index))\n", | |
| " route_distance += routing.GetArcCostForVehicle(\n", | |
| " previous_index, index, vehicle_id)\n", | |
| " plan_output += '{}\\n'.format(manager.IndexToNode(index))\n", | |
| " plan_output += 'Cost of the route: {}\\n'.format(route_distance)\n", | |
| " print(plan_output)\n", | |
| " max_route_distance = max(route_distance, max_route_distance)\n", | |
| " print('Maximum route cost: {}'.format(max_route_distance))\n", | |
| "\n", | |
| "def generate_solution(data, manager, routing): \n", | |
| " \"\"\"Solve the CVRP problem.\"\"\"\n", | |
| " \n", | |
| " # Create and register a transit callback.\n", | |
| " def distance_callback(from_index, to_index):\n", | |
| " \"\"\"Returns the distance between the two nodes.\"\"\"\n", | |
| " # Convert from routing variable Index to distance matrix NodeIndex.\n", | |
| " from_node = manager.IndexToNode(from_index)\n", | |
| " to_node = manager.IndexToNode(to_index)\n", | |
| " return data['distance_matrix'][from_node][to_node]\n", | |
| "\n", | |
| " transit_callback_index = routing.RegisterTransitCallback(distance_callback)\n", | |
| "\n", | |
| " # Define cost of each arc.\n", | |
| " routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)\n", | |
| "\n", | |
| " # Add Distance constraint.\n", | |
| " dimension_name = 'Distance'\n", | |
| " flattened_distance_matrix = [i for j in data['distance_matrix'] for i in j]\n", | |
| " max_travel_distance = 2 * max(flattened_distance_matrix)\n", | |
| "\n", | |
| " routing.AddDimension(\n", | |
| " transit_callback_index,\n", | |
| " 0, # no slack\n", | |
| " max_travel_distance, # vehicle maximum travel distance\n", | |
| " True, # start cumul to zero\n", | |
| " dimension_name)\n", | |
| " distance_dimension = routing.GetDimensionOrDie(dimension_name)\n", | |
| " distance_dimension.SetGlobalSpanCostCoefficient(100)\n", | |
| "\n", | |
| " # Setting first solution heuristic.\n", | |
| " search_parameters = pywrapcp.DefaultRoutingSearchParameters()\n", | |
| " search_parameters.first_solution_strategy = (\n", | |
| " routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)\n", | |
| "\n", | |
| " # Solve the problem.\n", | |
| " solution = routing.SolveWithParameters(search_parameters)\n", | |
| " return solution\n", | |
| "\n", | |
| "def solve_vrp_for(distance_matrix, num_vehicles):\n", | |
| " # Instantiate the data problem.\n", | |
| " data = create_data_model(distance_matrix, num_vehicles)\n", | |
| "\n", | |
| " # Create the routing index manager.\n", | |
| " manager = pywrapcp.RoutingIndexManager(\n", | |
| " len(data['distance_matrix']), data['num_vehicles'], data['depot'])\n", | |
| "\n", | |
| " # Create Routing Model.\n", | |
| " routing = pywrapcp.RoutingModel(manager)\n", | |
| "\n", | |
| " # Solve the problem\n", | |
| " solution = generate_solution(data, manager, routing)\n", | |
| " \n", | |
| " if solution:\n", | |
| " # Print solution on console.\n", | |
| " print_solution(num_vehicles, manager, routing, solution)\n", | |
| " routes = extract_routes(num_vehicles, manager, routing, solution)\n", | |
| " return routes\n", | |
| " else:\n", | |
| " print('No solution found.')\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Solve for Distance\n", | |
| "The generated route for each vehicle are logged to the console, including a node-to-node chain diagram." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 8, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Route for vehicle 0:\n", | |
| " 0 -> 3 -> 2 -> 9 -> 0\n", | |
| "Cost of the route: 42082\n", | |
| "\n", | |
| "Route for vehicle 1:\n", | |
| " 0 -> 7 -> 6 -> 0\n", | |
| "Cost of the route: 40228\n", | |
| "\n", | |
| "Route for vehicle 2:\n", | |
| " 0 -> 4 -> 5 -> 8 -> 1 -> 0\n", | |
| "Cost of the route: 39490\n", | |
| "\n", | |
| "Maximum route cost: 42082\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "try:\n", | |
| " routes = solve_vrp_for(distance_matrix, num_vehicles)\n", | |
| "except:\n", | |
| " print('Something went wrong solving VRP.')" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Map the Solution\n", | |
| "The Directions API is called to generate the road pathways to overlay on the map. Note: we call Directions API merely as a convenience to generate the polylines for map display reasons only. It’s performing no waypoint optimization since the VRP solver has already performed all needed optimization." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "def map_solution(depot, shipments, routes):\n", | |
| " colors = ['blue','red','green','#800080','#000080','#008080']\n", | |
| " for vehicle_id in routes:\n", | |
| " waypoints = []\n", | |
| " \n", | |
| " # skip depot (occupies first and last index)\n", | |
| " for shipment_index in routes[vehicle_id][1:-1]: \n", | |
| " waypoints.append(shipments[shipment_index-1]['location'])\n", | |
| " \n", | |
| " if len(waypoints) == 0:\n", | |
| " print('Empty route:', vehicle_id)\n", | |
| " else:\n", | |
| " route_layer = gmaps.directions_layer(\n", | |
| " depot['location'], waypoints[-1], waypoints=waypoints[0:-1], show_markers=True,\n", | |
| " stroke_color=colors[vehicle_id], stroke_weight=5, stroke_opacity=0.5)\n", | |
| " fig.add_layer(route_layer)\n", | |
| " \n", | |
| " # complete the route from last shipment to depot\n", | |
| " return_layer = gmaps.directions_layer(\n", | |
| " waypoints[-1], depot['location'], show_markers=False,\n", | |
| " stroke_color=colors[vehicle_id], stroke_weight=5, stroke_opacity=0.5)\n", | |
| " fig.add_layer(return_layer)\n", | |
| "\n", | |
| "if routes:\n", | |
| " map_solution(depot, shipments, routes)\n", | |
| "else:\n", | |
| " print('No solution found.') \n", | |
| "\n", | |
| "fig" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Solve for Duration\n", | |
| "For a second VRP solver run, we generate the cost matrix based on duration. The goal here is to minimize delivery time. By comparing these generated routes with the above routes derived from a distance-based cost matrix, it’s evident that the routes differ significantly. This makes sense considering the goals to minimize either distance or duration can be in competition." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 10, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Route for vehicle 0:\n", | |
| " 0 -> 8 -> 2 -> 3 -> 4 -> 0\n", | |
| "Cost of the route: 3014\n", | |
| "\n", | |
| "Route for vehicle 1:\n", | |
| " 0 -> 1 -> 9 -> 0\n", | |
| "Cost of the route: 2736\n", | |
| "\n", | |
| "Route for vehicle 2:\n", | |
| " 0 -> 6 -> 7 -> 5 -> 0\n", | |
| "Cost of the route: 3311\n", | |
| "\n", | |
| "Maximum route cost: 3311\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "text/html": [ | |
| "<div>\n", | |
| "<style scoped>\n", | |
| " .dataframe tbody tr th:only-of-type {\n", | |
| " vertical-align: middle;\n", | |
| " }\n", | |
| "\n", | |
| " .dataframe tbody tr th {\n", | |
| " vertical-align: top;\n", | |
| " }\n", | |
| "\n", | |
| " .dataframe thead th {\n", | |
| " text-align: right;\n", | |
| " }\n", | |
| "</style>\n", | |
| "<table border=\"1\" class=\"dataframe\">\n", | |
| " <thead>\n", | |
| " <tr style=\"text-align: right;\">\n", | |
| " <th></th>\n", | |
| " <th>0</th>\n", | |
| " <th>1</th>\n", | |
| " <th>2</th>\n", | |
| " <th>3</th>\n", | |
| " <th>4</th>\n", | |
| " <th>5</th>\n", | |
| " <th>6</th>\n", | |
| " <th>7</th>\n", | |
| " <th>8</th>\n", | |
| " <th>9</th>\n", | |
| " </tr>\n", | |
| " </thead>\n", | |
| " <tbody>\n", | |
| " <tr>\n", | |
| " <th>0</th>\n", | |
| " <td>0</td>\n", | |
| " <td>722</td>\n", | |
| " <td>823</td>\n", | |
| " <td>736</td>\n", | |
| " <td>151</td>\n", | |
| " <td>670</td>\n", | |
| " <td>600</td>\n", | |
| " <td>1023</td>\n", | |
| " <td>622</td>\n", | |
| " <td>1147</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>1</th>\n", | |
| " <td>709</td>\n", | |
| " <td>0</td>\n", | |
| " <td>1089</td>\n", | |
| " <td>1003</td>\n", | |
| " <td>813</td>\n", | |
| " <td>930</td>\n", | |
| " <td>949</td>\n", | |
| " <td>1372</td>\n", | |
| " <td>639</td>\n", | |
| " <td>937</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>2</th>\n", | |
| " <td>807</td>\n", | |
| " <td>1026</td>\n", | |
| " <td>0</td>\n", | |
| " <td>413</td>\n", | |
| " <td>877</td>\n", | |
| " <td>1081</td>\n", | |
| " <td>1113</td>\n", | |
| " <td>1256</td>\n", | |
| " <td>989</td>\n", | |
| " <td>1189</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>3</th>\n", | |
| " <td>702</td>\n", | |
| " <td>956</td>\n", | |
| " <td>435</td>\n", | |
| " <td>0</td>\n", | |
| " <td>772</td>\n", | |
| " <td>976</td>\n", | |
| " <td>1008</td>\n", | |
| " <td>1203</td>\n", | |
| " <td>929</td>\n", | |
| " <td>1163</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>4</th>\n", | |
| " <td>133</td>\n", | |
| " <td>826</td>\n", | |
| " <td>938</td>\n", | |
| " <td>852</td>\n", | |
| " <td>0</td>\n", | |
| " <td>737</td>\n", | |
| " <td>658</td>\n", | |
| " <td>1081</td>\n", | |
| " <td>726</td>\n", | |
| " <td>1263</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>5</th>\n", | |
| " <td>621</td>\n", | |
| " <td>871</td>\n", | |
| " <td>1008</td>\n", | |
| " <td>922</td>\n", | |
| " <td>739</td>\n", | |
| " <td>0</td>\n", | |
| " <td>877</td>\n", | |
| " <td>1300</td>\n", | |
| " <td>755</td>\n", | |
| " <td>1333</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>6</th>\n", | |
| " <td>557</td>\n", | |
| " <td>1003</td>\n", | |
| " <td>1133</td>\n", | |
| " <td>1038</td>\n", | |
| " <td>602</td>\n", | |
| " <td>968</td>\n", | |
| " <td>0</td>\n", | |
| " <td>838</td>\n", | |
| " <td>903</td>\n", | |
| " <td>1478</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>7</th>\n", | |
| " <td>971</td>\n", | |
| " <td>1418</td>\n", | |
| " <td>1278</td>\n", | |
| " <td>1183</td>\n", | |
| " <td>1017</td>\n", | |
| " <td>1252</td>\n", | |
| " <td>794</td>\n", | |
| " <td>0</td>\n", | |
| " <td>1318</td>\n", | |
| " <td>1892</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>8</th>\n", | |
| " <td>682</td>\n", | |
| " <td>686</td>\n", | |
| " <td>1074</td>\n", | |
| " <td>975</td>\n", | |
| " <td>786</td>\n", | |
| " <td>741</td>\n", | |
| " <td>922</td>\n", | |
| " <td>1345</td>\n", | |
| " <td>0</td>\n", | |
| " <td>1175</td>\n", | |
| " </tr>\n", | |
| " <tr>\n", | |
| " <th>9</th>\n", | |
| " <td>1077</td>\n", | |
| " <td>900</td>\n", | |
| " <td>1207</td>\n", | |
| " <td>1121</td>\n", | |
| " <td>1148</td>\n", | |
| " <td>1351</td>\n", | |
| " <td>1383</td>\n", | |
| " <td>1807</td>\n", | |
| " <td>1096</td>\n", | |
| " <td>0</td>\n", | |
| " </tr>\n", | |
| " </tbody>\n", | |
| "</table>\n", | |
| "</div>" | |
| ], | |
| "text/plain": [ | |
| " 0 1 2 3 4 5 6 7 8 9\n", | |
| "0 0 722 823 736 151 670 600 1023 622 1147\n", | |
| "1 709 0 1089 1003 813 930 949 1372 639 937\n", | |
| "2 807 1026 0 413 877 1081 1113 1256 989 1189\n", | |
| "3 702 956 435 0 772 976 1008 1203 929 1163\n", | |
| "4 133 826 938 852 0 737 658 1081 726 1263\n", | |
| "5 621 871 1008 922 739 0 877 1300 755 1333\n", | |
| "6 557 1003 1133 1038 602 968 0 838 903 1478\n", | |
| "7 971 1418 1278 1183 1017 1252 794 0 1318 1892\n", | |
| "8 682 686 1074 975 786 741 922 1345 0 1175\n", | |
| "9 1077 900 1207 1121 1148 1351 1383 1807 1096 0" | |
| ] | |
| }, | |
| "execution_count": 10, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "try:\n", | |
| " objective = 'duration' # distance or duration\n", | |
| " distance_matrix = build_distance_matrix(depot, shipments[0:9], objective)\n", | |
| " df = pd.DataFrame(distance_matrix)\n", | |
| " routes = solve_vrp_for(distance_matrix, num_vehicles)\n", | |
| "except:\n", | |
| " print('Something went wrong solving for duration.')\n", | |
| "\n", | |
| "df" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Map the Solution" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "if routes:\n", | |
| " fig = gmaps.figure()\n", | |
| " fig.add_layer(depot_layer)\n", | |
| " fig.add_layer(shipments_layer)\n", | |
| " map_solution(depot, shipments, routes)\n", | |
| "else:\n", | |
| " print('No solution found.') \n", | |
| "\n", | |
| "fig" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "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.7.3" | |
| } | |
| }, | |
| "nbformat": 4, | |
| "nbformat_minor": 2 | |
| } |
Distance Matrix API has the following per request limits:
To allow for matrices beyond 10 x 10, you would have to split up the input matrix into pieces that meet the usage limits above, make multiple Distance Matrix API calls, and join the results to form a single matrix.
Sorry. Binder ask me to build and I click it. But it returns
Build failed with 504, please run 'jupyter lab build' on the server for full output
The Map Depot and Shipments code block prints:
Error displaying widget: model not found
Thank you @hollemawoolpert for the response.
Reading the VRP documentation again, this link helps you compute bigger matrices with multiple requests.
Hi, So running the vrp for lets say 25 points and 5 vehicles, outputs the routes but they are only assigned to 1 or 2 vehicles and the rest 3 vehicles are left no job to do. Is there a workaround to this so as to make sure all the vehicles do at least some visits/distance and not just zero. Actually the problem we currently face is our depot is outside the locations' cluster and so I think the VRP is assigning only 1-2 vehicles. If we set max_distance to a lower value than the deafult 2*() then program gets stuck in infinite loop.
Thanks!
Hi, while running the function, gmaps.symbol_layer
I am getting the following error,
AttributeError Traceback (most recent call last)
1 depot = {
2 'location': (29.399013114383962, -98.52633476257324)
3 }
----> 5 depot_layer = gmaps.symbol_layer(
6 [depot['location']], hover_text='Depot', info_box_content='Depot',
7 fill_color='white', stroke_color='red', scale=8
8 )
File ~\AppData\Local\Apps\envs\route_opt\lib\site-packages\gmaps\marker.py:477, in symbol_layer(locations, hover_text, fill_color, fill_opacity, stroke_color, stroke_opacity, scale, info_box_content, display_info_box)
328 def symbol_layer(
329 locations, hover_text='', fill_color=None,
330 fill_opacity=1.0, stroke_color=None, stroke_opacity=1.0,
331 scale=3, info_box_content=None, display_info_box=None):
332 """
333 Symbol layer
334
(...)
475 A :class:`gmaps.Markers` instance.
476 """
--> 477 options = _symbol_layer_options(
478 locations, hover_text, fill_color,
479 fill_opacity, stroke_color, stroke_opacity, scale,
480 info_box_content, display_info_box)
481 symbols = [Symbol(**option) for option in options]
482 return Markers(markers=symbols)
File ~\AppData\Local\Apps\envs\route_opt\lib\site-packages\gmaps\marker.py:275, in _symbol_layer_options(locations, hover_text, fill_color, fill_opacity, stroke_color, stroke_opacity, scale, info_box_content, display_info_box)
273 if is_atomic(hover_text):
274 hover_text = [hover_text] * number_markers
--> 275 if is_atomic(scale):
276 scale = [scale] * number_markers
277 if is_color_atomic(fill_color):
File ~\AppData\Local\Apps\envs\route_opt\lib\site-packages\gmaps\options.py:40, in is_atomic(elem)
34 def is_atomic(elem):
35 """
36 True if an element is a single atom and false if it's a collection
37 """
38 return (
39 isinstance(elem, string_types) or
---> 40 not isinstance(elem, collections.Iterable)
41 )
AttributeError: module 'collections' has no attribute 'Iterable'
Please help.
Hola, mientras ejecuta la función,
gmaps.symbol_layerEstoy recibiendo el siguiente error,AttributeError Traceback (most recent call last) 1 depot = { 2 'location': (29.399013114383962, -98.52633476257324) 3 } ----> 5 depot_layer = gmaps.symbol_layer( 6 [depot['location']], hover_text='Depot', info_box_content='Depot', 7 fill_color='white', stroke_color='red', scale=8 8 ) File ~\AppData\Local\Apps\envs\route_opt\lib\site-packages\gmaps\marker.py:477, in symbol_layer(locations, hover_text, fill_color, fill_opacity, stroke_color, stroke_opacity, scale, info_box_content, display_info_box) 328 def symbol_layer( 329 locations, hover_text='', fill_color=None, 330 fill_opacity=1.0, stroke_color=None, stroke_opacity=1.0, 331 scale=3, info_box_content=None, display_info_box=None): 332 """ 333 Symbol layer 334 (...) 475 A :class:`gmaps.Markers` instance. 476 """ --> 477 options = _symbol_layer_options( 478 locations, hover_text, fill_color, 479 fill_opacity, stroke_color, stroke_opacity, scale, 480 info_box_content, display_info_box) 481 symbols = [Symbol(**option) for option in options] 482 return Markers(markers=symbols) File ~\AppData\Local\Apps\envs\route_opt\lib\site-packages\gmaps\marker.py:275, in _symbol_layer_options(locations, hover_text, fill_color, fill_opacity, stroke_color, stroke_opacity, scale, info_box_content, display_info_box) 273 if is_atomic(hover_text): 274 hover_text = [hover_text] * number_markers --> 275 if is_atomic(scale): 276 scale = [scale] * number_markers 277 if is_color_atomic(fill_color): File ~\AppData\Local\Apps\envs\route_opt\lib\site-packages\gmaps\options.py:40, in is_atomic(elem) 34 def is_atomic(elem): 35 """ 36 True if an element is a single atom and false if it's a collection 37 """ 38 return ( 39 isinstance(elem, string_types) or ---> 40 not isinstance(elem, collections.Iterable) 41 ) AttributeError: module 'collections' has no attribute 'Iterable'Por favor ayuda.
Hola, Lograste resolverlo?
Google Distance Matrix API won't allow more than 10 elements for the calculation
if the change the shipments[0:9] to shipments[0:].
How can I overcome this limitation?
MAX_ELEMENTS_EXCEEDED