algorithm - 多 TSP 扭曲

Question

几周前，我遇到了一个问题，我几乎可以分解为旅行商问题的变体。曲折是：

有多个推销员。城市列表在动态增加（如实时输入）每个城市仅在有限的时间内完全盈利，如在一定时间后城市将返回较少的奖励并且有一个总体时间限制

显然，这个问题是NP。我想知道是否有任何好的 TSP 近似值可以被修改以适应这个问题？

Answer 1

您可能可以使用一些运筹学软件来解决您的问题，例如Coin-OR，原因是通常更容易将新的约束/目标添加到 OR 约束/线性/整数/等编程求解器而不是例如专门的用 C 或 Fortran 或其他语言编写的 TSP 求解器（您不太可能找到一些 C/Fortran 代码来解决您的精确问题）。 这是有关如何编写禁忌搜索代码以使用 Coin-OR 解决基本 TSP 的教程。另外，这里有一篇关于对时间相关的 TSP 建模的文章（本文使用分支定界来解决可能不适合您的问题的问题，因为它的规模不会超过一百个城市左右，但该模型应该延续到像 Coin-OR 这样的近似求解器） .

考虑到有多个推销员，您可能需要研究图划分以在不同推销员之间划分城市，例如这里是一个快速的在线图划分算法。这样做的好处是，一旦您对图表进行了分区，您就可以减少甚至消除不同销售人员之间的同步。