ortools vrp 没有给我任何解决方案
ortools vrp does not give me any solution
我想用 ORTools 解决车辆路径问题，距离和持续时间矩阵都会用到。
但问题是当我改变矩阵时，它不会再给我任何解决方案了！
有两组矩阵。对于注释矩阵有解决方案，但对于另一组，没有。你知道为什么会这样吗：
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 可能意味着它没有找到解决方案。很可能你的限制太低了
通过增加限制，它工作正常。
但为了更好地理解，最好检查求解器状态。时限错误多指时限低。
在这个例子中，我们在时间矩阵中有许多超过 300 的值，但每辆车的最大时间是 300.so 这个问题没有可行的解决方案。
我想用 ORTools 解决车辆路径问题，距离和持续时间矩阵都会用到。 但问题是当我改变矩阵时，它不会再给我任何解决方案了！ 有两组矩阵。对于注释矩阵有解决方案，但对于另一组，没有。你知道为什么会这样吗：
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 可能意味着它没有找到解决方案。很可能你的限制太低了 通过增加限制，它工作正常。 但为了更好地理解，最好检查求解器状态。时限错误多指时限低。 在这个例子中，我们在时间矩阵中有许多超过 300 的值，但每辆车的最大时间是 300.so 这个问题没有可行的解决方案。