问题标签 [traveling-salesman]

I made a memetic algorithm in Python for traveling salesman problem. However, all the test data (list of distances between cities) I've encountered lack the information of the best solution, so I can't know how close to global optimum my algorithm gets.

Does anyone know where I can find some tsp test data (preferably in matrix form, but anything's good) with known best solution?

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 地图作为现实世界应用程序的示例。

我有一个任务 Z，只有在任务 X 或任务 Y 完成后才能完成。还：

% 任务 Z 的长度取决于完成 X 或 Y 中的哪一个：

% 如果任务 X 完成，任务 Z 需要 4 小时

% 如果任务 Y 完成，任务 Z 需要 7 小时

% 任务 X 需要 5 小时才能完成

% 任务 Y 需要 3 小时才能完成

% 任务 X 和任务 Y 是互斥的：你不能两者都做（但这可能无关紧要，因为这永远不会是最佳的）

问题：我能以最快的速度完成任务 Z 是什么？

在这种情况下，答案显然是 9 小时（X 然后 Z），但我真正的问题有很多这样的情况。

taskjuggler 可以帮助我吗？可以换个工具吗？补充说明：

% 这是“旅行推销员问题”的扩展，因此是 NP-hard。我会对一个好的但非最佳的解决方案感到满意。

% 在实际问题中，一些任务是具有非负值的“里程碑”。我的目标是最大化这些值的总和。不过，我很乐意先解决最短时间问题。此外，所有里程碑的值可能相同，从而简化了问题。

注意：由于 Mathematica 具有快速（但非最佳）解决 TravelingSalesman 问题的功能，因此将其添加为标签。

我正在尝试为这个问题提出一个合理的算法：

假设你有一堆球。每个球至少有一种颜色，但也可以是多色的。每个球上也有一个数字。还有一堆盒子，每个盒子只有一种颜色。目标是最大化盒子中球上的数字总和，唯一的规则是：

• 为了将球放入盒子中，它必须至少具有盒子的颜色
• 你只能在每个盒子里放一个球。

例如，您可以将蓝色和绿色的球放入蓝色盒子或绿色盒子，但不能放入红色盒子。

我提出了一些在运行时间方面有很大帮助的优化。例如，您可以按点值的降序对球进行排序。然后当你从最高数字到最低数字时，如果球只有一种颜色，并且没有其他包含该颜色的更高点球，你可以把它放在那个盒子里（然后把那个盒子和那个球从其余组合）。

我只是好奇这种类型的问题是否有某种动态算法，或者只是变相的旅行推销员问题。如果我知道最多有 X 种颜色会有帮助吗？任何帮助是极大的赞赏。谢谢！

编辑 - 这是一个简单的例子：

球：

• 1 个红球 - 5 分
• 1 个蓝球 - 3 分
• 1 个绿球/红球 - 2 分
• 1 个绿/蓝球 - 4 分
• 1 个红/蓝球 - 1 分

盒子：

• 1红色
• 1 蓝色
• 1 绿色

最佳解决方案：

• 红盒子里的红球
• 蓝色盒子里的蓝色球

• 绿盒中的绿/蓝球

  总分：12分（5+3+4）

我在哪里可以找到旅行萨拉斯曼问题的源代码？

这与旅行商问题有关。首先需要生成所有排列，然后附加目的地（与原点相同）。即：1）abcd abdc ....

2) abcda abdca ....a

我有所有的距离，只需要一个算法来总结它们。我想知道是否有一种算法（最好是 C）我可以使用它，或者某处是否有现成的解决方案。

解决 TSP 问题的最常见的启发式方法（特别是 Kernighan-Lin 启发式方法）需要处理随机生成的游览并从那里改进解决方案。但是，我想出的唯一方法是生成顶点的随机排列并检查它是否是一个解决方案。

对于问题的大型实例（例如 1000 个顶点），此过程可能需要一段时间。是否有另一种智能方法可以更快地为 TSP 问题生成随机游历？请注意，我正在寻找旅行，无论成本如何，而不是最佳解决方案。

提前致谢

我在一家快递公司工作。我们目前通过“手工”解决 50 多个地点路线。

我一直在考虑使用 Google Maps API 来解决这个问题，但我读到有 24 个点的限制。

目前我们在我们的服务器中使用rails，所以我正在考虑使用一个ruby脚本来获取50多个位置的坐标并输出一个合理的解决方案。

你会用什么算法来解决这个问题？

Ruby 是一种很好的编程语言来解决这类问题吗？

你知道任何现有的 ruby​​ 脚本吗？

我遇到了一个使用 Matlab 脚本的旅行推销员解决方案，在它的代码中，我发现它使用了一个名为 City Coordinates 的表示，它看起来像：

5个城市。

在这一点上，我真的不知道作者是如何得到这个表示的，因为从我目前看到的情况来看，手头的信息应该是一个 5*5 对称矩阵，表示这五个城市中任意两个城市之间的距离。

因此，如果有人能给我一个关于基于坐标的表示如何工作的想法，我将不胜感激。提前致谢。

首先，这是家庭作业。我认为很明显我已经做出了努力，我正在寻找提示，而不是代码。

问题如下。操作方程有四个用于改变给定神经元的组件。

• A) 确保每个城市最多访问一次的部分。
• B）一个确保每个位置（第一，第二，第三等）最多有一个城市。
• C) 保证活跃神经元总数等于城市数的一部分。
• D) 使距离最小化的部分。

如果我对 D 的权重足够大以至于它有任何影响，网络就会确定一个无效的游览（例如，访问 A、D、无处、E、C）。但是，我可以减轻 D 的重量，并且代码会找到解决方案，但不是那些距离最小的解决方案。

我将非常感谢任何建议，我已经将头撞在键盘上一段时间了。任何熟悉使用 Hopfield 网络解决 TSP 的人都应该可以理解该代码。

代码：

杜（）

V()