问题标签 [traveling-salesman]

我知道那里有几个不同的旅行推销员项目，我和LKH玩过一些，但我想知道是否有人对其他项目有任何建议？

我的项目是 GPL 的，所以我需要与该许可证兼容的东西。

我在大学时在 NP Completeness 的背景下学习了 TSP。我从来没有真正遇到过适用于实际问题的情况。一些研究表明，它已被用来选择最便宜的移动钻头的路径，即在电路板上打孔。这几乎是我能找到的所有东西。

你在用吗？TSA 还有哪些其他实际应用？

有没有办法使用 Google Maps API 在给定一组航点的情况下返回“优化”路线（换句话说，旅行商问题的“足够好”的解决方案），或者它总是返回带有按指定顺序点？

在过去的几天里，我注意到一些网站展示 了使用遗传算法的 TS 解决方案。

哪种方法会在 TSP 问题中产生更短的行程：最近邻算法还是遗传算法？

这是一个项目，我被要求为旅行商优化问题以及哈密顿路径或循环决策问题实施启发式算法。我不需要实施本身的帮助，但对我的前进方向有疑问。

我已经有一个基于遗传算法的 TSP 启发式算法：它假设一个完整的图，从一组随机解作为总体，并努力改进几代人的总体。我也可以用它来解决哈密顿路径或循环问题吗？而不是优化以获得最短路径，我只想检查是否有路径。

现在任何完整的图都将有一条哈密顿路径，因此 TSP 启发式必须扩展到任何图。如果两个城市之间没有路径，这可以通过将边设置为某个无穷大值来完成，并返回第一条有效的哈密顿路径。

这是处理它的正确方法吗？或者我应该对哈密顿路径使用不同的启发式方法？我主要关心的是它是否是一种可行的方法，因为我可以肯定 TSP 优化是有效的（因为你从解决方案开始并改进它们），但如果哈密顿路径决定器会在固定代数中找到任何路径，则不是。

我认为最好的方法是自己测试它，但我受到时间的限制，并认为在沿着这条路线走之前我会问......（我可以为哈密顿路径找到不同的启发式）

我希望通过多次访问来讨论 TSP 的分支和绑定解决方案。（也就是说，每个城市都需要至少访问一次，而不仅仅是一次）

编辑：

消除了疑虑，因为它与 Jitse 指出的不相关。现在问题更清楚了。

我有一个强连接的有向图（即，对于图 G 中的每对节点（i，j），都有一条从 i 到 j 和 j 到 i 的路径）。我希望从这个图中找到一个强连通图，使得所有边的总和最小。

换句话说，我需要以这样一种方式摆脱边缘，即在移除它们之后，图形仍将是强连接的，并且边缘总和的成本最低。

我认为这是一个NP难题。我正在为一小组数据（如 20 个节点）寻找最佳解决方案，而不是近似值。

编辑

更一般的描述：给定一个图 G(V,E) 找到一个图 G'(V,E') 使得如果在 G 中存在从 v1 到 v2 的路径，那么在 G 中也存在 v1 和 v2 之间的路径' 和 E 中每个 ei 的总和是最不可能的。所以它类似于找到一个最小等价图，只是在这里我们想要最小化边权重的总和而不是边的总和。

编辑：

到目前为止我的方法：我想过使用多次访问的 TSP 来解决它，但它是不正确的。我的目标是覆盖每个城市，但使用最低成本路径。所以，我猜这更像是封面设置问题，但我不确定。我需要使用总成本最低的路径覆盖每个城市，因此多次访问已经访问过的路径不会增加成本。

我正在尝试用遗传算法解决旅行商问题（TSP）。我的基因组是图中顶点的排列（推销员的路径）。

我应该如何对我的基因组执行交叉操作？

我在哪里可以找到 C# 中我的问题的实现？

在 (a) 和 (b) 中，假设一个 2 交换变换算子，将解决方案 A 和 B，它们是路径表示中的 TSP 旅游，连接到它们在旅游 C、D、E、F、G 中的可能邻居

我不知道这是要我做什么。

I'm trying to solve the TSP with Branch and bound algorithm.

I must build a matrix with costs but I have this problem: I have city with coordinates x and y.

The cost of traveling is ceil(ceil(sqrt((x1-x2)^2+(y1-y2)^2))/v) + days spent in the city. V is speed.

Days spent in the city depends from day when w comes to the city. For example if we arrived on Monday(t1) to city 1, we stay for 9 days but if we arrived on Tuesday, then we stay in the city for 4 days.

How can I solve this problem using branch and bound algorithm?