TSP 与 CP-SAT：如何在特定时间设置某些节点访问

Question

我正在使用 CP-SAT 求解 TSP，如 https://github.com/google/or-tools/blob/master/examples/python/tsp_sat.py 所示，但我有一些限制，但我没有能够制定：

1. 我在特定节点有一些“固定”访问，例如我需要访问节点 15 作为第四个访问的注释。我该如何制定这个约束？
2. 另外，我想在特定时间点之前访问一些节点，例如我想最晚访问节点 9，作为第五个访问的节点。

我不确定如何获取特定节点的时间点来检查这些约束，因为决策变量仅说明从节点 i 到节点 j 的访问。

我尝试实现带有时间戳的 CP-SAT TSP 问题，如 https://github.com/google/or-tools/issues/590，但它的性能不佳（42 个节点约为 2 小时，但我在我的实际示例中必须服务约 150 个节点）。

Answer 1

我认为在您的情况下，运行时间的增加可能是可以预料的——因为您有额外的排序限制，所以与 Google OR 示例相比，您的问题要困难得多。

您最初的问题可以说是 2D - 它只涉及城市之间的距离和连接，而您的问题是 3D - 您有额外的及时订购要求。

此链接准确定义了一个 3D 问题 - 连接加上

t

表示时间。如果您希望代理在特定时间访问特定城市，则需要额外的约束：

stops = [10, 15, ...]
for i in range(0, num_cities):
    t = stops[i]
    solver.Add(solver.Sum(x[i,j,t] for j in range(0, num_cities)) == 1)

基本上，它告诉我们必须选择城市

i

的入站弧线之一，因此，我们强制在该特定时间戳访问该城市

i

。

我只知道改善此类问题运行时间的几种方法：

• 减少决策变量的数量。也许您对您的问题有一些额外的了解，因此您可以将一些自由变量设置为特定值？您的时间限制就是此类限制之一。也许有一些更长且不可行的路径或一些模式，您可以立即排除？例如。 如果选择了城市

  A

  ，则永远不会到达城市

  B

• 是否可以将较大的问题贪婪地分解为一组较小的子问题？当然，您将无法找到全局最优值，但也许它已经足够好了？其他方法可以使用假设 - 您建议一个求解器，该解决方案可能看起来像某种东西，并且您想测试这个假设
• 引入越来越多的限制。同样，也许您拥有一些领域知识，可以从搜索空间中排除某些特定情况？您的约束有上限/下限吗？

（不幸）幸运的是，此类问题涉及大量专业知识、运气和直觉，通常更多的是关于艺术而不是科学。