Skip to content

Instantly share code, notes, and snippets.

@takazawa

takazawa/example-CVRPTW-ortools.ipynb

Last active April 12, 2024 06:34
Show Gist options
  • Save takazawa/13f1ae2cd35c3add5c27e9c5ff6de37a to your computer and use it in GitHub Desktop.
Save takazawa/13f1ae2cd35c3add5c27e9c5ff6de37a to your computer and use it in GitHub Desktop.
Download ZIP
Example of Python implementation of Capacitated vehicle routing problem with time windows (CVRPTW) with Google OR-tools
Display the source blob
Display the rendered blob
Raw
example-CVRPTW-ortools.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from __future__ import print_function\n",
"from ortools.constraint_solver import routing_enums_pb2\n",
"from ortools.constraint_solver import pywrapcp"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"time_matrix = [\n",
" [0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7],\n",
" [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14],\n",
" [9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9],\n",
" [8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16],\n",
" [7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14],\n",
" [3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8],\n",
" [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5],\n",
" [2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10],\n",
" [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6],\n",
" [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5],\n",
" [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4],\n",
" [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10],\n",
" [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8],\n",
" [4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6],\n",
" [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2],\n",
" [9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9],\n",
" [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0],\n",
" ]\n",
"\n",
"time_windows = [\n",
" (0, 60), # depot\n",
" (7, 30), # 1\n",
" (10, 40), # 2\n",
" (16, 50), # 3\n",
" (10, 30), # 4\n",
" (0, 40), # 5\n",
" (5, 60), # 6\n",
" (0, 50), # 7\n",
" (5, 50), # 8\n",
" (0, 30), # 9\n",
" (10, 40), # 10\n",
" (10, 15), # 11\n",
" (0, 5), # 12\n",
" (5, 10), # 13\n",
" (7, 8), # 14\n",
" (10, 15), # 15\n",
" (11, 15), # 16\n",
" ]\n",
"\n",
"\n",
"\n",
"demands = [0, 1, 1, 2, 4, 2, 4, 8, 3, 1, 2, 1, 2, 4, 4, 5, 5]\n",
"\n",
"\n",
"num_vehicles = 4\n",
"vehicle_capacities = [15, 15, 15, 15]\n",
"\n",
"depot_index = 0\n",
"\n",
"time_limit_seconds = 10 # time limit for calculation"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"def create_data_model(time_matrix, time_windows, num_vehicles, demands, vehicle_capacities, depot_index):\n",
" \"\"\"Stores the data for the problem.\"\"\"\n",
" data = {}\n",
" data['time_matrix'] = time_matrix\n",
" data['time_windows'] = time_windows\n",
" data['num_vehicles'] = num_vehicles\n",
" data['demands'] = demands\n",
" data['vehicle_capacities'] = vehicle_capacities\n",
" data['depot'] = depot_index\n",
" return data"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"\"\"\"Capacitated Vehicles Routing Problem (CVRP) with Time Windows.\"\"\"\n",
"\n",
"def print_solution(data, manager, routing, solution):\n",
" \"\"\"Prints solution on console.\"\"\"\n",
" total_distance = 0\n",
" total_load = 0\n",
" time_dimension = routing.GetDimensionOrDie('Time')\n",
" total_time = 0\n",
" \n",
" for vehicle_id in range(data['num_vehicles']):\n",
" index = routing.Start(vehicle_id)\n",
" plan_output = 'Route for vehicle {}:\\n'.format(vehicle_id)\n",
" route_load = 0\n",
" while not routing.IsEnd(index):\n",
" node_index = manager.IndexToNode(index)\n",
" time_var = time_dimension.CumulVar(index)\n",
" route_load += data['demands'][node_index]\n",
" plan_output += 'Place {0:>2} Arrive at {2:>2}min Depart at {3:>2}min (Load {1:>2})\\n'.format(manager.IndexToNode(index), route_load, solution.Min(time_var), solution.Max(time_var))\n",
" \n",
" previous_index = index\n",
" index = solution.Value(routing.NextVar(index))\n",
" \n",
" \n",
" time_var = time_dimension.CumulVar(index)\n",
" total_time += solution.Min(time_var)\n",
" plan_output +=\"Place {0:>2} Arrive at {2:>2}min \\n\\n\".format(manager.IndexToNode(index), route_load, solution.Min(time_var), solution.Max(time_var))\n",
" \n",
" # route output\n",
" plan_output += 'Load of the route: {}\\n'.format(route_load)\n",
" plan_output += 'Time of the route: {}min\\n'.format(solution.Min(time_var))\n",
" plan_output += \"--------------------\"\n",
" \n",
" print(plan_output)\n",
" total_load += route_load\n",
"\n",
" print('Total load of all routes: {}'.format(total_load))\n",
" print('Total time of all routes: {}min'.format(total_time))\n",
"\n",
" \n",
"def main():\n",
" \"\"\"Solve the VRP with time windows.\"\"\"\n",
" # Instantiate the data problem.\n",
" data = create_data_model(time_matrix, time_windows, num_vehicles, demands, vehicle_capacities, depot_index)\n",
"\n",
" # Create the routing index manager.\n",
" manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),\n",
" data['num_vehicles'], data['depot'])\n",
"\n",
" # Create Routing Model.\n",
" routing = pywrapcp.RoutingModel(manager)\n",
"\n",
"\n",
" # Create and register a transit callback.\n",
" def time_callback(from_index, to_index):\n",
" \"\"\"Returns the travel time between the two nodes.\"\"\"\n",
" # Convert from routing variable Index to time matrix NodeIndex.\n",
" from_node = manager.IndexToNode(from_index)\n",
" to_node = manager.IndexToNode(to_index)\n",
" return data['time_matrix'][from_node][to_node]\n",
"\n",
" transit_callback_index = routing.RegisterTransitCallback(time_callback)\n",
"\n",
" # Define cost of each arc.\n",
" routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)\n",
" \n",
" # Add Capacity constraint.\n",
" def demand_callback(from_index):\n",
" \"\"\"Returns the demand of the node.\"\"\"\n",
" # Convert from routing variable Index to demands NodeIndex.\n",
" from_node = manager.IndexToNode(from_index)\n",
" return data['demands'][from_node]\n",
"\n",
" demand_callback_index = routing.RegisterUnaryTransitCallback(\n",
" demand_callback)\n",
" routing.AddDimensionWithVehicleCapacity(\n",
" demand_callback_index,\n",
" 0, # null capacity slack\n",
" data['vehicle_capacities'], # vehicle maximum capacities\n",
" True, # start cumul to zero\n",
" 'Capacity')\n",
" \n",
" # Add Time Windows constraint.\n",
" time = 'Time'\n",
" routing.AddDimension(\n",
" transit_callback_index,\n",
" 30, # allow waiting time\n",
" 30, # maximum time per vehicle\n",
" False, # Don't force start cumul to zero.\n",
" time)\n",
" time_dimension = routing.GetDimensionOrDie(time)\n",
" \n",
" # Add time window constraints for each location except depot.\n",
" for location_idx, time_window in enumerate(data['time_windows']):\n",
" if location_idx == 0:\n",
" continue\n",
" index = manager.NodeToIndex(location_idx)\n",
" time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])\n",
"\n",
" # Add time window constraints for each vehicle start node.\n",
" for vehicle_id in range(data['num_vehicles']):\n",
" index = routing.Start(vehicle_id)\n",
" time_dimension.CumulVar(index).SetRange(data['time_windows'][0][0],\n",
" data['time_windows'][0][1])\n",
"\n",
" # Instantiate route start and end times to produce feasible times.\n",
" for i in range(data['num_vehicles']):\n",
" routing.AddVariableMinimizedByFinalizer(\n",
" time_dimension.CumulVar(routing.Start(i)))\n",
" routing.AddVariableMinimizedByFinalizer(\n",
" time_dimension.CumulVar(routing.End(i)))\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",
" search_parameters.time_limit.seconds = time_limit_seconds\n",
" \n",
" # Solve the problem.\n",
" solution = routing.SolveWithParameters(search_parameters)\n",
"\n",
" # Print solution on console.\n",
" if solution:\n",
" print_solution(data, manager, routing, solution)\n",
" return solution"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Route for vehicle 0:\n",
"Place 0 Arrive at 0min Depart at 0min (Load 0)\n",
"Place 9 Arrive at 2min Depart at 5min (Load 1)\n",
"Place 14 Arrive at 7min Depart at 8min (Load 5)\n",
"Place 16 Arrive at 11min Depart at 11min (Load 10)\n",
"Place 0 Arrive at 18min \n",
"\n",
"Load of the route: 10\n",
"Time of the route: 18min\n",
"--------------------\n",
"Route for vehicle 1:\n",
"Place 0 Arrive at 0min Depart at 0min (Load 0)\n",
"Place 12 Arrive at 4min Depart at 5min (Load 2)\n",
"Place 11 Arrive at 10min Depart at 10min (Load 3)\n",
"Place 15 Arrive at 13min Depart at 13min (Load 8)\n",
"Place 3 Arrive at 19min Depart at 19min (Load 10)\n",
"Place 4 Arrive at 20min Depart at 20min (Load 14)\n",
"Place 1 Arrive at 22min Depart at 22min (Load 15)\n",
"Place 0 Arrive at 28min \n",
"\n",
"Load of the route: 15\n",
"Time of the route: 28min\n",
"--------------------\n",
"Route for vehicle 2:\n",
"Place 0 Arrive at 0min Depart at 0min (Load 0)\n",
"Place 7 Arrive at 2min Depart at 2min (Load 8)\n",
"Place 13 Arrive at 5min Depart at 5min (Load 12)\n",
"Place 0 Arrive at 9min \n",
"\n",
"Load of the route: 12\n",
"Time of the route: 9min\n",
"--------------------\n",
"Route for vehicle 3:\n",
"Place 0 Arrive at 0min Depart at 0min (Load 0)\n",
"Place 5 Arrive at 3min Depart at 5min (Load 2)\n",
"Place 6 Arrive at 5min Depart at 7min (Load 6)\n",
"Place 2 Arrive at 10min Depart at 10min (Load 7)\n",
"Place 10 Arrive at 14min Depart at 14min (Load 9)\n",
"Place 8 Arrive at 18min Depart at 18min (Load 12)\n",
"Place 0 Arrive at 21min \n",
"\n",
"Load of the route: 12\n",
"Time of the route: 21min\n",
"--------------------\n",
"Total load of all routes: 49\n",
"Total time of all routes: 76min\n"
]
}
],
"source": [
"solution = main()"
]
}
],
"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.6"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment