algorithm - 通过用户定义点的 TSP

Question

我有一些点，并且有一些点的子集，标记为“静态”。所以我需要解决 TSP，这将创建最佳路径，包括静态位置的标记点。我该如何解决？

可能我的问题可以通过另一种方式解决：点有两个主要特征 - 彼此之间的距离和时间，其中推销员必须在点。是否有一些问题可以解决这个物流任务？

UPD我不明白，非静态点的TSP如何与静态点的TSP合并？

Answer 1

TSP基本上有三种方法：

1. 蛮力
2. 启发式
3. 近似

对于少量节点，使用蛮力可能是一种选择。它涉及生成所有(n-1)!排列并仅计算它们的长度。适应您的问题，您所需要更改的只是生成可能的往返行程的算法，以排除静态点不在其指定位置的那些。

使用启发式方法（例如模拟退火），您可以为更大的问题计算 TSP，但不能保证完美的往返，只能保证好的往返。这些通常采用现有解决方案并从中得出随机不同的解决方案（或多个解决方案）。适应您的问题，如果派生解决方案违反了静态点位于其指定位置的要求，您只需丢弃派生解决方案。

第三种变体使用在多项式时间内为您提供往返的算法，例如沿着最小生成树行走、向一个方向扫过或贪婪地遍历它们。这些提供了良好的时机，但在权衡由此产生的往返质量。我不清楚如何使这些适应需要某些点位于某个位置的解决方案。由于它们的简单性，它们不容易适应这些额外的要求。

Answer 2

如果我正确理解您的问题，这只是由您的静态、非静态位置和距离/时间矩阵定义的另一个旅行推销员问题。如果您的起源问题非常大，那么首先（并且只解决一次）解决起源问题的 TSP 可能是有意义的。产生的解决方案可用于指定新的初始解决方案，考虑您的“非静态”或用户定义的位置，例如，只需通过简单的最佳插入。然后，您可以使用例如由 Lin-Kernighan ( http://en.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic ) 开发和应用的 k-opt 启发式算法来改进这个初始解决方案。
如果您的起源问题很小，只需解决另一个 TSP（考虑您的“静态”和“非静态”位置）。