algorithm - 多 TSP 有一个转折

Question

几周前我遇到了一个问题，我实际上将其分解为旅行商问题的变体。曲折是:

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

很明显，这个问题是NP问题。我想知道是否可以修改任何好的 TSP 近似值来解决这个问题？

Answer 1

您也许可以使用一些运筹学软件来解决您的问题，例如Coin-OR ，原因是将新的约束/目标添加到 OR 约束/线性/整数/等编程求解器通常比添加新约束/目标更容易。用 C 或 Fortran 或其他语言编写的专用 TSP 求解器(您不太可能找到一些 C/Fortran 代码来解决您的精确问题)。 Here is a tutorial on how to code a Tabu search to solve the basic TSP using Coin-OR .此外，here is an article on modeling the time-dependent TSP (这篇文章使用分支定界来解决可能不适合您的问题的问题，因为它不会扩展到一百个左右的城市，但该模型应该转移到像 Coin-OR 这样的近似求解器) .

为了说明有多位销售员，您可能需要研究图形分区以在不同的销售员之间划分城市，例如 here is a fast online graph partitioning algorithm .优点是，一旦您对图表进行了分区，就可以减少甚至消除不同销售人员之间的同步。