1#!/usr/bin/env python3 2# Copyright 2010-2021 Google LLC 3# Licensed under the Apache License, Version 2.0 (the "License"); 4# you may not use this file except in compliance with the License. 5# You may obtain a copy of the License at 6# 7# http://www.apache.org/licenses/LICENSE-2.0 8# 9# Unless required by applicable law or agreed to in writing, software 10# distributed under the License is distributed on an "AS IS" BASIS, 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12# See the License for the specific language governing permissions and 13# limitations under the License. 14# [START program] 15"""Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). 16 17 This is a sample using the routing library python wrapper to solve a CVRPTW 18 problem. 19 A description of the problem can be found here: 20 http://en.wikipedia.org/wiki/Vehicle_routing_problem. 21 22 Distances are in meters and time in minutes. 23""" 24 25# [START import] 26import functools 27from ortools.constraint_solver import routing_enums_pb2 28from ortools.constraint_solver import pywrapcp 29# [END import] 30 31 32# [START data_model] 33def create_data_model(): 34 """Stores the data for the problem.""" 35 data = {} 36 # Locations in block unit 37 locations_ = \ 38 [(4, 4), # depot 39 (2, 0), (8, 0), # locations to visit 40 (0, 1), (1, 1), 41 (5, 2), (7, 2), 42 (3, 3), (6, 3), 43 (5, 5), (8, 5), 44 (1, 6), (2, 6), 45 (3, 7), (6, 7), 46 (0, 8), (7, 8)] 47 # Compute locations in meters using the block dimension defined as follow 48 # Manhattan average block: 750ft x 264ft -> 228m x 80m 49 # here we use: 114m x 80m city block 50 # src: https://nyti.ms/2GDoRIe "NY Times: Know Your distance" 51 data['locations'] = [(l[0] * 114, l[1] * 80) for l in locations_] 52 data['numlocations_'] = len(data['locations']) 53 data['time_windows'] = \ 54 [(0, 0), 55 (75, 85), (75, 85), # 1, 2 56 (60, 70), (45, 55), # 3, 4 57 (0, 8), (50, 60), # 5, 6 58 (0, 10), (10, 20), # 7, 8 59 (0, 10), (75, 85), # 9, 10 60 (85, 95), (5, 15), # 11, 12 61 (15, 25), (10, 20), # 13, 14 62 (45, 55), (30, 40)] # 15, 16 63 data['demands'] = \ 64 [0, # depot 65 1, 1, # 1, 2 66 2, 4, # 3, 4 67 2, 4, # 5, 6 68 8, 8, # 7, 8 69 1, 2, # 9,10 70 1, 2, # 11,12 71 4, 4, # 13, 14 72 8, 8] # 15, 16 73 data['time_per_demand_unit'] = 5 # 5 minutes/unit 74 data['num_vehicles'] = 4 75 data['breaks'] = [(2, False), (2, False), (2, False), (2, False)] 76 data['vehicle_capacity'] = 15 77 data['vehicle_speed'] = 83 # Travel speed: 5km/h converted in m/min 78 data['depot'] = 0 79 return data 80 # [END data_model] 81 82 83def manhattan_distance(position_1, position_2): 84 """Computes the Manhattan distance between two points.""" 85 return (abs(position_1[0] - position_2[0]) + 86 abs(position_1[1] - position_2[1])) 87 88 89def create_distance_evaluator(data): 90 """Creates callback to return distance between points.""" 91 distances_ = {} 92 # precompute distance between location to have distance callback in O(1) 93 for from_node in range(data['numlocations_']): 94 distances_[from_node] = {} 95 for to_node in range(data['numlocations_']): 96 if from_node == to_node: 97 distances_[from_node][to_node] = 0 98 else: 99 distances_[from_node][to_node] = (manhattan_distance( 100 data['locations'][from_node], data['locations'][to_node])) 101 102 def distance_evaluator(manager, from_node, to_node): 103 """Returns the manhattan distance between the two nodes.""" 104 return distances_[manager.IndexToNode(from_node)][manager.IndexToNode( 105 to_node)] 106 107 return distance_evaluator 108 109 110def create_demand_evaluator(data): 111 """Creates callback to get demands at each location.""" 112 demands_ = data['demands'] 113 114 def demand_evaluator(manager, node): 115 """Returns the demand of the current node.""" 116 return demands_[manager.IndexToNode(node)] 117 118 return demand_evaluator 119 120 121def add_capacity_constraints(routing, data, demand_evaluator_index): 122 """Adds capacity constraint.""" 123 capacity = 'Capacity' 124 routing.AddDimension( 125 demand_evaluator_index, 126 0, # null capacity slack 127 data['vehicle_capacity'], 128 True, # start cumul to zero 129 capacity) 130 131 132def create_time_evaluator(data): 133 """Creates callback to get total times between locations.""" 134 135 def service_time(data, node): 136 """Gets the service time for the specified location.""" 137 return data['demands'][node] * data['time_per_demand_unit'] 138 139 def travel_time(data, from_node, to_node): 140 """Gets the travel times between two locations.""" 141 if from_node == to_node: 142 travel_time = 0 143 else: 144 travel_time = manhattan_distance( 145 data['locations'][from_node], 146 data['locations'][to_node]) / data['vehicle_speed'] 147 return travel_time 148 149 total_time_ = {} 150 # precompute total time to have time callback in O(1) 151 for from_node in range(data['numlocations_']): 152 total_time_[from_node] = {} 153 for to_node in range(data['numlocations_']): 154 if from_node == to_node: 155 total_time_[from_node][to_node] = 0 156 else: 157 total_time_[from_node][to_node] = int( 158 service_time(data, from_node) + 159 travel_time(data, from_node, to_node)) 160 161 def time_evaluator(manager, from_node, to_node): 162 """Returns the total time between the two nodes.""" 163 return total_time_[manager.IndexToNode(from_node)][manager.IndexToNode( 164 to_node)] 165 166 return time_evaluator 167 168 169def add_time_window_constraints(routing, manager, data, time_evaluator_index): 170 """Add Global Span constraint.""" 171 time = 'Time' 172 horizon = 120 173 routing.AddDimension( 174 time_evaluator_index, 175 horizon, # allow waiting time 176 horizon, # maximum time per vehicle 177 False, # don't force start cumul to zero 178 time) 179 time_dimension = routing.GetDimensionOrDie(time) 180 # Add time window constraints for each location except depot 181 # and 'copy' the slack var in the solution object (aka Assignment) to print it 182 for location_idx, time_window in enumerate(data['time_windows']): 183 if location_idx == data['depot']: 184 continue 185 index = manager.NodeToIndex(location_idx) 186 time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1]) 187 routing.AddToAssignment(time_dimension.SlackVar(index)) 188 # Add time window constraints for each vehicle start node 189 # and 'copy' the slack var in the solution object (aka Assignment) to print it 190 for vehicle_id in range(data['num_vehicles']): 191 index = routing.Start(vehicle_id) 192 time_dimension.CumulVar(index).SetRange(data['time_windows'][0][0], 193 data['time_windows'][0][1]) 194 routing.AddToAssignment(time_dimension.SlackVar(index)) 195 # The time window at the end node was impliclty set in the time dimension 196 # definition to be [0, horizon]. 197 # Warning: Slack var is not defined for vehicle end nodes and should not 198 # be added to the assignment. 199 200 201# [START solution_printer] 202def print_solution(data, manager, routing, assignment): # pylint:disable=too-many-locals 203 """Prints assignment on console.""" 204 print('Objective: {}'.format(assignment.ObjectiveValue())) 205 206 print('Breaks:') 207 intervals = assignment.IntervalVarContainer() 208 for i in range(intervals.Size()): 209 brk = intervals.Element(i) 210 if brk.PerformedValue() == 1: 211 print('{}: Start({}) Duration({})'.format(brk.Var().Name(), 212 brk.StartValue(), 213 brk.DurationValue())) 214 else: 215 print('{}: Unperformed'.format(brk.Var().Name())) 216 217 total_distance = 0 218 total_load = 0 219 total_time = 0 220 capacity_dimension = routing.GetDimensionOrDie('Capacity') 221 time_dimension = routing.GetDimensionOrDie('Time') 222 for vehicle_id in range(data['num_vehicles']): 223 index = routing.Start(vehicle_id) 224 plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) 225 distance = 0 226 while not routing.IsEnd(index): 227 load_var = capacity_dimension.CumulVar(index) 228 time_var = time_dimension.CumulVar(index) 229 slack_var = time_dimension.SlackVar(index) 230 plan_output += ' {0} Load({1}) Time({2},{3}) Slack({4},{5}) ->'.format( 231 manager.IndexToNode(index), assignment.Value(load_var), 232 assignment.Min(time_var), assignment.Max(time_var), 233 assignment.Min(slack_var), assignment.Max(slack_var)) 234 previous_index = index 235 index = assignment.Value(routing.NextVar(index)) 236 distance += routing.GetArcCostForVehicle(previous_index, index, 237 vehicle_id) 238 load_var = capacity_dimension.CumulVar(index) 239 time_var = time_dimension.CumulVar(index) 240 plan_output += ' {0} Load({1}) Time({2},{3})\n'.format( 241 manager.IndexToNode(index), assignment.Value(load_var), 242 assignment.Min(time_var), assignment.Max(time_var)) 243 plan_output += 'Distance of the route: {0}m\n'.format(distance) 244 plan_output += 'Load of the route: {}\n'.format( 245 assignment.Value(load_var)) 246 plan_output += 'Time of the route: {}\n'.format( 247 assignment.Value(time_var)) 248 print(plan_output) 249 total_distance += distance 250 total_load += assignment.Value(load_var) 251 total_time += assignment.Value(time_var) 252 print('Total Distance of all routes: {0}m'.format(total_distance)) 253 print('Total Load of all routes: {}'.format(total_load)) 254 print('Total Time of all routes: {0}min'.format(total_time)) 255 # [END solution_printer] 256 257 258def main(): 259 """Entry point of the program.""" 260 # Instantiate the data problem. 261 # [START data] 262 data = create_data_model() 263 # [END data] 264 265 # Create the routing index manager 266 manager = pywrapcp.RoutingIndexManager(data['numlocations_'], 267 data['num_vehicles'], data['depot']) 268 269 # Create Routing Model 270 routing = pywrapcp.RoutingModel(manager) 271 272 # Define weight of each edge 273 distance_evaluator_index = routing.RegisterTransitCallback( 274 functools.partial(create_distance_evaluator(data), manager)) 275 routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator_index) 276 277 # Add Capacity constraint 278 demand_evaluator_index = routing.RegisterUnaryTransitCallback( 279 functools.partial(create_demand_evaluator(data), manager)) 280 add_capacity_constraints(routing, data, demand_evaluator_index) 281 282 # Add Time Window constraint 283 time_evaluator_index = routing.RegisterTransitCallback( 284 functools.partial(create_time_evaluator(data), manager)) 285 add_time_window_constraints(routing, manager, data, time_evaluator_index) 286 287 # Add breaks 288 time_dimension = routing.GetDimensionOrDie('Time') 289 node_visit_transit = {} 290 for index in range(routing.Size()): 291 node = manager.IndexToNode(index) 292 node_visit_transit[index] = int(data['demands'][node] * 293 data['time_per_demand_unit']) 294 295 break_intervals = {} 296 for v in range(data['num_vehicles']): 297 vehicle_break = data['breaks'][v] 298 break_intervals[v] = [ 299 routing.solver().FixedDurationIntervalVar(15, 100, vehicle_break[0], 300 vehicle_break[1], 301 f'Break for vehicle {v}') 302 ] 303 time_dimension.SetBreakIntervalsOfVehicle(break_intervals[v], v, 304 node_visit_transit.values()) 305 306 # Setting first solution heuristic (cheapest addition). 307 # [START parameters] 308 search_parameters = pywrapcp.DefaultRoutingSearchParameters() 309 search_parameters.first_solution_strategy = ( 310 routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # pylint: disable=no-member 311 # [END parameters] 312 313 # Solve the problem. 314 # [START solve] 315 assignment = routing.SolveWithParameters(search_parameters) 316 # [END solve] 317 318 # Print solution on console. 319 # [START print_solution] 320 if assignment: 321 print_solution(data, manager, routing, assignment) 322 else: 323 print('No solution found!') 324 # [END print_solution] 325 326 327if __name__ == '__main__': 328 main() 329# [END program] 330