关于有向图的 TSP 变体，两个相邻节点之间可能有两条边

Question

我正在寻找关于有向图的 TSP（旅行商问题）的变体，其中任意两个相邻节点之间可能存在两条边。 注意：一个节点应该至少被访问一次，并且每两个相邻节点之间的两条平行边方向相反。

有这样的算法吗？

Answer 1

可以将有向图转化为无向图。

获取每个节点

u

并添加一个新节点

u'

。将它们与边权重连接起来，强制边

u-u'

始终成为 TSP 实例解决方案的一部分。任何替代边

u-v

都被分配了原始权重

u->v

并且每个替代边

u'-v

被分配了原始权重

v->u

.

然后，在解决对称问题之后，您可以通过将所有

u

和

u'

再次合并为一个来在原始图中导出TSP。