我如何使用 Google OR 工具来添加析取、设置惩罚并防止某些位置在 VRPTW 中被丢弃？
How do I use Google OR Tools to add disjunctions, set penalties, and prevent certain locations from being dropped in VRPTW?
我有一个有效的车辆路径问题（时间 Windows）解决方案，使用 Google 的 OR 工具 python 库实现。我有一个包含 15 个位置的时间矩阵，每个位置的时间 windows。我还将访问每个位置的持续时间计入每次访问的成本。所有值均以秒为单位。我有意只用一辆车解决这个问题（本质上是解决旅行推销员问题）。
如果它们阻止创建有效的解决方案，我不会尝试添加从解决方案中删除位置的功能。现在，如果我将每次访问的 duration 设置为 3600 秒，将无法访问所有 15 个位置。但是，如果我改为将每次访问的持续时间设置为 900 秒，那么所有 15 个位置的解决方案都是可能的。我想添加一个析取以允许创建具有这些大持续时间的解决方案，而不是失败，只需从解决方案中删除一个位置。
我有一些位置不想从解决方案中删除，因此我给了它们非常大的惩罚以确保它们不会被删除，而其他位置我指定了零惩罚。但是现在，所有 other 地点都被删除了，因为它们的罚款为零 - 我认为这是因为罚款低于运输成本，但我不完全确定这是否确实是这个原因。 我应该如何允许从解决方案中删除位置，但防止其他位置被删除？
目前我添加的唯一代码是：
# Allow to drop nodes.
for node in range(1, len(Penalties)):
routing.AddDisjunction([manager.NodeToIndex(node)], Penalties[node])
来源
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
Matrix = [
[0, 557, 763, 813, 618, 822, 700, 1527, 112, 1011, 734, 551, 604, 1156, 732], # Depot
[523, 0, 598, 934, 607, 658, 535, 1529, 589, 857, 424, 475, 725, 1107, 899], # 1 - Location
[631, 480, 0, 960, 570, 451, 135, 1698, 582, 1075, 642, 743, 751, 968, 925], # 2 - Location
[746, 1000, 1135, 0, 1168, 1186, 1071, 1012, 776, 1358, 1162, 947, 594, 1283, 426], # 3 - Location
[685, 627, 810, 990, 0, 712, 709, 1649, 550, 1221, 788, 726, 734, 1227, 653], # 4 - Location
[869, 718, 558, 1105, 650, 0, 384, 1328, 821, 1313, 880, 981, 989, 732, 993], # 5 - Location
[679, 528, 202, 1008, 618, 412, 0, 1740, 630, 1123, 690, 791, 799, 878, 973], # 6 - Location
[1378, 1553, 1766, 1031, 1595, 1355, 1731, 0, 1408, 1990, 1715, 1579, 1226, 1452, 1098], # 7 - Location
[149, 626, 762, 696, 556, 821, 698, 1410, 0, 999, 803, 536, 487, 1156, 614], # 8 - Location
[918, 943, 1184, 1296, 1193, 1244, 1121, 2010, 1030, 0, 509, 870, 1063, 1693, 1250], # 9 - Location
[763, 541, 782, 1118, 791, 842, 719, 1713, 719, 558, 0, 567, 909, 1291, 1083], # 10 - Location
[449, 543, 843, 887, 769, 902, 780, 1601, 561, 876, 573, 0, 678, 1352, 806], # 11 - Location
[628, 873, 1008, 491, 933, 1068, 945, 1205, 657, 1014, 1035, 825, 0, 1276, 444], # 12 - Location
[1343, 1247, 1367, 1270, 1289, 809, 1193, 1335, 1253, 1842, 1409, 1509, 1287, 0, 1158], # 13 - Location
[520, 774, 909, 385, 875, 1052, 845, 1078, 550, 1132, 936, 721, 368, 1149, 0] # 14 - Location
]
Windows = [
[28800, 28800], # Depot
[43200, 43200], # 1 - Location
[50400, 50400], # 2 - Location
[21600, 79200], # 3 - Location
[21600, 79200], # 4 - Location
[21600, 79200], # 5 - Location
[21600, 79200], # 6 - Location
[21600, 79200], # 7 - Location
[21600, 79200], # 8 - Location
[21600, 79200], # 9 - Location
[21600, 79200], # 10 - Location
[21600, 79200], # 11 - Location
[21600, 79200], # 12 - Location
[21600, 79200], # 13 - Location
[21600, 79200] # 14 - Location
]
Durations = [0, 1800, 3600, 3600, 7200, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800]
Penalties = [99999999, 99999999, 99999999, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# The inputs to RoutingIndexManager are:
# 1. The number of rows of the time matrix, which is the number of locations (including the depot).
# 2. The number of vehicles in the problem.
# 3. The node corresponding to the depot.
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(Matrix), 1, 0)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def transit_callback(from_index, to_index):
# Returns the travel time between the two nodes.
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return Matrix[from_node][to_node] + Durations[from_node]
transit_callback_index = routing.RegisterTransitCallback(transit_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Time Windows constraint.
routing.AddDimension(
transit_callback_index,
64800, # An upper bound for slack (the wait times at the locations).
64800, # An upper bound for the total time over each vehicle's route.
False, # Determine whether the cumulative variable is set to zero at the start of the vehicle's route.
'Time')
time_dimension = routing.GetDimensionOrDie('Time')
# Allow to drop nodes.
for node in range(1, len(Penalties)):
routing.AddDisjunction([manager.NodeToIndex(node)], Penalties[node])
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(Windows):
if location_idx == 0:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add time window constraints for each vehicle start node.
index = routing.Start(0)
time_dimension.CumulVar(index).SetRange(Windows[0][0],Windows[0][1])
# Instantiate route start and end times to produce feasible times.
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(0)))
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(0)))
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
# Setting local search metaheuristics:
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 5
search_parameters.log_search = False
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Display dropped nodes.
dropped_nodes = 'Dropped nodes:'
for node in range(routing.Size()):
if routing.IsStart(node) or routing.IsEnd(node):
continue
if solution.Value(routing.NextVar(node)) == node:
dropped_nodes += ' {}'.format(manager.IndexToNode(node))
print(dropped_nodes)
# Return the solution.
time = 0
index = routing.Start(0)
print('Solution:')
while not routing.IsEnd(index):
time = time_dimension.CumulVar(index)
print('{0} ({1},{2})'.format(manager.IndexToNode(index), solution.Min(time), solution.Max(time)))
index = solution.Value(routing.NextVar(index))
time = time_dimension.CumulVar(index)
print('{0} ({1},{2})'.format(manager.IndexToNode(index), solution.Min(time), solution.Max(time)))
输出
Dropped nodes: 3 4 5 6 7 8 9 10 11 12 13 14
Solution:
0 (28800,28800)
1 (43200,43200)
2 (50400,50400)
0 (54631,54631)
同样，如果我删除我添加的那 3 行代码，并将 Duration 数组中的所有值设置为等于 900 秒，则创建一个解决方案正好。但是当我增加持续时间时，无法创建解决方案。当我添加 Disjunction 并将所有惩罚设置为零时，解决方案会忽略除车站以外的所有位置。我在使用 OR 工具时是否存在任何明显的错误？任何帮助将不胜感激！
要使位置“强制”，您必须使用最大 int64 值 (0x7FFFFFFFFFFFFFF)，因为求解器不能溢出，它将禁止它删除该位置。
由于您使用时间矩阵来提供弧成本评估器，因此您应该将惩罚设置在 10k 左右，否则求解器有动力丢弃节点并支付成本而不是支付传输成本。
你所有的时间 window 范围应该在 [0, max dimension value] 内，在这里你将它设置为 64800 但你有一些时间 Windows 79200 作为上限，从求解器的角度来看，这会使问题不可行，因此您应该将时间维度上限设置为至少 79200 恕我直言。
我有一个有效的车辆路径问题（时间 Windows）解决方案，使用 Google 的 OR 工具 python 库实现。我有一个包含 15 个位置的时间矩阵，每个位置的时间 windows。我还将访问每个位置的持续时间计入每次访问的成本。所有值均以秒为单位。我有意只用一辆车解决这个问题（本质上是解决旅行推销员问题）。
如果它们阻止创建有效的解决方案，我不会尝试添加从解决方案中删除位置的功能。现在，如果我将每次访问的 duration 设置为 3600 秒，将无法访问所有 15 个位置。但是，如果我改为将每次访问的持续时间设置为 900 秒，那么所有 15 个位置的解决方案都是可能的。我想添加一个析取以允许创建具有这些大持续时间的解决方案，而不是失败，只需从解决方案中删除一个位置。
我有一些位置不想从解决方案中删除，因此我给了它们非常大的惩罚以确保它们不会被删除，而其他位置我指定了零惩罚。但是现在，所有 other 地点都被删除了，因为它们的罚款为零 - 我认为这是因为罚款低于运输成本，但我不完全确定这是否确实是这个原因。 我应该如何允许从解决方案中删除位置，但防止其他位置被删除？
目前我添加的唯一代码是：
# Allow to drop nodes.
for node in range(1, len(Penalties)):
routing.AddDisjunction([manager.NodeToIndex(node)], Penalties[node])
来源
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
Matrix = [
[0, 557, 763, 813, 618, 822, 700, 1527, 112, 1011, 734, 551, 604, 1156, 732], # Depot
[523, 0, 598, 934, 607, 658, 535, 1529, 589, 857, 424, 475, 725, 1107, 899], # 1 - Location
[631, 480, 0, 960, 570, 451, 135, 1698, 582, 1075, 642, 743, 751, 968, 925], # 2 - Location
[746, 1000, 1135, 0, 1168, 1186, 1071, 1012, 776, 1358, 1162, 947, 594, 1283, 426], # 3 - Location
[685, 627, 810, 990, 0, 712, 709, 1649, 550, 1221, 788, 726, 734, 1227, 653], # 4 - Location
[869, 718, 558, 1105, 650, 0, 384, 1328, 821, 1313, 880, 981, 989, 732, 993], # 5 - Location
[679, 528, 202, 1008, 618, 412, 0, 1740, 630, 1123, 690, 791, 799, 878, 973], # 6 - Location
[1378, 1553, 1766, 1031, 1595, 1355, 1731, 0, 1408, 1990, 1715, 1579, 1226, 1452, 1098], # 7 - Location
[149, 626, 762, 696, 556, 821, 698, 1410, 0, 999, 803, 536, 487, 1156, 614], # 8 - Location
[918, 943, 1184, 1296, 1193, 1244, 1121, 2010, 1030, 0, 509, 870, 1063, 1693, 1250], # 9 - Location
[763, 541, 782, 1118, 791, 842, 719, 1713, 719, 558, 0, 567, 909, 1291, 1083], # 10 - Location
[449, 543, 843, 887, 769, 902, 780, 1601, 561, 876, 573, 0, 678, 1352, 806], # 11 - Location
[628, 873, 1008, 491, 933, 1068, 945, 1205, 657, 1014, 1035, 825, 0, 1276, 444], # 12 - Location
[1343, 1247, 1367, 1270, 1289, 809, 1193, 1335, 1253, 1842, 1409, 1509, 1287, 0, 1158], # 13 - Location
[520, 774, 909, 385, 875, 1052, 845, 1078, 550, 1132, 936, 721, 368, 1149, 0] # 14 - Location
]
Windows = [
[28800, 28800], # Depot
[43200, 43200], # 1 - Location
[50400, 50400], # 2 - Location
[21600, 79200], # 3 - Location
[21600, 79200], # 4 - Location
[21600, 79200], # 5 - Location
[21600, 79200], # 6 - Location
[21600, 79200], # 7 - Location
[21600, 79200], # 8 - Location
[21600, 79200], # 9 - Location
[21600, 79200], # 10 - Location
[21600, 79200], # 11 - Location
[21600, 79200], # 12 - Location
[21600, 79200], # 13 - Location
[21600, 79200] # 14 - Location
]
Durations = [0, 1800, 3600, 3600, 7200, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800]
Penalties = [99999999, 99999999, 99999999, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# The inputs to RoutingIndexManager are:
# 1. The number of rows of the time matrix, which is the number of locations (including the depot).
# 2. The number of vehicles in the problem.
# 3. The node corresponding to the depot.
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(Matrix), 1, 0)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def transit_callback(from_index, to_index):
# Returns the travel time between the two nodes.
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return Matrix[from_node][to_node] + Durations[from_node]
transit_callback_index = routing.RegisterTransitCallback(transit_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Time Windows constraint.
routing.AddDimension(
transit_callback_index,
64800, # An upper bound for slack (the wait times at the locations).
64800, # An upper bound for the total time over each vehicle's route.
False, # Determine whether the cumulative variable is set to zero at the start of the vehicle's route.
'Time')
time_dimension = routing.GetDimensionOrDie('Time')
# Allow to drop nodes.
for node in range(1, len(Penalties)):
routing.AddDisjunction([manager.NodeToIndex(node)], Penalties[node])
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(Windows):
if location_idx == 0:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add time window constraints for each vehicle start node.
index = routing.Start(0)
time_dimension.CumulVar(index).SetRange(Windows[0][0],Windows[0][1])
# Instantiate route start and end times to produce feasible times.
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(0)))
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(0)))
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
# Setting local search metaheuristics:
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 5
search_parameters.log_search = False
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Display dropped nodes.
dropped_nodes = 'Dropped nodes:'
for node in range(routing.Size()):
if routing.IsStart(node) or routing.IsEnd(node):
continue
if solution.Value(routing.NextVar(node)) == node:
dropped_nodes += ' {}'.format(manager.IndexToNode(node))
print(dropped_nodes)
# Return the solution.
time = 0
index = routing.Start(0)
print('Solution:')
while not routing.IsEnd(index):
time = time_dimension.CumulVar(index)
print('{0} ({1},{2})'.format(manager.IndexToNode(index), solution.Min(time), solution.Max(time)))
index = solution.Value(routing.NextVar(index))
time = time_dimension.CumulVar(index)
print('{0} ({1},{2})'.format(manager.IndexToNode(index), solution.Min(time), solution.Max(time)))
输出
Dropped nodes: 3 4 5 6 7 8 9 10 11 12 13 14
Solution:
0 (28800,28800)
1 (43200,43200)
2 (50400,50400)
0 (54631,54631)
同样，如果我删除我添加的那 3 行代码，并将 Duration 数组中的所有值设置为等于 900 秒，则创建一个解决方案正好。但是当我增加持续时间时，无法创建解决方案。当我添加 Disjunction 并将所有惩罚设置为零时，解决方案会忽略除车站以外的所有位置。我在使用 OR 工具时是否存在任何明显的错误？任何帮助将不胜感激！
要使位置“强制”，您必须使用最大 int64 值 (
0x7FFFFFFFFFFFFFF)，因为求解器不能溢出，它将禁止它删除该位置。由于您使用时间矩阵来提供弧成本评估器，因此您应该将惩罚设置在 10k 左右，否则求解器有动力丢弃节点并支付成本而不是支付传输成本。
你所有的时间 window 范围应该在
[0, max dimension value]内，在这里你将它设置为64800但你有一些时间 Windows79200作为上限，从求解器的角度来看，这会使问题不可行，因此您应该将时间维度上限设置为至少79200恕我直言。