如何使用 Google OR 工具添加析取、设置惩罚并防止某些位置在 VRPTW 中被删除？

Question

我有一个使用 Google 的 OR Tools python 库实现的有效车辆路由问题（带时间窗口）解决方案。我有一个包含 15 个位置的时间矩阵以及每个位置的时间窗口。我还将访问每个地点的持续时间纳入每次访问的费用中。所有值均以秒为单位。我有意只用一辆车来解决这个问题（本质上是解决旅行推销员问题）。

如果位置阻止创建有效的解决方案，我不会尝试添加从解决方案中删除位置的功能。现在，如果我将每次访问的持续时间设置为 3600 秒，则无法访问所有 15 个位置。但是，如果我将每次访问的持续时间设置为 900 秒，那么所有 15 个位置都可以找到解决方案。我想添加一个析取项，以允许在这些较长的持续时间内创建解决方案，并且只需从解决方案中删除一个位置即可避免失败。

我不想从解决方案中删除一些位置，因此我给了它们极大的惩罚以确保它们不会被删除，而其他位置我则指定为零的惩罚。但现在，所有其他地点都被放弃，因为它们的罚款为零 - 我认为这是因为罚款小于交通成本，但我不完全确定这是否确实是原因。我应该如何允许从解决方案中删除位置，但防止其他位置可删除？

现在我添加的唯一代码是：

# 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 秒，则可以很好地创建解决方案。但是当我增加持续时间时，无法创建解决方案。当我添加析取并将所有惩罚设置为零时，解决方案会忽略除仓库之外的每个位置。我在使用 OR Tools 时是否存在任何明显的错误？任何帮助将不胜感激！

Answer 1

1. 要使位置“强制”，您必须使用最大 int64 值 ( 0x7FFFFFFFFFFFFFF)，因为解算器无法溢出，它将禁止它删除此位置。

2. 由于您使用时间矩阵来提供弧成本评估器，因此您应该将惩罚设置为 10k 左右，否则求解器有动力放弃节点并支付成本而不是支付传输成本。

3. 您所有的时间窗口范围都应该在 中[0, max dimension value]，在这里您将其设置为64800但是您有一些时间窗口作为79200上限，这可能会使问题从求解器的角度来看不可行，因此您应该将时间维度上限设置为至少恕79200我直言。