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

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解算器(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 * 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)

我将它传递给我的forkpytsp,它将它传递给LKH求解器.一切都很好......除非路径穿过自己.TSP解决方案不能有闭环,所以我总是得到右边显示的开环:

请注意,这是我的情况的类似2D版本.还要注意,即使沿着"直"位,这些点也不完全对齐.

所以我的问题是:如何尽可能帮助求解器保持路径的方向？我有两个结构不合理的想法,但到目前为止还没有实现任何东西:

• 使用其他指标而不是L2.但我不认为这可行,因为在给定的交汇点,"错误"点没有任何本质上的不同.它的错误取决于前一点.我们还不知道前一点是什么(这是我们想要弄清楚的).所以我认为这不好.
• 评估每组三个点的局部共线性(例如,使用每个三元组的行列式).通过该共线性系数调制局部"3D斜率"(不确定我的意思).给每个点指定另一个表示此局部对齐的维度.现在规范将反映局部对齐,并且(希望)粗略的共线事物将会加入.

我把这些文件放在Dropbox上:

• 原始数据NumPy文件
• 订购数据NumPy文件

谢谢你的阅读; 任何想法赞赏.

参考

K. Helsgaun,一般用于Lin-Kernighan TSP启发式的k-opt子手套.数学规划计算,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 数据的解决方案中是否不可能存在闭环。在我看来，“无闭环”是二维特有的（三角不等式）的结果。