Noon-Bean Transformation详解1

GTSP 转换为 TSP

文档作者： 李拥祺

Noon-Bean Transformation详解

论文

C. E. Noon and J. C. Bean, “An efficient transformation of the generalized traveling salesman

problem,” INFOR, vol. 31, no. 1, pp. 39 – 44, 1993.

转换过程

定义一个 asymmetric GTSP 实例 ，节点集 ，边集记为 ， 中只包含

转换过程：

;

假设每一个簇中的节点都有一个任意的顺序， ， ;

在每一个簇中添加边 ;

新添加的边都赋权值 0 ，即 ；

对于 中的边 ，在 中变为 ，且

；

其中

对于 中的边 在 中变为 ，且 ；

证明

问题 的任意可行解，如果是从节点 进入簇 ,那么其必然从节点

离开 ；如果是从节点 进入簇 ，那么其必然从节点 离开；（这是很显然的，

因为clustered TSP的可行解就是需要遍历簇节点）

这也就意味着如果问题 有一个可行解通过了边 ，那么这个可行解也必然包括

以节点 为进簇点的簇间边和以节点 为出簇点的簇间边。

因此，如果给定问题 的任意可行解 ，我们可以构造出问题 的一个可行解 ：对