异步旅行推销员子旅行的本地搜索启发式

Question

假设我想最小化一系列城市之间的旅行距离：

开始游览：S-1-2-3-4-5-E

最佳游览：S-5-1-2-3-4-E

游览必须从 S 开始，必须在 E 结束，但可以按任意顺序游览中间的城市。在我的用例中，S 和 E 之间的城市数将在 1 到 35 之间。

我目前使用的启发式是一个重复的二选一（以伪javascript显示）：

minStopSequence = ['S', 1, 2, 3, 4, 5, 'E'];
changed = true;
while (changed === true) {
  changed = false;
  for (i = 1; i < minStopSequence.length - 2; i++) {
    for (j = i + 1; j < minStopSequence.length - 1; j++) {
      newStopSequence = reverseTheMiddleSection(minStopSequence, i, j);
      newSegmentDur = getDuration(newStopSequence);
      if (newSegmentDur < minSegmentDur) {
        minSegmentDur = newSegmentDur;
        minStopSequence = newStopSequence;
        changed = true;
      }
    }
  }
}

这经常无法找到最佳解决方案（例如，它不会在上面的示例中找到最佳游览）。我尝试通过移位来增加它（对于每个索引，对于每个长度，将该段移动到末尾），但这样做会导致 2 个问题：

我重复了一些游览的可能性（低效）
我仍然没有达到最佳状态，即使是 5 个城市的小行程

我已经看到 lin-kernighan-helsgaun 算法实现了小于 50 的优化，并且 'exact' 变体适用于异步图（http://www.researchgate.net/profile/Daniel_Karapetyan/publication/227414913_Lin-Kernighan_heuristic_adaptations_for_the_generalized_traveling_salesman_problem/links/02e7e527676733456d000000.pdf 第 11 页），但我不确定如何使其适应我的用例。

如果可以使用这个启发式方法，你能帮我弄清楚如何实现吗？如果不是，什么是最合适的启发式 returns 最小问题（例如 n < 15）的最佳结果和较大问题的接近最佳结果？

Answer 1

能最优求解15个城市问题的最简单算法是指数时间动态规划：https://class.coursera.org/algo2-002/lecture/181。以此为起点，您可以通过将其应用于 15 个城市的子旅游来进行大社区本地搜索。

异步旅行推销员子旅行的本地搜索启发式

A local search heuristic for a subtour in an asynchronous traveling salesman

javascript

algorithm

optimization

mathematical-optimization

traveling-salesman