旅行商问题中的交叉边缘

Question

是否存在旅行推销员问题,其中最优解具有交叉边缘？

节点位于xy平面中,因此在这种情况下交叉意味着如果要绘制图形,则连接四个单独节点的两个线段将相交.

Answer 1

如果闭合折线中的两条边交叉,则存在具有相同顶点但具有较小周长的折线.这是三角不等式的结果.因此,TSP的解决方案必须是简单的多边形.请参阅此文章(图4).

Answer 2

简单地说，任何每个节点都有两条边的连通图都只有一个 TPS 解决方案，如果用交叉绘制将满足您规定的标准。

如果您施加其他约束，例如您正在使用信风进行环球旅行建模，那么成本仅与空间位置有一定关系，您可能会发现更复杂的情况，其中穿越是最佳的。