标签: traveling-salesman

我想知道TSP没有问题的名称是什么,考虑回到起点的方式以及解决这个问题的算法是什么.

我查看了最短路径问题,但这不是我想要的,问题只能找到2个指定点的最短路径.但我正在寻找的是我们给出n分并仅输入1个起点的问题.然后,找到所有点正好行进一次的最短路径.(终点可以是任何一点.)

我也研究了汉密尔顿路径问题,但似乎没有解决我定义的问题,而是找出是否存在汉密尔顿路径.

请指教我,谢谢!

我有一个问题,已经有效地减少到多个推销员的旅行推销员问题.我有一个从初始位置访问的城市列表,并且必须访问所有销售人员数量有限的城市.

我试图想出一个启发式,并想知道是否有人可以伸出援助之手.例如,如果我有20个城市有2个推销员,我想采取的方法是两步法.首先,将20个城市随机划分为10个城市,每个城市为2个销售人员,我会发现每个城市的旅行,好像它是独立的几次迭代.之后,我想交换或指定一个城市给另一个推销员并找到旅游.实际上,它是一个TSP,然后是最小的完工时间问题.问题在于它太慢了,交换或分配城市的邻里生成很难.

任何人都可以就如何改进上述内容提出建议吗？

编辑:

每个城市的地理位置都是已知的,销售人员在同一个地方开始和结束.目标是最小化最大行程时间,使这种最小完工时间问题.因此,例如,如果salesman1需要10个小时而salesman2需要20个小时,则最长行程时间为20个小时.

我试图按顺序沿路径排序3D坐标数组.一个样品:

points = np.array([[ 0.81127451,  0.22794118,  0.52009804],
                   [ 0.62986425,  0.4546003 ,  0.12971342],
                   [ 0.50666667,  0.41137255,  0.65215686],
                   [ 0.79526144,  0.58186275,  0.04738562],
                   [ 0.55163399,  0.49803922,  0.24117647],
                   [ 0.47385621,  0.64084967,  0.10653595]])

这些点是随机顺序的,但总是有一条通过它们的路径.我正在使用LKH解算器(Helsgaun 2009)找到适应旅行商问题(TSP)的路径.它涉及两个修改:

• 在原点处或附近添加一个点.这是我到目前为止所处理的每个实例中的最佳起点.这是我的想法,我没有其他依据.
• 在每个点的零距离处添加一个点.这使得求解器找到到路径另一端的路径.这个想法来自这个问题.

请注意,TSP不涉及位置,只涉及节点之间的距离.所以求解者确实"知道"(或关心)我在3D中工作.我只是像这样制作一个距离矩阵:

import numpy as np
from scipy.spatial.distance import pdist, squareform

# Add a point near the origin.
points = np.vstack([[[0.25, 0, 0.5]], points])
dists = squareform(pdist(points, 'euclidean'))

# Normalize to int16s because the solver likes it.
d = 32767 * …

鉴于城市列表和每个城市之间的飞行成本,我试图找到访问所有这些城市的最便宜的行程.我目前正在使用MATLAB解决方案找到最便宜的路线,但我现在想修改算法以允许以下内容:

1. 重复节点 - 应允许重复节点,因为通过枢纽城市旅行通常会导致更便宜的路线
2. 动态边缘权重 - 返回/往返航班与两个等效单程航班的成本不同(通常较低)

目前,我忽略了航班日期的问题,并假设可以从任何城市前往任何其他城市.

有没有人有任何想法如何解决这个问题？我的第一个想法是使用像GA或ACO这样的进化优化方法来解决第2点,并根据行程中是否包含返程/往返航班来评估目标函数时简单地调整边权重,但也许其他人有更好的理念.

(注意:我使用的是MATLAB,但我不是专门寻找编码解决方案,更多的是关于可以使用哪种算法的高级想法.)

编辑 - 在考虑了这个之后,允许"重复节点"似乎过于松散了约束.我们可以进一步约束问题,以便尽管可以重复访问节点,但每个有向边只能访问一次.忽略任何不止一次包含同一航班的行程似乎是合理的.

我在NP Completeness的背景下在大学里学习过TSP.我实际上从未遇到过适用于实际问题的情况.一些研究表明,它已被用来选择最便宜的移动钻头的路径,即在电路板上钻孔.这几乎是我所能找到的.

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

我的任务是编写A*算法的实现(提供启发式算法),以解决旅行商问题.我理解算法,它很简单,但我只是看不到实现它的代码.我的意思是,我明白了.节点的优先级队列,按距离+启发式(节点)排序,将最近的节点添加到路径上.问题是,如果无法从前一个最近的节点到达最近的节点会发生什么？如何将"图形"作为函数参数？我只是无法看到算法实际上如何运作,如代码.

我在发布问题之前阅读了维基百科页面.反复.它并没有真正回答问题 - 搜索图表的方式与解决TSP的方式不同.例如,您可以构造一个图形,其中任何给定时间的最短节点总是导致回溯,因为相同长度的两条路径不相等,而如果您只是尝试从A到B,那么两条路径长度相同的是相同的.

您可以通过始终最接近的方式派生一个图形,通过该图形永远不会到达某些节点.

我真的不知道A*如何适用于TSP.我的意思是,找到从A到B的路线,当然,我明白了.但TSP？我没有看到连接.

有人可以给我一个2-opt算法的代码样本,用于旅行商问题.现在我使用最近邻居找到路径,但这种方法远非完美,经过一些研究后我发现2-opt算法可以将该路径纠正到可接受的水平.我发现了一些示例应用程序,但没有源代码.

有没有办法使用Google Maps API在给定一组航路点(换句话说,对旅行商问题的"足够好的"解决方案)的情况下取回"优化"路线,或者它是否始终返回路线按指定顺序分？

假设你有一个这样的网格(随机制作):

现在让我们假设你有一辆汽车从其中一个盒子里随机开始,那么通过每个白盒子的最短路径是什么？您可以根据需要多次访问每个白盒,也不能跳过黑盒子.黑匣子就像墙壁.简单来说,您只能从白框移动到白盒.

您可以向任何方向移动,甚至是对角移动.

两个子问题:

1. 假设您在移动之前知道所有黑匣子的位置.
2. 假设您在与其相邻的白色框中时只知道黑匣子的位置.

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

我该如何对基因组进行交叉操作？

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