python - 有方向约束的旅行推销员

Question

我正在尝试按路径上的顺序排列一组 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 solver 找到适合旅行商问题 (TSP) 解决方案的路径(赫尔斯冈 2009)。它涉及两个修改:

• 在原点或原点附近添加一个点。这在我迄今为止处理的每个实例中都找到了最佳起点。这是我的想法，我没有其他依据。
• 在距每个点零距离处添加一个点。这使求解器找到通往路径另一端的路径。这个想法来自 this SO question .

注意，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 * dists / np.sqrt(3)
d = d.astype(np.int16)

# Add a point that is zero units from every other point.
row, col = d.shape
d = np.insert(d, row, 0, axis=0)
d = np.insert(d, col, 0, axis=1)

我把这个传给 my fork of pytsp ，将其传递给 LKH 求解器。一切都很好......除了路径交叉时。 TSP 解决方案不能有闭环，所以我总是得到右侧显示的开环:

请注意，这是我的情况的类似 2D 版本。另请注意，这些点未完全对齐，即使沿着“直”位也是如此。

所以我的问题是:我怎样才能帮助求解器尽可能保持路径的方向？我有两个不正确的想法，但到目前为止无法实现任何东西:

• 使用其他指标而不是 L2。但我认为这行不通，因为在给定的路口，“错误”点没有本质上的不同。它的错误取决于前一点。而且我们还不知道哪一点是前一点(这就是我们想要弄清楚的)。所以我认为这不好。
• 评估每组三个点的局部共线性(例如，使用每个三元组的行列式)。通过这个共线性系数调制局部“3D 斜率”(不确定我的意思)。给每个点另一个维度来表达这种局部对齐。现在，规范将反射(reflect)局部对齐，并且(希望)大致共线的事物将连接起来。

我已将这些文件放在 Dropbox 上:

• Raw data NumPy file
• Ordered data NumPy file

感谢您的阅读；任何想法表示赞赏。

引用

K。 Helsgaun，Lin-Kernighan TSP 启发式的通用 k-opt 子 Action 。数学规划计算，2009，doi: 10.1007/s12532-009-0004-6 .

Answer 1

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

另外，我不确定在距离矩阵取自 3D 数据的解决方案中不可能有闭环。在我看来，“无闭环”是 2D 特有的(三角不等式)结果。