I want to solve a vehicle routing problem with ORTools, both distance and duration matrix will be used. But the problem is when I change the matrix , it wouldn't give me any solutions anymore! There are 2 groups of matrixes. with the commented matrixes there is solution, but with the other group, there is not. do you have any idea why this is happening:
from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model():
"""Stores the data for the problem."""
data = {}
#data['distance_matrix']=[[0, 329, 146, 157, 318, 528, 457, 242, 491, 335, 471, 456, 391, 128, 461, 555, 460], [329, 0, 399, 384, 544, 493, 339, 378, 108, 243, 125, 394, 136, 561, 505, 315, 447], [146, 399, 0, 262, 471, 316, 297, 227, 548, 377, 267, 430, 383, 154, 234, 188, 400], [157, 384, 262, 0, 440, 271, 383, 525, 223, 367, 511, 354, 112, 539, 159, 152, 373], [318, 544, 471, 440, 0, 423, 112, 381, 346, 512, 161, 239, 581, 291, 284, 145, 143], [528, 493, 316, 271, 423, 0, 380, 196, 409, 212, 199, 277, 387, 515, 391, 261, 318], [457, 339, 297, 383, 112, 380, 0, 379, 298, 267, 482, 247, 462, 256, 296, 533, 200], [242, 378, 227, 525, 381, 196, 379, 0, 156, 230, 551, 555, 338, 372, 403, 358, 506], [491, 108, 548, 223, 346, 409, 298, 156, 0, 140, 532, 405, 531, 129, 220, 482, 222], [335, 243, 377, 367, 512, 212, 267, 230, 140, 0, 418, 440, 526, 255, 455, 296, 430], [471, 125, 267, 511, 161, 199, 482, 551, 532, 418, 0, 439, 285, 181, 254, 208, 304], [456, 394, 430, 354, 239, 277, 247, 555, 405, 440, 439, 0, 397, 229, 121, 385, 147], [391, 136, 383, 112, 581, 387, 462, 338, 531, 526, 285, 397, 0, 544, 205, 197, 226], [128, 561, 154, 539, 291, 515, 256, 372, 129, 255, 181, 229, 544, 0, 150, 204, 516], [461, 505, 234, 159, 284, 391, 296, 403, 220, 455, 254, 121, 205, 150, 0, 192, 544], [555, 315, 188, 152, 145, 261, 533, 358, 482, 296, 208, 385, 197, 204, 192, 0, 138], [460, 447, 400, 373, 143, 318, 200, 506, 222, 430, 304, 147, 226, 516, 544, 138, 0]]
data['distance_matrix']=[[0, 228, 299, 301, 235, 208, 405, 447, 144, 579], [228, 0, 343, 288, 357, 426, 530, 510, 122, 490], [299, 343, 0, 236, 228, 523, 274, 377, 397, 530], [301, 288, 236, 0, 594, 523, 289, 397, 154, 380], [235, 357, 228, 594, 0, 558, 370, 444, 173, 558], [208, 426, 523, 523, 558, 0, 219, 278, 504, 507], [405, 530, 274, 289, 370, 219, 0, 195, 283, 257], [447, 510, 377, 397, 444, 278, 195, 0, 407, 417], [144, 122, 397, 154, 173, 504, 283, 407, 0, 273], [579, 490, 530, 380, 558, 507, 257, 417, 273, 0]]
data['time_matrix']=[[0, 205, 519, 308, 428, 574, 399, 138, 573, 541], [205, 0, 447, 578, 296, 536, 135, 345, 198, 315], [519, 447, 0, 209, 438, 174, 231, 382, 104, 522], [308, 578, 209, 0, 235, 264, 492, 305, 134, 538], [428, 296, 438, 235, 0, 600, 177, 435, 204, 556], [574, 536, 174, 264, 600, 0, 476, 119, 183, 476], [399, 135, 231, 492, 177, 476, 0, 497, 208, 167], [138, 345, 382, 305, 435, 119, 497, 0, 344, 454], [573, 198, 104, 134, 204, 183, 208, 344, 0, 422], [541, 315, 522, 538, 556, 476, 167, 454, 422, 0]]
data['cost_matrix']=[[0, 160, 135, 433, 581, 453, 336, 329, 343, 237], [160, 0, 313, 596, 576, 458, 264, 380, 348, 354], [135, 313, 0, 591, 391, 211, 561, 236, 304, 414], [433, 596, 591, 0, 539, 253, 427, 300, 214, 118], [581, 576, 391, 539, 0, 243, 521, 499, 560, 255], [453, 458, 211, 253, 243, 0, 571, 216, 121, 314], [336, 264, 561, 427, 521, 571, 0, 425, 271, 165], [329, 380, 236, 300, 499, 216, 425, 0, 425, 549], [343, 348, 304, 214, 560, 121, 271, 425, 0, 176], [237, 354, 414, 118, 255, 314, 165, 549, 176, 0]]
data['num_vehicles'] = 4
data['depot'] = 0
return data
def print_solution(data, manager, routing, assignment):
"""Prints assignment on console."""
total_cost ,total_distance,total_time= 0,0,0
print('Objective: {}'.format(assignment.ObjectiveValue()))
distance_dimension=routing.GetDimensionOrDie('Distance')
time_dimension=routing.GetDimensionOrDie('Time')
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_cost = 0
route_distance = 0
route_time = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
distance_var=distance_dimension.CumulVar(index)
time_var=time_dimension.CumulVar(index)
previous_index = index
index = assignment.Value(routing.NextVar(index))
route_cost += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
route_distance+=assignment.Value(distance_var)
route_time+=assignment.Value(time_var)
plan_output += '{}\n'.format(manager.IndexToNode(index))
plan_output += 'Cost of the route: {0}\nDistance of the route: {1}m\nTime of route: {2}\n'.format(
route_cost,
route_distance,
route_time)
print(plan_output)
total_cost += route_cost
total_time+=route_time
total_distance+=route_distance
print('Total Cost of all routes: {}\nTotal Distance of all routes: {}\nTotal Time of all routes: {}\n'.format(total_cost,total_distance,total_time))
def get_routes(manager, routing, solution, num_routes):
"""Get vehicle routes from a solution and store them in an array."""
# Get vehicle routes and store them in a two dimensional array whose
# i,j entry is the jth location visited by vehicle i along its route.
routes = []
for route_nbr in range(num_routes):
index = routing.Start(route_nbr)
route = [manager.IndexToNode(index)]
while not routing.IsEnd(index):
index = solution.Value(routing.NextVar(index))
route.append(manager.IndexToNode(index))
routes.append(route)
return routes
def main():
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['cost_matrix']), data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def cost_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['cost_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(cost_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Cost constraint.
routing.AddDimension(
transit_callback_index,
0, # no slack
3000, # vehicle maximum travel distance
False, # start cumul to zero
'Cost')
cost_dimension = routing.GetDimensionOrDie('Cost')
cost_dimension.SetGlobalSpanCostCoefficient(1000)
#Add Distance constraint.
def distance_callback(from_index,to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix'][from_node][to_node]
distance_callback_index=routing.RegisterTransitCallback(distance_callback)
routing.AddDimension(
distance_callback_index,
0,
3000,
False,
'Distance')
distance_dimension=routing.GetDimensionOrDie('Distance')
#Add Time constraint.
def time_callback(from_index,to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['time_matrix'][from_node][to_node]
time_callback_index=routing.RegisterTransitCallback(time_callback)
routing.AddDimension(
time_callback_index,
0,
300,
False,
'Time')
time_dimension=routing.GetDimensionOrDie('Time')
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.solution_limit = 100
search_parameters.time_limit.seconds = 3
# Solve the problem.
assignment = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if assignment:
print_solution(data, manager, routing, assignment)
routes = get_routes(manager, routing, assignment, data['num_vehicles'])
# Display the routes.
for i, route in enumerate(routes):
print('Route', i, route)
if __name__ == '__main__':
main()
None could mean that it did not find a solution. Most likely your limits are too low by increasing the limits, it works fine. but for better understanding, it's better to check solver status. time limit errors mostly refer to the low limitations. in this example we have many value more than 300 in time matrix but the maximum time for every vehicle is 300.so there is not a feasible solution for this problem.