陈冬华

（华东交通大学基础科学学院，江西南昌 330013）

1TSP与CTSP

从上个世纪50年代起，学术界出版了大量关于旅行商问题[1]的文献。旅行商问题（traveling salesman problem，TSP）是指这样一个组合优化问题：某个商人欲到n座城市A=（a1，a2，…，an）去推销商品，希望选择一条路线使得商人走遍每座城市后（仅能访问一次）回到起点且所走路程最短。用图论术语来说[2]，假设有一个图g=（v，e），其中v是顶点集（顶点对应于某个城市），e是边集（城市之间的连接状态，每边赋予权重表示城市间距离），设D是由顶点i与顶点j之间的距离所组成的距离矩阵，如果任意两个城市的距离都是对称的，它所对应的是图论中的无向图，若两个城市间的距离是非对称的，它所对应于图论中的有向图。旅行商问题就是求出一条经过所有顶点且每个顶点只经过一次的具有最短路径的回路。

如果令城市ai与aj的距离为dij，用xij表示商人是否以顺序i访问城市ai后接着访问城市aj（即，xij=1表示商人以顺序i访问城市ai后接着访问城市aj，否则xij=0），则TSP问题可以描述成如下优化问题

式中：s.t.为约束条件。

TSP是典型的NP-hard问题，是组合优化领域研究中研究最多的问题之一，也是目前解决旅行优化领域里的研究热点。也有不少研究者对TSP进行了推广，如多旅行商问题[3-6]，广义旅行商问题[7-14]，中国旅行商问题[15]，有向黑白旅行商问题[16]。

下面将TSP变形推广成全体旅行商问题（caboodle traveling salesman problem，CTSP）。CTSP定义如下：某个商人拥有s种货物B=（b1，b2，…，bs），其中bj（j=1，2，…，s）表示第j种货物的数量，欲到n座城市A=（A1，A2，…，An）去推销这些商品，Ai=（a1i，a2i，…，asi），其中aji（i=1，2，…，n；j=1，2，…，s）表示第i座城市Ai对这s种……