OR-Tools VRP 求解器表现不佳
OR-Tools VRP Solver Under-performing
我正在尝试测试 or-tools 路由求解器来解决基本的 TSP 问题，但我无法使其正常工作。在问题被发送到路由求解器之前，我有一个距离矩阵和一堆贪婪的解决方案。例如，我使用底部共享的 this website 中的示例 python 代码设置了一个问题。
在示例中，我有 10 个具有非对称距离矩阵的城市。最佳贪心解（从不同城市开始的最近优先）作为初始解存储在 data 中。我有两个函数：solve_from_initial_route() 和 solve_from_scratch() 可以在有或没有初始解决方案信息的情况下解决相同的问题，并产生相同的结果。求解器在这里表现出一些令人惊讶的行为：
- 函数
solve_from_initial_route() 产生初始贪婪解作为最终解并立即退出（4-5 毫秒），没有任何尝试求解和生成 运行 时间日志（即使搜索日志记录是已启用）。
- 函数
solve_from_scratch() 也产生了与最终解决方案相同的贪婪解决方案，并且确实产生了 运行 时间日志，显示它已经评估了很多选项。但有趣的是，无论我 运行 解算多久，解总是一样的。求解器在某种程度上并不聪明，并且总是在评估更糟糕的选择。另一方面，针对同一问题的遗传算法 运行 在 1 秒内产生了比贪心初始解更好的解！
- 我还尝试了所有其他本地搜索选项以及模拟退火等随机算法，您可能希望在不同的时间限制内看到结果的一些变化，但这种情况不会发生，解决方案始终相同作为最初的贪心解！
- 此外，路由求解器继续运行，即使它在技术上应该已经评估了所有组合。 10个城市一共有10个！ = 总共要评估 3628800 个序列，但具有比求解器保持 运行ning 更高的限制，直到它达到搜索限制而不是实际问题限制。
可能是我没有正确设置所有选项，或者我的代码中遗漏了某些内容。如果能帮助求解器按预期工作，我将不胜感激。
谢谢！
!pip install ortools
from __future__ import print_function
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['distance_matrix'] = [
[0, 227543, 133934, 200896, 106495, 163222, 75896, 139494, 46460, 102942],
[135873, 0, 15673, 174874, 80474, 197318, 109993, 232377, 139343, 46665],
[229482, 15673, 0, 88692, 183092, 125214, 214714, 153718, 247723, 140274],
[108503, 174151, 80542, 0, 15674, 169948, 82622, 205007, 111973, 49550],
[195308, 94193, 167348, 21174, 0, 105716, 169428, 134221, 198779, 136356],
[77835, 203602, 109992, 176954, 82554, 0, 15660, 174340, 81306, 79000],
[172835, 119784, 213500, 94785, 189185, 21172, 0, 96019, 190024, 174000],
[48413, 232967, 139358, 206320, 111919, 168647, 81321, 0, 15662, 108366],
[141422, 153773, 247490, 128774, 204928, 101504, 174329, 15662, 0, 201374],
[104492, 139205, 45595, 143494, 49093, 165938, 78612, 200997, 107963, 0]
]
data['initial_routes'] = [
[8, 7, 6, 5, 4, 3, 2, 1]
]
data['num_vehicles'] = 1
data['start_idx'] = [0]
data['end_idx'] = [9]
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
max_route_distance = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_distance = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id)
plan_output += '{}\n'.format(manager.IndexToNode(index))
plan_output += 'Distance of the route: {}m\n'.format(route_distance)
print(plan_output)
max_route_distance = max(route_distance, max_route_distance)
print('Maximum of the route distances: {}m'.format(max_route_distance))
def solve_from_initial_route():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'], data['start_idx'],
data['end_idx'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def distance_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['distance_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
initial_solution = routing.ReadAssignmentFromRoutes(data['initial_routes'],True)
print('Initial solution:')
print_solution(data, manager, routing, initial_solution)
# Set default search parameters.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 2
search_parameters.lns_time_limit.seconds = 1
search_parameters.solution_limit = 15000
search_parameters.log_search = True
# Solve the problem.
solution = routing.SolveFromAssignmentWithParameters(initial_solution, search_parameters)
# Print solution on console.
if solution:
print('Solution after search:')
print_solution(data, manager, routing, solution)
def solve_from_scratch():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'], data['start_idx'],
data['end_idx'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def distance_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['distance_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Set default search parameters.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 2
search_parameters.lns_time_limit.seconds = 1
search_parameters.solution_limit = 150000
search_parameters.log_search = True
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print('Solution after search:')
print_solution(data, manager, routing, solution)
if __name__ == '__main__':
#solve_from_initial_route()
solve_from_scratch()
如果我运行你的代码，它会打印
Solution after search:
Route for vehicle 0:
0 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 9
Distance of the route: 411223m
这是使用所有节点从 0 到 9 的最佳路径（我使用 tsp_sat 代码检查过）。而且不到1毫秒就被发现了
现在，在日志部分，
Solution #5265 (783010, objective minimum = 411223, objective maximum = 1103173, time = 1998 ms, branches = 26227, failures = 14386, depth = 33, OrOpt<3>, neighbors = 351904, filtered neighbors = 5265, accepted neighbors = 5265, memory used = 35.63 MB, limit = 99%)
GLS对成本函数进行了惩罚，所以实际值783010不是真正的距离，而是惩罚后的距离
现在，solve_from_initial_route() 命中 known bug
这里是正确的求解代码
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'],
data['start_idx'],
data['end_idx'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def distance_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['distance_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Set default search parameters.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 1
search_parameters.lns_time_limit.seconds = 1
search_parameters.solution_limit = 15000
search_parameters.log_search = True
routing.CloseModelWithParameters(search_parameters)
initial_solution = routing.ReadAssignmentFromRoutes(data['initial_routes'],
True)
print('Initial solution:')
print_solution(data, manager, routing, initial_solution)
# Solve the problem.
solution = routing.SolveFromAssignmentWithParameters(initial_solution, search_parameters)
这样就正确初始化了参数，搜索找到了最优解。
我正在尝试测试 or-tools 路由求解器来解决基本的 TSP 问题，但我无法使其正常工作。在问题被发送到路由求解器之前，我有一个距离矩阵和一堆贪婪的解决方案。例如，我使用底部共享的 this website 中的示例 python 代码设置了一个问题。
在示例中，我有 10 个具有非对称距离矩阵的城市。最佳贪心解（从不同城市开始的最近优先）作为初始解存储在 data 中。我有两个函数：solve_from_initial_route() 和 solve_from_scratch() 可以在有或没有初始解决方案信息的情况下解决相同的问题，并产生相同的结果。求解器在这里表现出一些令人惊讶的行为：
- 函数
solve_from_initial_route()产生初始贪婪解作为最终解并立即退出（4-5 毫秒），没有任何尝试求解和生成 运行 时间日志（即使搜索日志记录是已启用）。 - 函数
solve_from_scratch()也产生了与最终解决方案相同的贪婪解决方案，并且确实产生了 运行 时间日志，显示它已经评估了很多选项。但有趣的是，无论我 运行 解算多久，解总是一样的。求解器在某种程度上并不聪明，并且总是在评估更糟糕的选择。另一方面，针对同一问题的遗传算法 运行 在 1 秒内产生了比贪心初始解更好的解！ - 我还尝试了所有其他本地搜索选项以及模拟退火等随机算法，您可能希望在不同的时间限制内看到结果的一些变化，但这种情况不会发生，解决方案始终相同作为最初的贪心解！
- 此外，路由求解器继续运行，即使它在技术上应该已经评估了所有组合。 10个城市一共有10个！ = 总共要评估 3628800 个序列，但具有比求解器保持 运行ning 更高的限制，直到它达到搜索限制而不是实际问题限制。
可能是我没有正确设置所有选项，或者我的代码中遗漏了某些内容。如果能帮助求解器按预期工作，我将不胜感激。
谢谢！
!pip install ortools
from __future__ import print_function
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['distance_matrix'] = [
[0, 227543, 133934, 200896, 106495, 163222, 75896, 139494, 46460, 102942],
[135873, 0, 15673, 174874, 80474, 197318, 109993, 232377, 139343, 46665],
[229482, 15673, 0, 88692, 183092, 125214, 214714, 153718, 247723, 140274],
[108503, 174151, 80542, 0, 15674, 169948, 82622, 205007, 111973, 49550],
[195308, 94193, 167348, 21174, 0, 105716, 169428, 134221, 198779, 136356],
[77835, 203602, 109992, 176954, 82554, 0, 15660, 174340, 81306, 79000],
[172835, 119784, 213500, 94785, 189185, 21172, 0, 96019, 190024, 174000],
[48413, 232967, 139358, 206320, 111919, 168647, 81321, 0, 15662, 108366],
[141422, 153773, 247490, 128774, 204928, 101504, 174329, 15662, 0, 201374],
[104492, 139205, 45595, 143494, 49093, 165938, 78612, 200997, 107963, 0]
]
data['initial_routes'] = [
[8, 7, 6, 5, 4, 3, 2, 1]
]
data['num_vehicles'] = 1
data['start_idx'] = [0]
data['end_idx'] = [9]
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
max_route_distance = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_distance = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id)
plan_output += '{}\n'.format(manager.IndexToNode(index))
plan_output += 'Distance of the route: {}m\n'.format(route_distance)
print(plan_output)
max_route_distance = max(route_distance, max_route_distance)
print('Maximum of the route distances: {}m'.format(max_route_distance))
def solve_from_initial_route():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'], data['start_idx'],
data['end_idx'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def distance_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['distance_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
initial_solution = routing.ReadAssignmentFromRoutes(data['initial_routes'],True)
print('Initial solution:')
print_solution(data, manager, routing, initial_solution)
# Set default search parameters.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 2
search_parameters.lns_time_limit.seconds = 1
search_parameters.solution_limit = 15000
search_parameters.log_search = True
# Solve the problem.
solution = routing.SolveFromAssignmentWithParameters(initial_solution, search_parameters)
# Print solution on console.
if solution:
print('Solution after search:')
print_solution(data, manager, routing, solution)
def solve_from_scratch():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'], data['start_idx'],
data['end_idx'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def distance_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['distance_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Set default search parameters.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 2
search_parameters.lns_time_limit.seconds = 1
search_parameters.solution_limit = 150000
search_parameters.log_search = True
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print('Solution after search:')
print_solution(data, manager, routing, solution)
if __name__ == '__main__':
#solve_from_initial_route()
solve_from_scratch()
如果我运行你的代码，它会打印
Solution after search:
Route for vehicle 0:
0 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 9
Distance of the route: 411223m
这是使用所有节点从 0 到 9 的最佳路径（我使用 tsp_sat 代码检查过）。而且不到1毫秒就被发现了
现在，在日志部分，
Solution #5265 (783010, objective minimum = 411223, objective maximum = 1103173, time = 1998 ms, branches = 26227, failures = 14386, depth = 33, OrOpt<3>, neighbors = 351904, filtered neighbors = 5265, accepted neighbors = 5265, memory used = 35.63 MB, limit = 99%)
GLS对成本函数进行了惩罚，所以实际值783010不是真正的距离，而是惩罚后的距离
现在，solve_from_initial_route() 命中 known bug
这里是正确的求解代码
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'],
data['start_idx'],
data['end_idx'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def distance_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['distance_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Set default search parameters.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 1
search_parameters.lns_time_limit.seconds = 1
search_parameters.solution_limit = 15000
search_parameters.log_search = True
routing.CloseModelWithParameters(search_parameters)
initial_solution = routing.ReadAssignmentFromRoutes(data['initial_routes'],
True)
print('Initial solution:')
print_solution(data, manager, routing, initial_solution)
# Solve the problem.
solution = routing.SolveFromAssignmentWithParameters(initial_solution, search_parameters)
这样就正确初始化了参数，搜索找到了最优解。