提问人：BRaabe99 提问时间：9/4/2023 最后编辑：Laurent PerronBRaabe99 更新时间：9/25/2023 访问量：57
TSP with CP-SAT：如何在特定时间设置某些节点访问次数
TSP with CP-SAT: How to set certain node-visits at specific time
问：
我正在用 CP-SAT 解决 TSP，如 https://github.com/google/or-tools/blob/master/examples/python/tsp_sat.py 所示，但我有一些我无法制定的约束：
- 我在特定节点上有一些“固定”访问，例如，我需要访问节点 15 作为第四次访问的注释。如何制定此约束？
- 另外，我想在特定时间点之前访问一些节点，例如，我想最迟访问节点 9 作为第五个访问的节点。
我不确定如何获取特定节点的时间点来检查这些约束，因为决策变量仅声明从节点 i 到节点 j 的访问。
我尝试像 https://github.com/google/or-tools/issues/590 一样使用时间戳实现 CP-SAT TSP 问题，但它的性能不佳（42 个节点为 ~2 小时，但在我的实际示例中我必须为 ~150 个节点提供服务）。
答：
0赞
CaptainTrunky
9/4/2023
#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)
基本上，它告诉我们必须选择一个城市的入站弧线，因此，我们强制要求在这个特定的时间戳访问该城市。ii
对于此类问题，我只知道几种改进运行时的方法：
- 减少决策变量的数量。也许你对你的问题有一些额外的了解，所以你可以将一些自由变量设置为特定的值？时序约束就是这样的限制之一。也许有一些更长且不可行的路径或一些模式，您可以立即排除？例如，如果选择了城市
A，则从未到达城市B - 是否有可能贪婪地将较大的问题拆分为一组较小的子问题？当然，您将无法找到全局最优值，但也许它已经足够好了？其他方法可能是使用假设 - 你建议一个求解器，该解决方案可能看起来像某种东西，你想测试这个假设
- 引入越来越多的约束。同样，也许您有一些领域知识，可以将某些特定情况排除在搜索空间之外？你的约束有一些上限/下限吗？
幸运的是，这些问题涉及大量的专业知识、运气和直觉，很多时候它更多地是关于艺术而不是科学。
评论