数学建模经典问题——旅行商问题

1第7章旅行商问题2第7章旅行商问题1.问题概述2.求解算法2.1.下界和上界算法2.2.分支定界法目录2.5.竞赛题2.3.动态规划法2.5.近似算法3§7-1问题概述一、数学模型1.标准TSP旅行商问题（简称TSP），也称货郎担问题或旅行推销员问题，是运筹学中一个著名的问题，其一般提法为：有一个旅行商从城市1出发，需要到城市2、3、…、n去推销货物，最后返回城市1，若任意两个城市间的距离已知，则该旅行商应如何选择其最佳行走路线？4TSP在图论意义下又常常被称为最小Hamilton圈问题，Euler等人最早研究了该问题的雏形，后来由英国的Hamilton爵士作为一个悬赏问题而提出。但这个能让普通人在几分钟内就可理解的游戏之作，却延续至今仍未能完全解决，成了一个世界难题。TSP有着明显的实际意义，如，邮局里负责到各信箱开箱取信的邮递员，以及去各分局送邮件的汽车等，都会遇到类似的问题。有趣的是，还有一些问题表面上看似乎与TSP无关，而实质上却可以归结为TSP来求解。已经证明，TSP是个NP难题，除非P=NP，否则不存在有效算法。5记为赋权图G=(V,E)，V为顶点集，E为边集，各顶点间的距离dij已知。设1,,0,ijijx若在回路路径上其他则经典的TSP可写为如下的数学规划模型：1111min1,(71)1,(72)s.t1,,21(73)0,1nnijijijnijjnijiijiSjSijZdxxiVxjVxSSVSnx61111min1,(71)1,(72)s.t1,,21(73)0,1nnijijijnijjnijiijiSjSijZdxxiVxjVxSSVSnx模型中，为集合中所含图的顶点数。约束（7－1）和（7－2）意味着对每个点而言，仅有一条边进和一条边出；约束（7－3）则保证了没有任何子回路解的产生。于是，满足约束（7－1）、（7－2）和（7－3）的解构成了一条Hamilton回路。7当dij=dji(i,j∈V)时，问题被称为对称型TSP，否则称为非对称型TSP。若对所有1≤i,j,k≤n，有不等式dij+djk≥dik成立，则问题被称为是满足三角形不等式的，简称为ΔTSP。82.扩展TSP(1)瓶颈TSP瓶颈问题是最早从TSP延伸出来的一种扩展型TSP，其含义与经典的TSP类似，仅目标不同，要求巡回路线中经过的最长距离最短，即最小化瓶颈距离。该情形体现了那些并不追求总巡回路线最短，而只希望在巡回路线中每次从一个地点至另一个地点的单次行程尽可能短的实际应用问题的特征。9从严格的数学意义而言，瓶颈TSP（简称BTSP）并没有降低问题的难度，也未能提供任何特殊的解决办法。瓶颈TSP的数学模型与标准TSP类似，仅目标函数不同：minZmax,ijijdxijV由于目标函数为瓶颈值，故求得的最佳巡回路线与标准TSP的往往截然不同。10(2)最小比率TSP最小比率TSP（简称MRTSP）是从经典TSP引申出来的另一个变形问题，假定从一个城市走到另一个城市可得到某种收益（记为），则MRTSP的目标就是确定最佳行走路线，使得回路的总行程与总收益之比最小。这种优化目标的思想类似于人们日常生活中经常使用的费用效益比，与单纯的总行程最短相比，往往更具实际意义。11假定收益的数学性质与相同，则最小比率TSP的数学模型也与标准TSP类似，仅目标函数不同：毫无疑问，由于目标函数中的非线性因素，最小比率TSP的求解比之标准TSP显得更为困难。minijijijijijijdxZpx12(3)多人TSP若标准TSP中，出发点有多个推销员同时出发，各自行走不同的路线，使得所有的城市都至少被访问过一次，然后返回出发点，要求所有推销员的总行程最短，则问题就成为一个多人的旅行商问题（简记MTSP）。令决策变量则MTSP的数学模型为：1,0,ijijx若有某推销员从城市到城市否则13-110-10-10min1,1,2,,1,01,1,2,,1..,00,1,0,,mnijijijnkjknikkijiiZdxjnxmjinxstmixxij对对对对且不存在任何子回路假定原问题为对称型MTSP，V={v0,v1,…vn-1}，v0为名推销员出发点，记V‘={v01,v02,…v0m;v0,v1,…vn-1}，扩大的m-1个顶点称为“人造顶点”，其距离矩阵也相应扩大，其中，位于出发点的m个顶点相互间的距离设定为∞，其他数值不变。14二、多面体理论从上世纪70年代开始的关于算法复杂性的研究表明，要想为TSP找到一个好的算法，也即多项式算法，似乎是不可能的。由于推销员的每条路线可以用一个以1开始的排列来表示，因此所有可能的路线有条。这样，若用枚举法来解决这一问题，即使不太大，例如n＝30，用目前最快的计算机，也要化几百万年才能求出一条最短的路线。15早在1954年，Dantzig等人就曾提出过一种方法（非多项式算法），并且求出了一个42城市的TSP最优解。到了1960年代，不少人用分支定界法解决了许多有几十个城市的TSP。还有人提出了一些近似方法，也解决了许多有几十个城市甚至上百个城市的TSP（有时找到的仅是近似解）。更值得注意的是，从1970年代中期开始，Grotschel与Padberg等人深入研究了TS多面体的最大面（facet），并从所得结果出发获得了一种解TSP的新算法，可以解决一些有100多个城市的TSP，且都在不长的时间内找到了最优解。16考虑个顶点的完全图Kn，则解TSP就相当于在中求一条总长度最短的Hamilton回路。现在，对每条边ej，定义一个变量xj与之对应，这样，TSP的一条路线T，即Kn的一条Hamilton回路，就可对应一个向量X={x1,x2,….xm}，其中，1,0,jjjjxeTxeT若若17称X为路线T的关联向量，其m=n(n-2)/2个分量中，恰好有个为1，其余的都为0。图有许多Hamilton回路，设为T1,T2…Ts,，对应的关联向量记为X1,X2…Xs，在m维空间Rm中，考虑这些向量生成的凸包（convexhull）Qn：111,0,1,2,,ssniiiiiiQXis18Qn是Rm中的一个凸多面体，称做TS多面体。显然，Qn是有界的，其极点正好是Kn的Hamilton回路关联向量。研究Qn的面非常重要的，因为根据线性不等式及凸多面体的理论，Qn一定是某一个有限线性不等式组的解集合，或者说，Qn一定是有限多个半空间的交。因此，如果能找出定义Qn的线性不等式组来，就可将TSP作为一个线性规划来解。19TS多面体研究中的一个重要问题就是寻找能导出Qn最大面的不等式，Grotschel等人发现了一类很重要的能导出最大面的梳子不等式，并予以了证明。此外，还有其它能导出最大面的不等式，如团树不等式等。可见，Qn的最大面极多，曾经计算过由梳子不等式所导出的最大面个数如表7－1所示：n6810203050120c(n)604142088419701.5*10181.5*103110602*10179表7－120可以看出，当增大时，最大面个数增长得非常快。在TS多面体理论的基础上，可以考虑先解TSP的松弛问题，如果得到的最优解正好是某一条路线的关联向量，那么就找到TSP的最优解了；否则，就设法找一些新的不等式作为额外约束，再解新的线性规划，直至找到恰好是关联向量的最优解。这种做法的基本思想与解整数规划的割平面法是同一类的，Gotschel等人曾用这种方法解过有120个城市的TSP，所增加的不等式只有子回路消去不等式与梳子不等式两类，在进行了13轮计算后，即解了13个线性规划后，就找到了TSP的精确最优解，每一轮的当时计算时间仅在30秒至2分钟之间。有趣的是，当n=120时，仅梳子不等式就有2*10179个，但在计算过程中，总共却只（凭经验）添加了96个子回路消去不等式与梳子不等式。21当然，用该方法有时会找不到TSP的最优解，因为很可能在进行了几轮迭代后，却找不到新的不等式。Padborg与Hong曾计算了74个TSP，其中54个得到了最优解，其余的虽未得到最优解，却得到了很好的下界，如果与近似方法配合，可以估计近似解的精确程度。如，他们解过一个有313个城市的TSP，获得一个下界41236.46，而用近似方法能得到一条长为41349的路线，于是可估计出所得近似解与最优解的误差不超过0.26%。22§7-2求解算法一、下界和上界算法1.下界（1）下界b1和b2针对TSP对应图的邻接矩阵，将矩阵中每一行最小的元素相加，就可得到一个简单的下界b1。经进一步改进，可得到更好的下界：考虑一个TSP的完整解，在每条路径上，每个城市都有两条邻接边，一条进，一条出，那么，如果把矩阵中每一行最小的两个元素相加再除以2（不失一般性，可假定图中所有距离权重都为整数），再对其结果向上取整，就可得到一个合理的下界b2。显然，b2≥b1，因此，一般不采用b1作为TSP的下界。23例1已知TSP及其距离矩阵如图7－1所示，试求其下界271563134253984(a)无向图图7－1无向图及距离矩阵(b)距离矩阵3298347524519763851324解：将矩阵中每一行最小的元素相加，1+3+1+3+2=10，即得b1=10。将矩阵中每一行最小的两个元素相加再除以2，再对结果向上取整，即可得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)长边的另一个结点的编号(其中一个结点编号为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轻易求得。通过对下界b2进行改进，可以得出一个求对称型TSP更好的下界b3。在求b2的过程中，只有当与每一结点关联的边中长度最小的两条边都出现在最优TSP回路中时，等号才成立，下面就来分析如何提高这个下界。27对结点i而言，设e(i)1与e(i)2分别为与结点i关联的边中长度最小的两条边，其长度分别为dmin(i,1)和dmin(i,2)。在对称型TSP回路中，由于有且仅有两条边与每一结点关联，因此，并不是与每个结点关联的最小两条边都能出现在最优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)或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关联边中最小的两条边之一，因此会造