具有方向约束的旅行推销员

Question

我试着在一条路径上按顺序排列三维坐标。样品：

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 solver（Helsgaun 2009）找到了一个适应旅行商问题（TSP）解的路径。它包括两个修改：

• 在原点处或附近添加点。这在我目前处理的每一个例子中都找到了最好的起点。这是我的主意，我没有其他依据。在
• 在距每个点0的距离处添加一个点。这将使解算器找到路径另一端的路径。{就是这个主意。在

注意，TSP不涉及位置，只涉及节点之间的距离。所以解算器“知道”（或关心）我在3D中工作。我只需制作一个距离矩阵，如下所示：

^{pr2}$

我将此传递给my fork of ^{}，后者将其传递给LKH解算器。一切都很好。。。除非这条路穿过自己。TSP解决方案不能有闭合回路，因此我总是在右侧显示开环：

请注意，这是一个类似的2D版本。还要注意的是，这些点是不完全对齐的，即使是沿着“直线”位。

所以我的问题是：如何帮助解算器尽可能保持路径的方向？我有两个不成熟的想法，但到目前为止还无法实现任何东西：

• 使用另一个度量而不是L2。但我认为这行不通，因为在一个特定的交叉口，“错误”点没有本质上的不同。它的错误取决于前一点。我们还不知道前一点是哪一点（这正是我们试图弄清楚的）。所以我觉得这不好。在
• 评估每组三个点的局部共线性（例如，使用每三个三元组的行列式）。用这个共线系数来调节局部的“3D斜率”（不确定我的意思）。给每个点另一个维度来表达这种局部对齐。现在，标准将反映出局部对齐，并且（希望）大致共线的东西将结合起来。在

我把这些文件放在Dropbox上：

• Raw data NumPy file
• Ordered data NumPy file

谢谢你的阅读；任何想法都值得赞赏。在

参考

Helsgaun，一般K-opt子移动用于Lin-Kernighan TSP启发式。数学规划计算，2009，doi: 10.1007/s12532-009-0004-6。在

Answer 1

从pytsp上的文档来看，距离矩阵不必是对称的。这意味着您可以修改L2规范，将有关首选方向的信息合并到该矩阵中。假设你对一些点（i，j）有一个优先的方向，那么对于每一个点，你可以用dists[i,j]除以(1+a)，然后用dists[j,i]乘以{}，使这个方向更有利。这意味着，如果您的算法确定能找到全局最优，您可以通过使a足够大来强制它满足您的首选方向。在

另外，我不确定在距离矩阵取自三维数据的解决方案中不可能有闭环。在我看来，这个不等式的结果是封闭的