问题标签 [traveling-salesman]

维基百科说：

旅行商问题即使在最纯粹的表述中也有多种应用，例如规划、物流和微芯片的制造。

我想了解更多关于 TSP 在不同领域的使用情况。不幸的是，搜索产生了很多关于陈述问题并试图仅以理论方式解决问题的结果。

我也发现了这个：

在广义旅行商问题 (GTSP) 中，目标是确定成本最低的哈密顿回路或通过几个顶点集群的循环。结果表明，可以将各种组合优化问题建模为 GTSP。这些问题包括位置选路问题、物流系统设计、邮箱收集、随机车辆选路和弧线选路。

但同样，它太笼统了。

您知道哪些实际使用旅行商问题及其解决方案的例子？

如果存在更好的 TSP 解决方案，还有什么可以做得更好？

我正在尝试创建一个 python 脚本来计算一组大学的最短行程。我需要添加一个起点，但我将自己迷惑到无法相信的地步。谁能帮我弄清楚从这里去哪里

无法让 tour_length 正常工作

我正在建立一个航点谷歌地图。我有起点和终点，它们位于同一位置。它似乎用我的航点绘制了一张地图，但起点和终点位置不在我的地图上。没有A点。必须有其他人必须处理这个问题。

有什么帮助吗？这是我的代码。来自 Google 示例的标准代码：

此外，航点似乎不遵循旅行推销员算法。它让我的路线走遍了。路线应该优化吗？

谢谢

在“密集”图中，我正在尝试使用Palmer's Algorithm构建哈密顿循环。但是，我需要对这个算法进行更多解释，因为当我实现它时它对我不起作用。维基百科的解释似乎有一个不清楚的部分。

如果有人更清楚地解释它或给我一些阅读链接，我将不胜感激。

这是算法语句：

Palmer (1997) 描述了以下简单算法，用于在满足 Ore 条件的图中构造哈密顿循环。将顶点任意排列成一个循环，忽略图中的邻接关系。当循环包含两个连续的顶点vi并且vi + 1在图中不相邻时，执行以下两个步骤：

• 搜索一个索引j，使得四个顶点vi、vi + 1、vj和vj + 1都是不同的，并且图包含从vitovj + 1和 from vjto的边vi + 1

• vi + 1反转和vj（包括）之间的循环部分。

更具体地说，我没有得到他们说的部分：在这种情况下，“将顶点任意排列成一个循环”，这是正确的做法：0,1,2,3,4,0

它们是什么意思：“扭转循环的一部分”？

在其他帖子中，Networkx 被建议为“我的朋友”。但是对于 TSP 问题的特定解决方案似乎没有现成的功能。即在Python中创建无向图

我有一个无向图，建议的解决方案都与有向图有关，我想知道使用可用边访问所有节点的短途旅行。

（另外，我在 networkx 的文档中找不到带有有向图的 tsp）

有没有人为无向图做了这样的事情，或者我应该修改有向图的解决方案，对于未连接的节点具有无限成本？

编辑：我正在学习：实际上，由于图未加权（或“所有权重”相同），并且并非每个节点都连接到所有其他节点，我只需要在包含所有节点的图中找到一个循环。当该循环不存在时，节点可能会重复（因此，它不再是循环......）。没有孤立的组（从每个节点到另一个节点都有一条路径）。我想这不是推销员的问题？！

到目前为止感谢您的反馈（当毫秒开始重要时，我将安装照片完成 :)）

我有 AutoRoute 11.0、AutoRoute 2010、MapPoint 2010、MapPoint 2011、MapPoint 2013。

我注意到，当我优化停止时，第一个需要合理的时间，而其他 4 个（更新的......）要慢得多。

例如，我尝试使用相同的 67 个站点，分布在托斯卡纳、拉齐奥和坎帕尼亚（在意大利）。较旧的 AutoRoute 需要半分钟，而其他 AutoRoute 大约需要 20 分钟。不幸的是，如此缓慢的过程对我们的客户毫无用处。

这怎么解释？算法的变化？设置一些设置？谢谢！

我正在为学校的数学课做一个项目，我选择做我的旅行商问题，这是我一直想进一步研究的问题。但是，我的蛮力求解算法存在问题。

*请到底部更新查看最新版本的代码

