的排列来表示，因此所有可能的路线有条。
这样，若用枚举法来解决这一问题，即使
不太大，例如n＝30，用目前最快的计算机， 也要化几百万年才能求出一条最短的路线。
14
•
早在1954年，Dantzig等人就曾提出
过一种方法（非多项式算法），并且求出
了一个42城市的TSP最优解。到了1960年代，
不少人用分支定界法解决了许多有几十个
V={v0,v1,…vn-1}，v0为名推销员出发点，记 V‘={v01,v02,…v0m; v0,v1,…vn-1} ，扩大的m-1个顶 点称为“人造顶点”，其距离矩阵也相应扩13
• 二、多面体理论
•
从上世纪70年代开始的关于算法复杂
性的研究表明，要想为TSP找到一个好的算
法，也即多项式算法，似乎是不可能的。 由于推销员的每条路线可以用一个以1开始
第7章 旅行商问题
1
目录
第7章 旅行商问题
1.问题概述 2.求解算法
2.1.下界和上界算法
2.2.分支定界法 2.3.动态规划法 2.5.近似算法 2.5.竞赛题
2
§7-1 问题概述
• 一、数学模型
• 1. 标准TSP
•
旅行商问题（简称TSP），也称货郎
担问题或旅行推销员问题，是运筹学中一
个著名的问题，其一般提法为：有一个旅
城市的TSP。还有人提出了一些近似方法，
也解决了许多有几十个城市甚至上百个城
市的TSP（有时找到的仅是近似解）。更值
得注意的是，从1970年代中期开始，
j1
n
s.t
i1
xij
1,
xij S 1,
iS jS
xij 0, 1
i V j V S V , 2 S n 1
(7 1) (7 2) (7 3)
模型中，为集合中所含图的顶点数。约束（7－1）
和（7－2）意味着对每个点而言，仅有一条边进和一条
4
•
记为赋权图G=(V,E)，V为顶点集，E为
边集，各顶点间的距离dij已知。设
xij

1 , 0,
若i, j 在回路路径上
其他
则经典的TSP可写为如下的数学规划模型：
nn
min Z
dij xij
i 1 j 1
n

xij 1,
j 1
n
s.t
i1
xij
1,
xij S 1,
iS jS
xij 0, 1
i V j V S V , 2 S n 1
(7 1) (7 2) (7 3)
5
nn
min Z
dij xij
i1 j1
n

xij 1,
人在几分钟内就可理解的游戏之作，却延续至今仍未能完
全解决，成了一个世界难题。
•
TSP有着明显的实际意义，如，邮局里负责到各信箱
开箱取信的邮递员，以及去各分局送邮件的汽车等，都会
遇到类似的问题。有趣的是，还有一些问题表面上看似乎
与TSP无关，而实质上却可以归结为TSP来求解。已经证明，
TSP是个NP难题，除非P = NP，否则不存在有效算法。
n-1
1, 对j 1, 2,
k 0
xkj

m,
对j 0
,n 1
s.t.

n -1xik来自 k 0 1, m,
对i 1, 2, 对i 0
,n 1

xij
0, 1,
xii

0,
i, j
且不存在任何子回路
•
假定原问题为对称型MTSP，
行商从城市1出发，需要到城市2、3、…、n 去推销货物，最后返回城市1，若任意两个
城市间的距离已知，则该旅行商应如何选
择其最佳行走路线？
3
•
TSP在图论意义下又常常被称为最小Hamilton圈问题，
Euler等人最早研究了该问题的雏形，后来由英国的
Hamilton爵士作为一个悬赏问题而提出。但这个能让普通
走不同的路线，使得所有的城市都至少被访问过一次，然后
返回出发点，要求所有推销员的总行程最短，则问题就成为
一个多人的旅行商问题（简记MTSP）。
•
令决策变量
1, xij 0,
若有某推销员从城市i 到城市j 否则
则MTSP的数学模型为：
12
m n-1
min Z
dij xij
i 1 j 0
式的，简称为ΔTSP。
7
• 2. 扩展TSP
• (1) 瓶颈TSP
•
瓶颈问题是最早从TSP延伸出来的一
种扩展型TSP，其含义与经典的TSP类似，仅
目标不同，要求巡回路线中经过的最长距
离最短，即最小化瓶颈距离。该情形体现
了那些并不追求总巡回路线最短，而只希
望在巡回路线中每次从一个地点至另一个
地点的单次行程尽可能短的实际应用问题
边出；约束（7－3）则保证了没有任何子回路解的产生。
于是，满足约束（7－1）、（7－2）和（7－3）的解
构成了一条Hamilton回路。
6
•
当dij=dji (i, j∈V) 时，问题被称为对称型
TSP，否则称为非对称型TSP。
•
若对所有1≤i, j, k≤n ，有不等式dij + djk
≥ dik成立，则问题被称为是满足三角形不等
的特征。
8
• 从严格的数学意义而言，瓶颈TSP（简称 BTSP）并没有降低问题的难度，也未能提供任 何特殊的解决办法。
•
瓶颈TSP的数学模型与标准TSP类似，仅目
标函数不同：
• min Z max dij xij i, j V
由于目标函数为瓶颈值，故求得的最佳巡回路 线与标准TSP的往往截然不同。
10
•
假定收益的数学性质与相同，则最小比
率TSP的数学模型也与标准TSP类似，仅目标
函数不同：
min Z
i j dij xij
i j pij xij
毫无疑问，由于目标函数中的非线性因素，最 小比率TSP的求解比之标准TSP显得更为困难。
11
• (3) 多人TSP
•
若标准TSP中，出发点有多个推销员同时出发，各自行
9
• (2) 最小比率TSP
•
最小比率TSP（简称MRTSP）是从经
典TSP引申出来的另一个变形问题，假定从
一个城市走到另一个城市可得到某种收益
（记为），则MRTSP的目标就是确定最佳行
走路线，使得回路的总行程与总收益之比
最小。这种优化目标的思想类似于人们日
常生活中经常使用的费用效益比，与单纯
的总行程最短相比，往往更具实际意义。