0

我有一个使用 Google 的 OR-Tools 在 Python 中实现的有效车辆路由问题解决方案。我有一个包含 16 个位置的时间矩阵、每个位置的时间窗口以及删除每个位置的惩罚。所有值都以秒为单位。我有意只用一辆车来解决这个问题（主要是解决旅行销售员问题）。只要需要，我允许车辆在任何位置等待。我为某些位置设置了极高的丢弃惩罚，因为我不希望它们被丢弃。

时间矩阵中表示的每个位置都会有一个时间窗口，它表示从一天开始的时间（28800 相当于上午 8:00，64800 相当于下午 6:00，等等）我设置上限最大值为 64800，因为我希望车辆在下午 6:00 之前完成。

我已将矩阵中的第一个位置指定为起始位置。
现在，我希望矩阵中的第二个位置成为结束位置。

我为此参考了OR-Tools 文档，但没有成功。我还在Stack Overflow 上发现了一个类似的问题，但没有找到任何特别有用的回答。

下面是我的源代码 - 它运行成功，但确实使用矩阵中的第二个位置作为它创建的解决方案中的结束位置。

来源

from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

Matrix = [
  [0, 0, 550, 743, 790, 606, 810, 684, 1500, 101, 1001, 722, 533, 574, 1126, 713],
  [0, 0, 550, 743, 790, 606, 810, 684, 1500, 101, 1001, 722, 533, 574, 1126, 713],
  [530, 530, 0, 609, 953, 620, 676, 550, 1544, 598, 875, 443, 489, 737, 1114, 914],
  [622, 622, 475, 0, 962, 570, 453, 144, 1695, 585, 1073, 641, 738, 745, 966, 922],
  [760, 760, 1014, 1147, 0, 1018, 1208, 1088, 1029, 780, 1375, 1180, 976, 609, 1293, 450],
  [629, 629, 621, 716, 989, 0, 715, 706, 1654, 516, 1219, 787, 734, 728, 1247, 650],
  [867, 867, 720, 567, 1109, 653, 0, 392, 1330, 830, 1318, 886, 983, 990, 731, 1092],
  [671, 671, 524, 213, 1011, 619, 395, 0, 1724, 634, 1122, 690, 788, 795, 867, 971],
  [1372, 1372, 1549, 1758, 1030, 1593, 1358, 1731, 0, 1392, 1987, 1714, 1588, 1221, 1443, 1101],
  [132, 132, 615, 764, 688, 545, 830, 704, 1398, 0, 990, 787, 547, 472, 1126, 612],
  [930, 930, 960, 1198, 1318, 1209, 1265, 1138, 2028, 1031, 0, 526, 866, 1078, 1703, 1272],
  [759, 759, 549, 786, 1130, 797, 853, 727, 1721, 718, 556, 0, 579, 914, 1291, 1091],
  [437, 437, 541, 836, 887, 764, 902, 776, 1597, 538, 877, 576, 0, 671, 1340, 811],
  [621, 621, 880, 1013, 486, 926, 1079, 953, 1196, 640, 1005, 1046, 837, 0, 1259, 441],
  [1608, 1608, 1517, 1654, 1547, 1562, 1088, 1480, 1610, 1484, 2115, 1683, 1794, 1556, 0, 1436],
  [515, 515, 769, 902, 373, 773, 969, 842, 1078, 534, 1130, 935, 731, 364, 1140, 0]
]

Windows = [[28800, 28800], [64800, 64800], [43200, 43200], [50400, 50400], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200], [21600, 79200]]

Durations = [0, 0, 1800, 3600, 3600, 7200, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800]

Penalties = [100000, 100000, 576460752303423487, 576460752303423487, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000]

# 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(Matrix)):
  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)

result = {
  'Dropped': None,
  'Schedule': None
}

# Display dropped nodes.
dropped = []
for node in range(routing.Size()):
  if routing.IsStart(node) or routing.IsEnd(node):
    continue
  if solution.Value(routing.NextVar(node)) == node:
    dropped.append(manager.IndexToNode(node))
result['Dropped'] = dropped

# Return the solution the problem.
schedule = []
time = 0
index = routing.Start(0)
while not routing.IsEnd(index):
  time = time_dimension.CumulVar(index)
  schedule.append([manager.IndexToNode(index), solution.Min(time),solution.Max(time)])
  index = solution.Value(routing.NextVar(index))
time = time_dimension.CumulVar(index)
schedule.append([manager.IndexToNode(index), solution.Min(time),solution.Max(time)])
result['Schedule'] = schedule
print(result)

输出

{'Dropped': [4, 5], 'Schedule': [[0, 28800, 28800], [9, 28901, 29249], [13, 31173, 31521], [15, 33414, 33762], [8, 36292, 36640], [14, 39535, 39883], [2, 43200, 43200], [6, 45676, 46195], [7, 47868, 48387], [3, 50400, 50400], [11, 54641, 57541], [10, 56997, 59897], [12, 59663, 62563], [1, 64800, 64800], [0, 64800, 64800]]}

我的理解是需要使用 RoutingIndexManager 进行主要更改。
就像 Google OR-Tools 文档似乎表明的那样，我尝试了以下更改：

manager = pywrapcp.RoutingIndexManager(len(Matrix),1,0)

到

manager = pywrapcp.RoutingIndexManager(len(Matrix),1,[0],[1])

但这会导致错误：

WARNING: Logging before InitGoogleLogging() is written to STDERR
F0820 15:13:16.748222 62401984 routing.cc:1433] Check failed: kUnassigned != indices[i] (-1 vs. -1) 
*** Check failure stack trace: ***

我在使用 OR Tools 时是否有任何明显的错误？我很乐意回答任何问题。任何帮助将不胜感激！谢谢！

4

1 回答 1

2

我在OR-Tools Google Groups 论坛中收到了这个问题的答案。

首先，正确更改管理器构造函数代码。

    # Create the routing index manager.
[-] manager = pywrapcp.RoutingIndexManager(len(Matrix), 1, 0)
[+] manager = pywrapcp.RoutingIndexManager(len(Matrix), 1, [0], [1])

其次，您不能在析取中指定开始或结束节点：

    # Allow to drop nodes.
[-] for node in range(1, len(Matrix)):
[+] for node in range(2, len(Matrix)):
      routing.AddDisjunction([manager.NodeToIndex(node)], Penalties[node])

第三，您不能NodeToIndex(node_index)在开始或结束节点上使用，因为它并不总是双射。

    # Add time window constraints for each location except start and end location.
    for location_idx, time_window in enumerate(Windows):
[-]   if location_idx == 0:
[+]   if location_idx == 0 or location_idx == 1:
        continue
      index = manager.NodeToIndex(location_idx)
      time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

最后，一定要在结束位置设置一个时间窗口：

    index = routing.Start(0)
    time_dimension.CumulVar(index).SetRange(Windows[0][0],Windows[0][1])
[+] index = routing.End(0)
[+] time_dimension.CumulVar(index).SetRange(Windows[1][0],Windows[1][1])
于 2020-08-21T14:29:51.747 回答