1

TLDR 版本：最重要的问题是，在 TSP 问题中，不是找到最短的哈密顿循环，而是找到最长 X 长度的最佳路径（我想是访问最多节点的路径）的好方法，一个固定的起点。

完整版本：

我对涉及 TSP 的问题的一些想法感兴趣。首先，一个现实世界的 TSP 问题示例是，当您有 N 个要访问的地理位置，并且您需要一条最佳路线（或接近最佳路线）的行车路线来访问所有地点，无论是往返还是从 A 到 Z。有一个不错的 JS在http://www.gebweb.net/optimap/上实现此功能，在http://code.google.com/p/google-maps-tsp-solver/上提供 JS TSP 求解器。

现在考虑您有 N = 100 - 1000+ 个位置。那时，您无法使用任何合理的时间/资源来计算路线，但即使有可能，这对于大多数现实世界的场景来说都不是那么有用。假设您选择了一个固定的起点，并基于此，您希望从这 1000 多个位置生成适合（相对较小）最大约束的最佳子路线（例如，可以在 1 天或 1 天内覆盖的路线星期）。如何近乎实时地解决这个问题？到目前为止我的想法：

  1. 从起点构建持续时间矩阵（此步骤即使在几千个点上也是可行的）并选择最接近起点的一小部分点。理想情况下，这个子集应该足够大，完全访问它肯定 > 最大约束，但小到足以快速处理，至少使用启发式算法。

  2. 考虑到步骤 1 中选择的位置，找到一条最佳路线。但是，我需要满足最大约束的最佳路线，而不是访问该集合中所有点的路线，因此它不应该访问所有点（它可以访问所有点，但那将是边缘情况）。我特别不确定如何以有效的方式解决这个问题？

任何链接或想法表示赞赏，尤其是第 2 点。

免责声明：当然，问题的核心与语言无关，我使用 JS/Google 地图作为现实世界应用程序的示例。

4

1 回答 1

1

好的，这是我用伪代码编写的解决方案草图。您需要了解优先队列

Define a data structure Route {
  the route taken so far, 
  and can give the score (nodes visited)
  the distance traveled
  and the remaining nodes allowed
  the current location.
}

Define a Priority Queue of Routes which sorts on distance traveled.
Define a SortedSet of Routes which sorts on score called solutions.

Add a Route of Length 0, at the depot to the priority queue.
Loop until the head of the priority queue is greater than MAX
   Route r = take the head of the priority queue.
   for each potential remaining node n in r, 
     (in increasing order of distance from the current location)
      child = a new route of r with n appended
      if child distance < max, append to priority queue, otherwise break
   if no children were appended add r to solutions

这有效地以合理的内存效率方式对解决方案空间进行了广度优先搜索。此外，如果它太慢，那么在遍历所有子节点时，您可以通过仅采用 N 个最近邻来加速算法，其中 N 是可配置的。您可能会错过最佳解决方案，但在大多数情况下它应该是合理的。

于 2010-08-19T09:26:41.133 回答