如果您知道旅行推销员的问题是什么，请跳过此段落： 尽可能地总结一下，TSP 是这样的：你是一个推销员，想要访问一个地区的每个城市（一个城市本质上是地图上的一个点）。在有界的 x 和 y 区域中有“n”个城市，每个城市都与每个城市相连（假设一条直路）。您需要在允许您访问每个城市的城市中找到最短的路线。我想使用的算法之一（我需要测试其他算法）是蛮力，它检查每条可能的路线并返回最短的路线路线。之所以不总是使用它，是因为它需要我们检查 (n-1)！可能的路线，随着“n”的增加，这个数字会变得很大——事实上，只有 50 个城市，那就是 608281864034267560872252163321295376887552831379210240000000000 条要检查的路线。

假设在这篇文章中讨论的所有示例，我们将使用具有 4个城市的任意区域（即使算法可以处理 n 个城市。我们也不关心距离 - 我们想粗暴地击中每条可能的路线力量）。

这是一个简单的图片演示我在说什么（4个城市是我开始检查过程是否正常工作）

带有城市的地图图片

这是蛮力算法（假设所有其他调用的方法都能正常工作，因为它们确实如此）：

（检查下面的更多解释）

[代码]

这是我的逻辑：（注意：城市对象有一个名为“已访问”的“标志”布尔变量）

（如果没有标记所有路线，并且路线不包含每个可能的城市）

• 从 1 个未标记城市的路线开始。
• 标记“最后一个未标记”的城市（这个城市是“枢轴”）
• 找到每个“不在 ROUTE R”中的城市，并将其添加到新路线中。
• 在这些路由中的每一个上递归调用 BruteForce 方法。

（如果所有路线都没有标记，但路线包含每个城市）

• 标记最后一个城市

（否则...这意味着该路线已标记每个城市并包含每个可能的城市）

• 看看这是否是最短的路线 - 如果是，将其存储在全局变量中

这张图片将帮助我解释问题......所以程序正确地从左侧下降。然而，在它到达底部之后，人们会期望递归跳回到第 4 步，它确实如此。然而，不是 R 将城市 A 标记和城市 B 未标记，然后在包含 Aflag 和 B 的“新路线”上递归调用自己，R 现在包含所有 4 个城市，并且所有 4 个城市都被标记。它失败了，因为它将城市 D 再次添加到“newRoute”，再次递归调用自身，在另一种方法中，我们得到一个数组越界错误，因为我所在的地区没有 5 个城市，但路线 r 中有 5 个城市错误（A、B、C、D、D）。

递归树结构的有用图片

该问题与在循环中调用递归或在递归调用中引用路由“r”有关。

如果您知道我需要做什么，我将非常感谢您的帮助。

感谢任何会帮助我的人。我会将整个项目发送给任何愿意提供帮助的人。

更新

好吧，所以我试图缩短和简化我原来的方法，这就是我所拥有的：

问题是，当我们跳出递归时，for 循环中的变量 i 似乎失去了意义，并且循环不会继续。想法？

我正在使用遗传算法 (GA) 来优化旅行商问题 (TSP)。我的问题是我如何计算个人的适应度。显然，具有较短路线的解决方案更合适，但是我如何在不知道最短可能路线和最长可能路线是什么的情况下准确分配适应度值来确定我的解决方案适合该范围的位置？

我正在研究我的硕士项目，希望你能给我一些关于如何在 java 中解决以下问题的想法：

交易者想要购买物品清单。他可以从多个卖家/市场购买商品。市场与买方的距离不同。买家必须想办法在尽可能短的距离内购买最便宜的商品。

本质上，买家希望在寻找最便宜的商品的同时尽量减少他的旅行成本。

我希望描述是有道理的，如果我不清楚，请告诉我，我会尝试以不同的方式解释它。

到目前为止，我有一个买家类、卖家类、项目类和主类。我打算把买家的位置和卖家的位置使用Java Point类型。

我正在考虑使用类似 Dijkstra 的最短路径算法，但问题是如果买家走得更远，他可能会以更便宜的价格买到一件物品。

提前感谢您的帮助和时间。

我需要一个具有以下更改的旅行商问题的启发式方法：

• 我们只需要访问V 的一个子集（给定V 的一个子集我们必须访问）。V=城市。

• 我们不需要在起始顶点（城市）结束旅行。

这个问题有已知的名称吗？我能找到一个很好的启发式方法来解决它吗？

感谢先进:)