广义旅行商问题与旅行商问题的转化

摘要：广义旅行商问题( Generalized Traveling Salesman Problem ，简称GTSP)是比旅行商问题( Traveling Salesman Problem ，简称TSP )更为复杂的一类组合优化问题，TSP 可视为GTSP的特例。GTSP的应用领域更广，但相对于TSP的研究而言，GTSP的研究成果很少。本文介绍了GTSP问题的定义与背景，研究了GTSP与TSP的转化，提出了转化的优缺点和研究方向。

关键词：广义旅行商问题；图论；转化

中图分类号：TP18 文献标识码：A文章编号：1009-3044(2007)05-11334-02

1 引言

上世纪六十年代，Henry-Labordere[1], Saksena[2] 和 Srivastava[3]几乎同时提出了广义旅行商问题（GTSP）。

图论上GTSP可定义如下：设G＝（V，A，W）是一个赋权有向图，其中V={v1,v2,...,vn}为顶点集（vertex set），A={(vi,vj):vi,vj∈V}为弧集（arc set）。令W=wij是定义在弧集A上的赋权矩阵，其中wij为弧(vi,vj)的费用。旅行商问题（TSP）即为在赋权图G上找一条费用最小的Hamilton回路，即一条能够遍历图中的一切顶点，而且起点与终点重合的路。在GTSP问题中，顶点集V变为p个点群（cluster）的并集，V=V1∪V2∪...∪Vp，目标是要找到一条能够遍历p个点群的费用最小的Hamilton回路。按照点群之间是否有公共点可以把GTSP分为两类。若任何两个点群的交集为空集，称为分离（非交叉）GTSP，否则称为交叉GTSP。本文的研究对象为点群分离的GTSP。

2 GTSP转化为TSP

从定义可以看出TSP是GTSP的一个特例，可以把GTSP转化为TSP求解。由于现在已经有很多针对TSP的算法，研究的重点在于如何转化。

V. Dimitrijevic和Z. Saric[4]考虑点群分离的GTSP转化。令Gs，m＝（W，E）（s，m≥2），W＝{V1∪V2∪...∪Vs}为一个GTSP实例图，其中参数s表示共含有s个点群，m表示每个点群有m个顶点。不失一般性，假设每个点群所含的顶点数相同，则此图中一共有n＝s×m个顶点，且假设E中只包括跨越不同点群的弧，C＝（cij）为E上的赋权矩阵。

下面把Gs，m转化为G'＝（V',E'），G'为TSP实例图。

（1）对每个图G中的点群Vj（j≤s）内的顶点i（i≤m），复制另一个顶点i'，并且增加弧（i，i'）。这样在G'中顶点数变为2n。我们把原来的顶点i称为入顶点（entering vertices），他们的复制顶点i'称为出顶点（leaving vertices）。每对出，入顶点间的弧（i，i'）称为超弧（supervertex arcs），每条超弧的费用为一个足够大的常数 。

（2）每个点群内的入顶点（出顶点）被连成一条回路，这两条回路的方向刚好相反，而且这些弧费用都为0。

（3）原图G中的弧（i，k）在 中用弧（i'，k）代替，费用不变。

V. Dimitrijevic和Z. Saric证明了 内的Hamilton回路如果满足费用小于 (s+1)M，那么这些回路与原图G中的GTSP回路一一对应。因此实例图的最优解可以转化为G中的最优解，而且两个图中最优路径的费用相差常数sM。图1说明了s＝4，m＝3时的转化。

图1 转化示例

这种方法转化后的顶点数为原来的2倍。由于此方法是建立在最简单的模型上，在实际求解中要和其他优化解法相结合，因而增加了调试的复杂性，而且在处理较大规模的问题时可能出现效率过低的问题。

3 结论

本文介绍了GTSP的应用背景，定义，研究了GTSP与TSP的转化，提出了这种转化的优缺点。GTSP展示了组合优化问题的几乎所有方面，吸引了越来越多的不同领域的研究者， GTSP未来的研究应至少包括以下几点：

（1）GTSP模型有着广泛的应用领域，针对具体应用问题深化研究GTSP模型是值得提倡的工作；

（2）求解方法上的研究可使用一些解决组合优化问题的仿生算法用于GTSP，例如蚁群算法，遗传算法。

参考文献：

[1]A L Henry-Labordere. The recordbalancing problem: A dynamic programming solution of a generalized traveling salesman problem[J]. RAIRO. 1969, B2:43-49.

[2]J P Saksena. Mathematical model of scheduling clients through welfare agencies[J]. CORS Journal. 1970, 8: 185-200.

[3]S S Srivastava, S Kumar, R C Garg, P Sen. Generalized traveling salesman problem through n sets of nodes[J]. CORS Journal. 1969, 7: 97-101.

[4]V Dimitrijevic, Z Saric. An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs[J]. Inf Sci. 1997, 102: 105C110.

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。