《数学建模经典问题——旅行商问题课件》由会员分享，可在线阅读，更多相关《数学建模经典问题——旅行商问题课件（104页珍藏版）》请在金锄头文库上搜索。
1、1第第7章章 旅行商问题旅行商问题2第第7章章 旅行商问题旅行商问题1.问题概述问题概述 2.求解算法求解算法 2.1.下界和上界算法下界和上界算法2.2.分支定界法分支定界法 目录目录2.5.竞赛题竞赛题2.3.动态规划法动态规划法2.5.近似算法近似算法37-1 问题概述问题概述 一、数学模型一、数学模型 1. 标准准TSP 旅行商旅行商问题（简称称TSP），也称），也称货郎担郎担问题或或旅行推旅行推销员问题，是运筹学中一个著名的，是运筹学中一个著名的问题，其，其一般提法一般提法为：有一个旅行商从城市：有一个旅行商从城市1出出发，需要到城，需要到城市市2、3、n去推去推销货物，最后返回城市
2、物，最后返回城市1，若任，若任意两个城市意两个城市间的距离已知，的距离已知，则该旅行商旅行商应如何如何选择其最佳行走路其最佳行走路线？4 TSP在在图论意意义下又常常被称下又常常被称为最小最小Hamilton圈圈问题，Euler等人最早研究了等人最早研究了该问题的的雏形，后来由英国的形，后来由英国的Hamilton爵士作爵士作为一个一个悬赏问题而提出。但而提出。但这个能个能让普通人普通人在几分在几分钟内就可理解的游内就可理解的游戏之作，却延之作，却延续至今仍未能完全解至今仍未能完全解决，成了一个世界决，成了一个世界难题。 TSP有着明有着明显的的实际意意义，如，如，邮局里局里负责到各信箱开到各
3、信箱开箱取信的箱取信的邮递员，以及去各分局送，以及去各分局送邮件的汽件的汽车等，都会遇到等，都会遇到类似的似的问题。有趣的是，。有趣的是，还有一些有一些问题表面上看似乎与表面上看似乎与TSP无关，而无关，而实质上却可以上却可以归结为TSP来求解。已来求解。已经证明，明，TSP是个是个NP难题，除非，除非P = NP，否，否则不存在有效算法。不存在有效算法。5 记为赋权图G=(V,E)，V为顶点集，点集，E为边集，集，各各顶点点间的距离的距离dij已知。已知。设则经典的TSP可写为如下的数学规划模型：6 模模型型中中，为为集集合合中中所所含含图图的的顶顶点点数数。约约束束（71）和和（72）意意
4、味味着着对对每每个个点点而而言言，仅仅有有一一条条边边进进和和一一条条边边出出；约约束束（73）则则保保证证了了没没有有任任何何子子回回路路解解的的产产生生。于于是是，满满足足约约束束（71）、（72）和和（73）的解构成了一条的解构成了一条Hamilton回路。回路。7 当当dij=dji (i, jV) 时，问题被称被称为对称型称型TSP，否，否则称称为非非对称型称型TSP。 若若对所有所有1i, j, kn ，有不等式，有不等式dij + djk dik成立，成立，则问题被称被称为是是满足三角形不等式足三角形不等式的，的，简称称为TSP。82. 扩展展TSP(1) 瓶瓶颈TSP 瓶瓶颈问
5、题是最早从是最早从TSP延伸出来的一种延伸出来的一种扩展型展型TSP，其含，其含义与与经典的典的TSP类似，似，仅目目标不同，要不同，要求巡回路求巡回路线中中经过的最的最长距离最短，即最小化瓶距离最短，即最小化瓶颈距离。距离。该情形体情形体现了那些并不追求了那些并不追求总巡回路巡回路线最短，最短，而只希望在巡回路而只希望在巡回路线中每次从一个地点至另一个地中每次从一个地点至另一个地点的点的单次行程尽可能短的次行程尽可能短的实际应用用问题的特征。的特征。9 从从严格的数学意格的数学意义而言，瓶而言，瓶颈TSP（简称称BTSP）并）并没有降低没有降低问题的的难度，也未能提供任何特殊的解决度，也未能
6、提供任何特殊的解决办法。法。 瓶瓶颈TSP的数学模型与的数学模型与标准准TSP类似，似，仅目目标函数函数不同：不同： 由于目标函数为瓶颈值，故求得的最佳巡回路由于目标函数为瓶颈值，故求得的最佳巡回路线与标准线与标准TSP的往往截然不同。的往往截然不同。10(2) 最小比率最小比率TSP 最小比率最小比率TSP（简称称MRTSP）是从）是从经典典TSP引引申出来的另一个申出来的另一个变形形问题，假定从一个城市走到另，假定从一个城市走到另一个城市可得到某种收益（一个城市可得到某种收益（记为），），则MRTSP的目的目标就是确定最佳行走路就是确定最佳行走路线，使得回路的，使得回路的总行程与行程与总收
7、益之比最小。收益之比最小。这种种优化目化目标的思想的思想类似于人似于人们日日常生活中常生活中经常使用的常使用的费用效益比，与用效益比，与单纯的的总行程行程最短相比，往往更具最短相比，往往更具实际意意义。11 假定收益的数学性假定收益的数学性质与相同，与相同，则最小比率最小比率TSP的的数学模型也与数学模型也与标准准TSP类似，似，仅目目标函数不同：函数不同： 毫无疑问，由于目标函数中的非线性因素，最毫无疑问，由于目标函数中的非线性因素，最小比率小比率TSP的求解比之标准的求解比之标准TSP显得更为困难。显得更为困难。12(3) 多人多人TSP 若若标准准TSP中中，出，出发点有多个推点有多个推
8、销员同同时出出发，各自行，各自行走不同的路走不同的路线，使得所有的城市都至少被，使得所有的城市都至少被访问过一次，然后一次，然后返回出返回出发点，要求所有推点，要求所有推销员的的总行程最短，行程最短，则问题就成就成为一个多人的旅行商一个多人的旅行商问题（简记MTSP）。）。 令决策令决策变量量则则MTSP的数学模型为：的数学模型为： 13 假定原假定原问题为对称型称型MTSP，V=v0,v1,vn-1，v0为名推名推销员出出发点，点，记V=v01,v02,v0m; v0,v1,vn-1 ，扩大的大的m-1个个顶点称点称为“人造人造顶点点”，其距离，其距离矩矩阵也相也相应扩大，其中，位于出大，其
9、中，位于出发点的点的m个个顶点相点相互互间的距离的距离设定定为，其他数，其他数值不不变。14二、多面体理二、多面体理论 从上世从上世纪70年代开始的关于算法复年代开始的关于算法复杂性的研究性的研究表明，要想表明，要想为TSP找到一个好的算法，也即多找到一个好的算法，也即多项式式算法，似乎是不可能的。由于推算法，似乎是不可能的。由于推销员的每条路的每条路线可可以用一个以以用一个以1开始的排列来表示，因此所有可能的路开始的排列来表示，因此所有可能的路线有条。有条。这样，若用枚，若用枚举法来解决法来解决这一一问题，即使，即使不太大，例如不太大，例如n30，用目前最快的，用目前最快的计算机，也要算机，
10、也要化几百万年才能求出一条最短的路化几百万年才能求出一条最短的路线。15 早在早在1954年，年，Dantzig等人就曾提出等人就曾提出过一种方一种方法（非多法（非多项式算法），并且求出了一个式算法），并且求出了一个42城市的城市的TSP最最优解。到了解。到了1960年代，不少人用分支定界法年代，不少人用分支定界法解决了解决了许多有几十个城市的多有几十个城市的TSP。还有人提出了一有人提出了一些近似方法，也解决了些近似方法，也解决了许多有几十个城市甚至上百多有几十个城市甚至上百个城市的个城市的TSP（有（有时找到的找到的仅是近似解）。更是近似解）。更值得得注意的是，从注意的是，从1970年代中
11、期开始，年代中期开始，Grotschel与与Padberg等人深入研究了等人深入研究了TS多面体的最大面多面体的最大面（facet），并从所得），并从所得结果出果出发获得了一种解得了一种解TSP的的新算法，可以解决一些有新算法，可以解决一些有100多个城市的多个城市的TSP，且都，且都在不在不长的的时间内找到了最内找到了最优解。解。16 考考虑个个顶点的完全点的完全图Kn ，则解解TSP就相当于在就相当于在中求一条中求一条总长度最短的度最短的Hamilton回路。回路。现在，在，对每每条条边ej，定，定义一个一个变量量xj与之与之对应，这样，TSP的一的一条路条路线T，即，即Kn的一条的一条H
12、amilton回路，就可回路，就可对应一一个向量个向量X=x1,x2,.xm，其中，其中，17 称称X为路路线T的关的关联向量，其向量，其m=n(n-2)/2个分量中，恰好个分量中，恰好有个有个为1，其余的都，其余的都为0。 图有有许多多Hamilton回路，回路，设为T1, T2 Ts,，对应的关的关联向向量量记为X1, X2 Xs ，在，在m维空空间Rm中，考中，考虑这些向量生成的些向量生成的凸包（凸包（convex hull） Qn ：18 Qn是是Rm中的一个凸多面体，称做中的一个凸多面体，称做TS多面体。多面体。显然，然， Qn是有界的，其极点正好是是有界的，其极点正好是Kn的的Ha
13、milton回回路关路关联向量。向量。 研究研究Qn的面非常重要的，因的面非常重要的，因为根据根据线性不等式性不等式及凸多面体的理及凸多面体的理论， Qn一定是某一个有限一定是某一个有限线性不等性不等式式组的解集合，或者的解集合，或者说， Qn一定是有限多个半空一定是有限多个半空间的交。因此，如果能找出定的交。因此，如果能找出定义Qn的的线性不等式性不等式组来，来，就可将就可将TSP作作为一个一个线性性规划来解。划来解。19 TS多面体研究中的一个重要问题就是寻找能导出多面体研究中的一个重要问题就是寻找能导出Qn最大面的不等式，最大面的不等式，Grotschel等人发现了一类很重要的能导等人发
14、现了一类很重要的能导出最大面的梳子不等式，并予以了证明。此外，还有其它出最大面的梳子不等式，并予以了证明。此外，还有其它能导出最大面的不等式，如团树不等式等。可见，能导出最大面的不等式，如团树不等式等。可见， Qn的最的最大面极多，曾经计算过由梳子不等式所导出的最大面个数大面极多，曾经计算过由梳子不等式所导出的最大面个数如表如表71所示：所示：n6810203050120c(n)604142088419701.5*10181.5*103110602*10179表表71 20 可以看出，当增大可以看出，当增大时，最大面个数增，最大面个数增长得非常快。得非常快。 在在TS多面体理多面体理论的基的基
15、础上，可以考上，可以考虑先解先解TSP的松弛的松弛问题，如果得到的最，如果得到的最优解正好是某一条路解正好是某一条路线的关的关联向量，那么向量，那么就找到就找到TSP的最的最优解了；否解了；否则，就，就设法找一些新的不等式作法找一些新的不等式作为额外外约束，再解新的束，再解新的线性性规划，直至找到恰好是关划，直至找到恰好是关联向量向量的最的最优解。解。这种做法的基本思想与解整数种做法的基本思想与解整数规划的割平面法是划的割平面法是同一同一类的，的，Gotschel 等人曾用等人曾用这种方法解种方法解过有有120个城市的个城市的TSP，所增加的不等式只有子回路消去不等式与梳子不等式，所增加的不等
16、式只有子回路消去不等式与梳子不等式两两类，在，在进行了行了13轮计算后，即解了算后，即解了13个个线性性规划后，就找划后，就找到了到了TSP的精确最的精确最优解，每一解，每一轮的当的当时计算算时间仅在在30秒至秒至2分分钟之之间。有趣的是，当。有趣的是，当n = 120时，仅梳子不等式就有梳子不等式就有2*10179个，但在个，但在计算算过程中，程中，总共却只（凭共却只（凭经验）添加了）添加了96个子回路消去不等式与梳子不等式。个子回路消去不等式与梳子不等式。21 当然，用当然，用该方法有方法有时会会找不到找不到TSP的最的最优解，解，因因为很可能在很可能在进行了几行了几轮迭代后，却找不到新的
17、不迭代后，却找不到新的不等式。等式。Padborg与与Hong曾曾计算了算了74个个TSP，其中，其中54个得到了最个得到了最优解，其余的解，其余的虽未得到最未得到最优解，却得到解，却得到了很好的下界，如果与近似方法配合，可以估了很好的下界，如果与近似方法配合，可以估计近近似解的精确程度。如，他似解的精确程度。如，他们解解过一个有一个有313个城市的个城市的TSP，获得一个下界得一个下界41236.46，而用近似方法能得，而用近似方法能得到一条到一条长为41349的路的路线，于是可估，于是可估计出所得近似解出所得近似解与最与最优解的解的误差不超差不超过0.26%。227-2 求解算法求解算法一
18、、下界和上界算法一、下界和上界算法1. 下界下界（1）下界）下界b1和和b2 针对TSP对应图的的邻接矩接矩阵，将矩，将矩阵中每一行最小的元中每一行最小的元素相加，就可得到一个素相加，就可得到一个简单的下界的下界b1。经进一步改一步改进，可得，可得到更好的下界：考到更好的下界：考虑一个一个TSP的完整解，在每条路径上，每的完整解，在每条路径上，每个城市都有两条个城市都有两条邻接接边，一条，一条进，一条出，那么，如果把矩，一条出，那么，如果把矩阵中每一行最小的两个元素相加再除以中每一行最小的两个元素相加再除以2（不失一般性，可（不失一般性，可假定假定图中所有距离中所有距离权重都重都为整数），再整
19、数），再对其其结果向上取整，果向上取整，就可得到一个合理的下界就可得到一个合理的下界b2。 显然，然，b2b1，因此，一般不采用，因此，一般不采用b1作作为TSP的下界。的下界。23例例1 已知已知TSP及其距离矩及其距离矩阵如如图71所示，所示，试求其下求其下界界 271563134253984(a) 无向图无向图图图71 无无向向图图及及距离矩阵距离矩阵(b) 距离矩阵距离矩阵24解：解： 将矩将矩阵中每一行最小的元素相加，中每一行最小的元素相加，1+3+1+3+2 = 10，即得，即得b1=10。将矩。将矩阵中每一行最小的两个元素相中每一行最小的两个元素相加再除以加再除以2，再，再对结果
20、向上取整，即可得果向上取整，即可得b2 = (1+3) + (3+6) + (1+2) + (3+4) + (2+3)/2 = 14。25（2）下界）下界b3为便于描述下界便于描述下界b3，先定，先定义如下符号：如下符号：T：对称称TSP问题；n：结点点总个数；个数；w(i,j)：结点点i与与j之之间距离；距离；dmin(i, k)：与第：与第i个个结点关点关联的所有的所有边中第中第k (k = 1, 2, 3)长边的的长度；度；dmin_j(i, k)：与第：与第i个个结点关点关联的所有的所有边中第中第k (k = 1, 2, 3) 长边的另一个的另一个结点的点的编号号(其中一个其中一个结点
21、点编号号为i)；node_ base(i)= dmin_j(i, 1)+ dmin_j(i, 2)：表示与：表示与i点关点关联边中中长度最短的两条度最短的两条边之和；之和；C*(T)：最：最优回路回路长度；度；26 于是，于是，dmin(i, 1)代表与第代表与第i个个结点关点关联的所有的所有边中最中最长边的的长度，度，dmin_j(i, 1) 代表与第代表与第i个个结点关点关联的所有的所有边中次中次长边的另一个的另一个结点点编号号(其中一个其中一个结点点编号号为i)，第，第i结点的点的dmin(i, k)和和dmin_j(i, k)可由距可由距离矩离矩阵w轻易求得。易求得。 通通过对下界下界
22、b2进行改行改进，可以得出一个求，可以得出一个求对称称型型TSP更好的下界更好的下界b3。 在求在求b2的的过程中，只有当与每一程中，只有当与每一结点关点关联的的边中中长度最小的两条度最小的两条边都出都出现在最在最优TSP回路中回路中时，等号才成立，下面就来分析如何提高等号才成立，下面就来分析如何提高这个下界。个下界。27 对结点点i而言，而言，设e (i)1与与e (i)2分分别为与与结点点i关关联的的边中中长度最小的两条度最小的两条边，其，其长度分度分别为dmin (i, 1) 和和dmin (i, 2)。 在在对称型称型TSP回路中，由于有且回路中，由于有且仅有两条有两条边与与每一每一结
23、点关点关联，因此，并不是与每个，因此，并不是与每个结点关点关联的最的最小两条小两条边都能出都能出现在最在最优TSP回路中，回路中，这意味可以意味可以在在node_ base(i)的基的基础上增加上增加TSP回路的回路的长度，将在度，将在这种情况下增加的种情况下增加的长度度记为Adjust (T)，现在分析如在分析如何何计算算Adjust(T)。28 对结点点i的的e (i)1，边e (i)1的一个的一个结点点为i，另一，另一个个结点点为j = dmin_j (i,1)，若，若e (i)1也是也是结点点j关关联边中最小的两条中最小的两条边之一，即之一，即 i = dmin_j (j,1) 或或
24、i = dmin_j (j,2)，则对边e (i)1来来说就不需要就不需要调整，否整，否则按以下方式按以下方式调整：整：29若若e (i)1不是不是结点点j=dmin_j(i,1)关关联边中最小的两条中最小的两条边之一，之一，则只有以下两种情况：只有以下两种情况： 选中中e (i)1到到TSP回路中回路中 此此时对结点点i不需不需调整，整，对结点点j来来说，由于，由于边e (i)1出出现在最在最优回路中，而回路中，而e (i)1不是不是结点点j关关联边中中最小的两条最小的两条边之一，因此会造成之一，因此会造成结点点j关关联边中最小中最小的两条的两条边中至少有一条不会出中至少有一条不会出现在最在
25、最优回路中，从回路中，从而而对结点点j而言，在而言，在node_base (i)的基的基础上至少会增上至少会增加的加的长度度为 dmin (i,1) dmin (j,2) 。30 不不选中中e (i)1到到TSP回路中回路中 此此时对结点点i需要需要调整，由于整，由于边e (i)1不在回路不在回路中，故其在中，故其在node_base (i)的基的基础上至少会增加的上至少会增加的长度度为 dmin (i,3) dmin (i,1)。 此此时对结点点j来来说，由于与它关，由于与它关联的最短两条的最短两条边仍然可能在回路中，因此不仍然可能在回路中，因此不须调整。整。31 对于于和和，必，必须有且有
26、且仅有一种情况出有一种情况出现，现取两种取两种情况中增加情况中增加长度小的度小的值，因而回路的，因而回路的长路一定会在路一定会在b2的基的基础上增加：上增加：add_node (i,1) = 1/2*min (dmin (i,3) dmin (i,1), dmin (i,1) dmin (j,2)。 对结点点i的的e (i)2，边e (i)2的一个的一个结点点为i，另一个，另一个结点点为j = dmin_j (i,2)，若，若e (i)2也是也是结点点j关关联边中最小的两条中最小的两条边之一，之一，则对边e (i)2来来说不需要不需要调整，否整，否则按与前面按与前面类似的方法似的方法计算算调整
27、整值。经分析，其在分析，其在base (T)的基的基础上至少要增加：上至少要增加：add_node (i,2) = 1/2*min (dmin (i,3) dmin (i,2), dmin (i,2) dmin (j,2)。32 将每个将每个结点都按上述方法点都按上述方法进行一次行一次调整，其整，其调整累加和就是整累加和就是Adjust (T)，可写成如下公式：，可写成如下公式：33 将将问题T中所有中所有结点的基本点的基本长度度node_base(T)累累加之和的一半称加之和的一半称为T的基本的基本长度，并用度，并用base (T)来表来表示，可写成如下公式：示，可写成如下公式：34 于是，
28、有于是，有C*(T) base(T) + Adjust(T) = b3，即，即 b3 = b2 + Adjust(T) 。由以上分析，不由以上分析，不难得出求得出求对称称TSP下界下界b3的算法：的算法：35Step 1. 计算算base (T)： get_base () i: Long For i = 1 To n base = base + dmin(i, 1) + dmin(i, 2) 36Step 2. 计算算Adjust (T)： get_adjust () i , ii1, ii2: Long For i = 1 To n ii1 = dmin_j (i, 1); ii2 = dm
29、in_j (i, 2) If i dmin_j (ii1, 1) And i dmin_j (ii1, 2) adjust= adjust+min(dmin(i, 3)-dmin(i,1), dmin(i, 1)-dmin(ii1, 2)If i dmin_j (ii2, 1) And i dmin_j (ii2, 2) adjust = adjust+min (dmin(i,3)-dmin(i, 2),dmin(i, 2)-dmin(ii2, 2) 37对例例1而言，可而言，可计算其算其b3如下：如下：dmin(1, 1)=1；dmin_j(1, 1)=3；dmin(1, 2)=3；dmin
30、_j(1, 2)=2；dmin(1, 3)=5；dmin_j(1, 3)=4；dmin(2, 1)=3；dmin_j(2, 1)=1；dmin(2, 2)=6；dmin_j(2, 2)=3；dmin(2, 3)=7；dmin_j(2, 3)=4；dmin(3, 1)=1；dmin_j(3, 1)=1；dmin(3, 2)=2；dmin_j(3, 2)=5；dmin(3, 3)=4；dmin_j(3, 3)=4；271563134253984(a) 无向图无向图图图71 无向图无向图38dmin(4, 1)=3；dmin_j(4, 1)=5；dmin(4, 2)=4；dmin_j(4, 2)=3
31、；dmin(4, 3)=5；dmin_j(4, 3)=1；dmin(5, 1)=2；dmin_j(5, 1)=3；dmin(5, 2)=3；dmin_j(5, 2)=4；dmin(5, 3)=8；dmin_j(5, 3)=1；271563134253984(a) 无向图无向图图图71 无向图无向图39add_node(1,1)=0; add_node(1,2)=0; add_node(2,1)=0; add_node(2,2)=1/2min (7-6), (6-2)=1/2;add_node(3,1)=0; add_node(3,2)=1/2min (5-4), (4-2)=1/2; add_
32、node(4,1)=0; add_node(4,2)= 0 ; add_node(5,1)=0; add_node(5,2)= 0; 所以，所以，Adjust(T) = 1/2+1/2=1，得，得b3 = b2 +Adjust(T)= 14 + 1 = 15。402. 上界上界 事事实上，上，TSP的任何可行解都是上界，的任何可行解都是上界，这里，里，给出求出求TSP上界上界U1的的贪心方法思想。心方法思想。算法步算法步骤如下：如下：41Step 1. 图G = V, E中中顶点个数点个数为n = |V|，边的条数的条数m = |E|，令，令i为出出发点，点，TSP_edge_n为加入到加入到
33、TSP回路回路中中边的条数且的条数且TSP_edge_n = 0，TSP_edge为已加入已加入到到TSP回路中的回路中的边集合且集合且TSP_edge= ，k为当前当前顶点点且且k = i。Step 2. 从从边集集 中选中一条代价最小的一条边中选中一条代价最小的一条边(k, h)，并执行，并执行 TSP_edge_n = TSP_edge_n + 1； TSP_edge = TSP_edge + (k, h)； k = h。Step 3. 若若TSP_edge_n U1, 故剪支e12=0e12=1b2 = 17 U1, 故剪支得最优解e12=e13= e24= e35= e54=1, e
34、14=e15= e23= e25= e34=0e25=0e25=1b2 = 18.5 U1=16, 故剪支此时有e14=e15= e23=0此时有e24= e35= e54=1, e34 = 049 (1)用用贪心算法求得心算法求得上界上界U1 = 16； (2)假定假定边(1, 3)不在不在TSP回路中回路中，即，即e13 = 0，此，此时，b2 = (5+3) + (3+6) + (4+2) + (3+4) + (2+3)/2 = 17.5，由于由于b2 = 17.5 U1 = 16，因此，因此边(1, 3)一定在回路一定在回路中，即中，即e13 = 1；(3) 在在e13 = 1的情况下
35、，的情况下，假定假定e12 = 0，此，此时b2 = (1+5) + (6+7) + (1+2) + (3+4) + (2+3)/2 = 17，由于，由于b2 = 17 U1 = 16，因此，因此边(1, 2)一定在回路中，即一定在回路中，即e12 = 1；50(4) 在在e12 = e13 = 1的情况下，由于的情况下，由于顶点点1已有两条关已有两条关联边在最在最优回路中，因此在回路中，因此在图71中中删去去边(1, 4)和和(1, 5)，由于，由于边(2, 3)与与边(1, 2)、(1, 3)形成圈形成圈，因此，因此在在图71中中删去去边(2, 3)，即此，即此时e14 = e15 = e
36、23 = 0；(5)在在e12 = e13 = 1，e14 = e15 = e23 = 0的情况下，的情况下，假定假定e25 = 1，此，此时b2 = (1+3) + (3+9) + (1+2) + (3+4) + (2+9)/2 = 18.5，由于，由于b2 = 18.5 U1 = 16，因此，因此边(2, 5)一定不在回路中，即一定不在回路中，即e25 = 0；51(6)在在e12 = e13 = 1，e14 = e15 = e23 = e25 = 0的情况下，由的情况下，由于与于与顶点点2关关联的的边有且只有有且只有2条在回路中，因此有条在回路中，因此有e24 = 1，进而有而有e35
37、= e54 = 1，e34 = 0。 至此，得到至此，得到 最最优解：解：e12 = e13 = e24 = e35 = e54 = 1，e14 = e15 = e23 = e25 = e34 = 0； 最最优目目标值：1+2+3+7+3 = 16。 522. 基于降基于降阶的分支定界法的分支定界法 对于于有向有向TSP的距离距的距离距阵，可通，可通过不同情况下不同情况下上下界的上下界的对比来确定某些比来确定某些边(i, j)一定在或不在回路一定在或不在回路中。如果能确定中。如果能确定(i, j)一定在回路中，由于每个一定在回路中，由于每个顶点点分分别有且只有一条入有且只有一条入边和出和出边，
38、从而可确定，从而可确定顶点点i的的其它出其它出边一定不在回路中，也可以确定一定不在回路中，也可以确定顶点点j的其它的其它出出边一定不在回路中，因此可将一定不在回路中，因此可将这些些边从距离距从距离距阵中去掉，从而达到中去掉，从而达到降低矩降低矩阵阶数数的目的。的目的。 这里，以一个具体的例子来予以里，以一个具体的例子来予以说明。明。53例例2 已知有向已知有向TSP的距离矩的距离矩阵如下：如下：54解解: 由于每个由于每个顶点都必点都必须有一条入有一条入边和出和出边，因此，因此将将顶点点i的所有出的所有出边的的权值减去所有出减去所有出边权值的最小的最小值min_out(i)，不会影响最，不会影
39、响最优解，解，仅最最优值在原来的基在原来的基础上减少了上减少了min_out (i)。 于是，可以将距离矩于是，可以将距离矩阵的每一行和每一列都减的每一行和每一列都减去去该行或行或该列的最小列的最小值，直至每行每列都含有，直至每行每列都含有0为止。止。 将上述矩将上述矩阵的每行分的每行分别减去减去该行的最小行的最小值3, 4, 16, 7, 25, 3，就得到如下，就得到如下缩减之后的矩减之后的矩阵：55 该缩减矩减矩阵所所对应TSP的最的最优解与原来的相同，但最解与原来的相同，但最优值比原来减少了比原来减少了3+4+16+7+25+3 = 58。 由于矩由于矩阵中第中第3、4列中不含列中不含
40、0元素，因此可元素，因此可继续缩减成：减成：56该缩减矩减矩阵所所对应TSP的最的最优解与原来的相同，但最解与原来的相同，但最优值比原来减少了比原来减少了3+4+16+7+25+3 = 58。由于矩由于矩阵中第中第3、4列中不含列中不含0元素，因此可元素，因此可继续缩减成：减成：57 其最其最优值比原来减少比原来减少58+15+8 = 81，这个个81可可作作为该TSP初始的下界初始的下界值b。58按按e63 = 1和和e63 = 0将解分成两种情况：将解分成两种情况：(1)e63 = 0 此此时，边(6, 3)不能出不能出现在回路中，其在回路中，其权值在在这种情况下种情况下为，因此，距离矩，
41、因此，距离矩阵可修改可修改为：59 由于第由于第3列没有列没有0元素，故用第元素，故用第3列各元素减去列各元素减去其最小元素其最小元素48，得如下，得如下缩减矩减矩阵： 此时的下界此时的下界 b = 81 + 48 = 129。60(2)e63 = 1 此此时，边(6, 3)已出已出现在回路中，从在回路中，从顶点点6出出发的其它的其它边都不可能在回路中，因此可都不可能在回路中，因此可删去第去第6行行；同理，同理，进入到入到顶点点3的其它的其它边都不可能在回路中，都不可能在回路中，因此又可因此又可删去第去第3列列。此。此时，边(3, 6)不可能出不可能出现在在回路中，令回路中，令边(3, 6)的
42、的权值为，矩，矩阵化化为：61继续依次计算，并实施分继续依次计算，并实施分支和定界，具体过程如图支和定界，具体过程如图73所示：所示：图图73 降阶分支定界过程降阶分支定界过程b = 81e63 =0e63 =1b =129e46 =0e46 =1b =113e21 =0e21 =1b =81b =81b =84b =101e14 =1e14 =0b = 84b =112得可行回路(1,4,6,3,5,2,1), 回路总长104，由此可将下界b大于104的分支剪去。62e63 = 1，e46 = 0下的下的缩减矩减矩阵： 63e63 = e46 = 1下的下的缩减矩减矩阵：64e63 = e4
43、6 = 1，e21 = 0下的下的缩减矩减矩阵：65e63 = e46 = e21 = 1下的下的缩减矩减矩阵：66e63 = e46 = e21 = 1，e14 = 0下的下的缩减矩减矩阵：67e63 = e46 = e21 = e14 = 1下的下的缩减矩减矩阵：68e63 = e46 = 1，e21 = e51 = 0下的下的缩减矩减矩阵：69e63 = e46 = e51 =1，e21 = 0下的下的缩减矩减矩阵：70e63 = e46 = e51 = 1，e21 = e14 = 0下的下的缩减矩减矩阵：71e63 = e46 = e51 = e14 = 1，e21 = 0下的下的缩减
44、矩减矩阵：72 最后可得到两个最最后可得到两个最优TSP回路：回路：(1, 4, 6, 3, 2, 5, 1) 和和 (1, 4, 6, 3, 5, 2, 1)，最，最优回路回路长度度为104。 若将无向若将无向图中的每条中的每条边看成有向看成有向图中方向相反中方向相反的两条的两条边，则无向无向图也可看成是有向也可看成是有向图，因此，基，因此，基于降于降阶的分支定界法也可用来求解无向的分支定界法也可用来求解无向TSP问题。73三、动态规划法定理定理1 TSP满足足最最优性原理性原理。 最最最最优优化化化化原原原原理理理理可可以以表表述述为：“一一个个过程程的的最最优策策略略具具有有这样的的性性
45、质,即即无无论初初始始状状态和和初初始始决决策策如如何何,对于于先先前前决决策策所所形形成成的的状状态而而言言,其其以以后后的的所所有有决决策策必构成最必构成最优策略，策略，”74证： 设s, s1, s2, , sp, s是从是从s出出发的一条的一条总长最短的最短的简单回路，假回路，假设从从s到下一个城市到下一个城市s1已已经求出，求出，则问题转化化为求从求从s1到到s的最短路径，的最短路径，显然然s1, s2, , sp, s一一定构成一条从定构成一条从s1到到s的最短路径。若不然，的最短路径。若不然，设s1, r1, r2, , rq, s是一条从是一条从s1到到s的最短路径且的最短路径
46、且经过n-1个不同个不同城市，城市，则s, s1, r1, r2, , rq, s将是一条从将是一条从s出出发的路径的路径长度最短的度最短的简单回路且比回路且比s, s1, s2, , sp, s要短，从而要短，从而导致矛盾。所以，致矛盾。所以，TSP满足最足最优性原理。性原理。75 设TSP顶点点编号分号分别为0，1，2，n，假，假设从从顶点点0出出发，令，令d (i, V )表示从表示从顶点点 i 出出发经过V 中各中各顶点一次且点一次且仅一次，最后回到出一次，最后回到出发点点0的最短路的最短路径径长度，中度，中间计算算过程中的程中的d (k, Vk)也表示从也表示从顶点点 k 出出发经过
47、Vk 中各中各顶点一次且点一次且仅一次，一次，最后回到出最后回到出发点点0（注意不是（注意不是k）的最短路径）的最短路径长度。度。开始开始时，V = Vi，cij为顶点点 i 至至顶点点 j 的距离，的距离，于是，于是，TSP的的动态规划划递推函数可写成：推函数可写成：76d (i, V ) = min cik + d (k, Vk) ( kV )d (k, ) = ck 0 ( k 0 )例例3 求解有向求解有向TSP：77解：解： 从城市从城市0出出发经城市城市1、2、3然后回到城市然后回到城市0的最的最短路径短路径长度度为：d (0, 1, 2, 3) = min c01 + d (1,
48、 2,3), c02 + d (2, 1,3), c03 + d (3, 1, 2)这是最后一个是最后一个阶段的决策，而段的决策，而d (1, 2, 3) = min c12 + d (2, 3), c13 + d (3, 2)，d (2, 1, 3) = min c21 + d (1, 3), c23 + d (3, 1)，d (3, 1, 2) = min c31 + d (1, 2), c32 + d (2, 1)；这一一阶段的决策又依段的决策又依赖于下述于下述计算算结果：果：78d (1, 2) = c12 + d (2, )， d (2, 3) = c23 + d (3, )， d
49、(3, 2) = c32 + d (2, )， d (1, 3) = c13 + d (3, )， d (2, 1) = c21 + d (1, )， d (3, 1) = c31 + d (1, )；而下式可以直接而下式可以直接获得（括号中是得（括号中是该决策引起的状决策引起的状态转移）：移）：d (1, ) = c10 = 5 (10)，d (2, ) = c20 = 6 (20)，d (3, ) = c30 = 3 (30)； 79再向前倒推，有：再向前倒推，有：d (1, 2) = c12 + d (2, ) = 2 + 6 = 8 (12)，d (1, 3) = c13 + d (3
50、, ) = 3 + 3 = 6 (13)， d (2, 3) = c23 + d (3, ) = 2 + 3 = 5 (23)，d (2, 1) = c21 + d (1, ) = 4 + 5 = 9 (21)，d (3, 1) = c31 + d (1, ) = 7 + 5 = 12 (31)，d (3, 2) = c32 + d (2, ) = 5 + 6 = 11 (32)；80再向前倒推，有：再向前倒推，有：d (1, 2, 3) = min c12 + d (2, 3), c13 + d (3, 2) = min 2+5, 3+11 = 7 (12)，d (2, 1, 3) = mi
51、n c21 + d (1, 3), c23 + d (3, 1) = min 4+6, 2+12 = 10 (21)，d (3, 1, 2) = min c31 + d (1, 2), c32 + d (2, 1) = min 7+8, 5+9 = 14 (32)； 81最后有：最后有： d (0, 1, 2, 3) = min c01 + d (1, 2, 3), c02 + d (2, 1, 3), c03 + d (3, 1, 2) = min 3+7, 6+10, 7+14 = 10 (01)。即，从即，从顶点点0出出发的的TSP最短回路最短回路长度度为10，回路路径，回路路径为：01
52、230。82四、近似算法 由于精确式算法所能求解的由于精确式算法所能求解的问题规模非常有限，模非常有限，实际中真正使用的往往都是多中真正使用的往往都是多项式式阶数的近似算法数的近似算法或启或启发式算法，算法的好坏用式算法，算法的好坏用C/C*来衡量，其中，来衡量，其中，C为近似算法所得的近似算法所得的总行程，行程，C*为最最优总行程，行程，为最最“坏坏“情况下近似与最情况下近似与最优总行程之比所不超行程之比所不超过的的上界上界值。这里，列里，列举几个常几个常见的的TSP快速近似算法。快速近似算法。83 旅行售货员问题的一些特殊性特殊性质： 比如，费用函数w往往具有三角不等式性三角不等式性质，即
53、对任意的3个顶点u,v,wV，有：w(u,w)w(u,v)+w(v,w)。当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数w就具有三角不等式性质。 对于给定的无向图G，可以利用找图图G的最小生的最小生成树成树的算法设计找近似最优的旅行售货员回路的算法。 84 当费用函数满足三角不等式时，算法当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的旅行售货员回路费用的2倍。倍。 void approxTSP (Graph g) (1)选择g的任一顶点r； (2)用Prim算法找出带权图g的一
54、棵以r为根的最小生成树T； (3)前序遍历树T得到的顶点表L； (4)将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回； 85(b)表示找到的最小生成树表示找到的最小生成树T；(c)表示对表示对T作前序遍历的次序；作前序遍历的次序；(d)表示表示L产生的哈密顿回路产生的哈密顿回路H；(e)是是G的一个最小费用旅行售货的一个最小费用旅行售货员回路。员回路。 为什么：为什么：当费用函数满足三角不等式时，当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的最优旅行售货员回路费用的2倍。倍。86答：答：存在一个
55、最存在一个最优TSP回路回路TSPOPT， TSPOPT中共有中共有n条条边，现去掉去掉TOPT中最中最长的一条的一条边，得路径，得路径POPT， POPT中共有中共有n-1条条边，其，其总权值之和之和WTSP大于等于最小生成大于等于最小生成树的的总权值之和之和WT；即；即WTSP WT,下面只需下面只需证明明该算法求得的算法求得的TSP回路回路总长度之和度之和WA小于等于小于等于2WT即可；即可； 把最小生成把最小生成树中的中的边重复一次，再根据三角不等式就可重复一次，再根据三角不等式就可得出得出结论（多次利用三角不等式）。（多次利用三角不等式）。 为什么：为什么：当费用函数满足三角不等式时
56、，当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的最优旅行售货员回路费用的2倍。倍。87 把最小生成树中的边重复一次，再根据三角不等式就可把最小生成树中的边重复一次，再根据三角不等式就可得出结论（多次利用三角不等式）。（得出结论（多次利用三角不等式）。（d）中蓝色的边为原）中蓝色的边为原来不在最小生成树中的边，最小生成树中的边重复一次及不来不在最小生成树中的边，最小生成树中的边重复一次及不在在(d)中，但在中，但在(b)中的边反复利用三角不等式就可得出结论。中的边反复利用三角不等式就可得出结论。881. 插入算法插
57、入算法插入型算法可按插入插入型算法可按插入规则的不同而分的不同而分为若干若干类，其一般思想，其一般思想为：Step 1. 通通过某种插入方式某种插入方式选择插入插入边( i, j ) 和插入点和插入点 k，将，将 k 插插入入 i 和和 j 之之间, 形成形成, i, k , j ,。Step 2. 依次依次进行，直至形成回路解。行，直至形成回路解。适用范适用范围：对称型称型TSP。具体具体实施中，可将出施中，可将出发点取遍点取遍V中各点而得到多个解，并从中中各点而得到多个解，并从中选择最好的一个，但此最好的一个，但此时的的时间复复杂度增加了度增加了n倍。倍。 主要的插入型算法有：主要的插入型
58、算法有：89(1) 最近插入法最近插入法最坏情况：最坏情况：= 2； 时间复复杂度：度：O (n2)。(2) 最小插入法最小插入法最坏情况：最坏情况：= 2； 时间复复杂度：度：O (n2 lg n) 。(3) 任意插入法任意插入法最坏情况：最坏情况：= 2 1g n + 0.16； 时间复复杂度：度：O (n2)。(4) 最最远插入法插入法最坏情况：最坏情况：= 2 1g n + 0.16； 时间复复杂度：度：O (n2)。(5) 凸核插入法凸核插入法最坏情况：最坏情况：= 未知；未知； 时间复复杂度：度：O (n2lg n)。90插入法插入法(Insertion Method)1 任任选一
59、一节点点为起点起点a；2 寻找距离找距离节点点a最近的最近的节点点b作作为下一个造下一个造访的的节点，点，形成形成a-b-a的子回路；的子回路；3 寻找距离子回路最近的找距离子回路最近的节点点k作作为下一个插入点；下一个插入点；4 寻找插入成本最小的位置找插入成本最小的位置(i-j)，将，将k插入插入i-j之之间，形，形成新的子回路；成新的子回路； 插入成本：插入成本：Cik+Ckj-Cij5 重复步重复步骤34，直到所有，直到所有节点均已插入回路之中，点均已插入回路之中，即形成一个即形成一个TSP的可行解。的可行解。91插入法插入法142357438755348141413333733373
60、17224525727421455885845455582145541 任选一节点为起点任选一节点为起点a；2 寻找距离节点寻找距离节点a最近的节点最近的节点b作为下一个造访的节点，作为下一个造访的节点，形成形成a-b-a的子回路；的子回路；3 寻找距离子回路最近的节点寻找距离子回路最近的节点k作为下一个插入点；作为下一个插入点；4 寻找插入成本最小的位置寻找插入成本最小的位置(i-j)，将，将k插入插入i-j之间，形成之间，形成新的子回路；新的子回路； 插入成本：插入成本：Cik+Ckj-Cij5 重复步骤重复步骤34，直到所有节，直到所有节点均已插入回路之中，即点均已插入回路之中，即形成一
61、个形成一个TSP的可行解。的可行解。922. 最近最近邻算法算法Step 1.任取一出任取一出发点。点。Step 2.依次取最近的点加入当前解中，直至形成回依次取最近的点加入当前解中，直至形成回路解。路解。适用范适用范围：对称型称型TSP。 具体具体实施中，可将出施中，可将出发点取遍点取遍V中各点而得到多中各点而得到多个解，从中个解，从中选择最好的一个，但此最好的一个，但此时的的时间复复杂度度增加了增加了n倍。倍。最坏情况：最坏情况：= (1g n + 1)/2； 时间复复杂度：度：O (n2)。93最近邻点法最近邻点法(Nearest-neighbor Heuristic)1 任任选一一节点
62、点为起点起点x；2 寻找距离找距离节点点x最近的最近的节点点y作作为下一个造下一个造访的的节点；点；3 寻找距离找距离节点点y最近的最近的节点点z作作为下一个造下一个造访的的节点；点；4 重复以上步重复以上步骤，直到所有，直到所有节点均已点均已访问；5 连接最后一个接最后一个节点与起点，即形成一个点与起点，即形成一个TSP的可行的可行解；解；94最近邻点法最近邻点法14235743875534814235123451 473824 755377 344353 858548953. 双生成双生成树算法算法Step 1.首先求出最小生成首先求出最小生成树。Step 2.将将树中各中各边都添一重复都
63、添一重复边形成形成Euler图，并求，并求出其出其Euler回路。回路。Step 3.在在Euler回路点序列中去除重复点，形成回路点序列中去除重复点，形成TSP回路解。回路解。适用范适用范围：对称型称型TSP。最坏情况：最坏情况：= 2； 时间复复杂度：度：O (n2)。964 Christofides算法算法Step 1.首先求出最小生成首先求出最小生成树。Step 2.对树中所有奇中所有奇顶点求解最小点求解最小权匹配匹配问题。Step 3.将匹配将匹配边添入生成添入生成树，并求出其，并求出其Euler回路。回路。Step 4.在在Euler回路点序列中去除重复点，形成回路点序列中去除重复
64、点，形成TSP回路解。回路解。适用范适用范围：对称型称型TSP。最坏情况：最坏情况：= 3/2； 时间复复杂度：度：O (n3)。975. r-opt 算法算法 该方法是一种局部改方法是一种局部改进搜索算法，由搜索算法，由Lin等人（等人（1965）提出，）提出，其核心思想就是其核心思想就是对给定的初始回路，通定的初始回路，通过每次交每次交换 r 条条边来来改改进当前的解。当前的解。适用范适用范围：对称型称型TSP。显然，然，对不同的不同的r，其，其优劣次序劣次序为：2-opt，3-optr-opt。 但是，大量但是，大量计算算发现，3-opt比比2-opt好，而好，而4-opt、5-opt等
65、等却并不比却并不比3-opt来得来得优越，况且越，况且r越大，运算越大，运算时间越越长。 对于于3-opt，有一个，有一个经验公式告公式告诉我我们，其求得最，其求得最优解的解的概率近似概率近似为2- n/10，例如，例如，对于于n = 50, 有有 p = 2- 50/10 = 0.03，即，只要随机，即，只要随机选取取150条初始路条初始路线，则求得最求得最优解的概率解的概率可达可达0.99。 迄今迄今为止，止，3-opt法仍是一种相当有效的近似算法。法仍是一种相当有效的近似算法。 最坏情况最坏情况: = 2 (n8, rn/4) ； 时间复复杂度：度：O (nr )。986. 混合算法混合
66、算法 用某个近似算法求得初始解，然后借助一个或用某个近似算法求得初始解，然后借助一个或若干个若干个r-opt算法算法对解加以改解加以改进。这种混合型的算法种混合型的算法往往能往往能获得得较好的解，但同好的解，但同时也很耗也很耗时，一般，一般仅在在对解有解有较高要求高要求时采用。采用。992-opt 交換法先构建一个起始可行解先构建一个起始可行解在可行解中任在可行解中任选两个不相两个不相邻的的节线(a b, c d)，以及另外两条以及另外两条对应之替之替换节线(a c, b d)，计算替算替换后后总成本是否降低成本是否降低 (即即检查替替换成本成本是否小于是否小于0)。替替换成本：成本：Cac+
67、Cbd-Cab-Ccd (对称型称型TSP) 若替若替换后后总成本有降低，成本有降低，则予以替予以替换，同，同时变更中更中间相关弧相关弧线的行走方向。的行走方向。重复步重复步骤23，直到所有可能的替，直到所有可能的替换均无法再降低均无法再降低成本成本为止止1002-opt 交換法142357438755348101如：如：98年全国数学建模竞赛题年全国数学建模竞赛题B题是题是TSP问题问题的一个变形的一个变形 从从县城出城出发分三个小分三个小组巡巡视受灾的地区受灾的地区各地的灾情，已知每个村各地的灾情，已知每个村镇所需要的停留所需要的停留时间以及行以及行车速度，速度，问如何如何设计各各组的巡的巡视路路线才能以最快的速度掌握整个地区全部的受才能以最快的速度掌握整个地区全部的受灾情况？灾情况？102灾情巡视路线灾情巡视路线(CUMCM-1998B)多人TSP问题的扩展103考虑用一个考虑用一个3 3个结点来代替县城结点，个结点来代替县城结点，将问题转化为一个将问题转化为一个TSPTSP问题：问题：
