如何在 Google OR-Tools 中指定路线的结束位置？

Question

我有一个有效的车辆路径问题解决方案，它是在 Python 中使用 Google 的 OR-Tools 实现的。我有一个包含 16 个位置的时间矩阵、每个位置的时间窗口以及丢弃每个位置的惩罚。所有值都以秒为单位。我有意只用一辆车解决这个问题（实质上是解决旅行推销员问题）。只要需要，我允许车辆在任何地点等待。我已将某些位置的掉落惩罚设置得非常高，因为我不想让它们掉落。

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

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

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

输出

{'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 工具时是否存在任何明显的错误？我很乐意回答任何问题。任何帮助将不胜感激！谢谢你！

Answer 1

首先，正确更改管理器构造函数代码。    # 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])