Skip to content

Instantly share code, notes, and snippets.

@Nogbit

Nogbit/README.md

Forked from hollemawoolpert/README.md
Last active August 15, 2019 16:59
Show Gist options
  • Save Nogbit/8e69d92c58aa68474baff06b526a64cf to your computer and use it in GitHub Desktop.
Save Nogbit/8e69d92c58aa68474baff06b526a64cf to your computer and use it in GitHub Desktop.
Download ZIP
Simple VRP with Google Developer Resources
Raw
README.md

Binder

Simple VRP with Google Developer Resources¶

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.

Getting Started

You will need a Google Maps Platform API Key.

Run on binder

Run locally

Prerequisites
  • Python 3 environment
  • JupyterLab
pip install jupyterlab
Installation
pip install -r requirements.txt
jupyter nbextension enable --py --sys-prefix gmaps
Run notebook
jupyter notebook

Libraries and Services

Raw
postBuild
#!/bin/bash
jupyter nbextension enable --py --sys-prefix gmaps
Raw
requirements.txt
gmaps==0.9.0
googlemaps==3.0.2
ortools==7.3.7083
pandas==0.25.0
Display the source blob
Display the rendered blob
Raw
simple-vrp-google-dev.ipynb
{
"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"
]
},
{
"cell_type": "code",
"execution_count": null,
"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"
]
},
{
"cell_type": "code",
"execution_count": null,
"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"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"num_vehicles = 3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Create Shipments"
]
},
{
"cell_type": "code",
"execution_count": null,
"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",
"fig"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Build Distance Matrix"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"scrolled": true
},
"outputs": [],
"source": [
"import googlemaps\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",
" import pandas as pd\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"
]
},
{
"cell_type": "code",
"execution_count": null,
"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"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"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"
]
},
{
"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": [
"### Solve for Duration"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"try:\n",
" objective = 'duration' # distance or duration\n",
" distance_matrix = build_distance_matrix(depot, shipments[0:9], objective)\n",
" routes = solve_vrp_for(distance_matrix, num_vehicles)\n",
"except:\n",
" print('Something went wrong solving for duration.')\n",
"\n",
"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": "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.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment