旅行商问题(TSP)

参考书：1.龚劬《图论与网络最优化算法》重庆大学出版社,20092.西北工业大学数学建模指导委员会《数学建模简明教程》高等教育出版社主讲：重庆大学龚劬主要内容基本概念算法简介TSP模型的应用最佳灾情巡视路线的模型的建立与求解引例•：引例1.98年全国大学生数学建模竞赛B题“最佳灾今年(1998年)夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.情巡视路线”中的前两个问题：•：引例1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线.2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时.要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.引例公路边的数字为该路段的公里数.引例2.问题分析本题给出了某县的公路网络图，要求在不同的条件下，灾情巡视的最佳分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权图，问题就转化为图论中一类称之为旅行推销员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权（路程或时间）最小.旅行商问题(TSP，travelingsalesmanproblem)一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路线最短。•：原始问题图论模型构造一个图G=（V，E），顶点表示城市，边表示连接两城市的路，边上的权W（e）表示距离（或时间或费用）。于是旅行推销员问题就成为在加权图中寻找一条经过每个顶点正好一次的最短圈的问题，即求最佳Hamilton圈的问题。•：原始问题基本概念1)哈米尔顿路径(H路径):经过图G每个顶点正好一次的路径;2)哈米尔顿圈(H圈)；经过G的每个顶点正好一次的圈;3)哈米尔顿图(H图):含H圈的图。4)最佳H圈:在加权图G=（V，E）中，权最小的H圈；5)最佳推销员回路:经过每个顶点一次的权最小闭通路;6)TSP问题:在完备加权图中求最佳H圈的问题。•：TSP问题举例工件排序设有n个工件等待在一台机床上加工，加工完i，接着加工j，这中间机器需要花费一定的准备时间tij，问如何安排加工顺序使总调整时间最短？此问题可用TSP的方法求解，n个工件对应n个顶点，tij表示(i,j)上的权，因此需求图中权最小的H路径。计算机布线一个计算机接口含几个组件。每个组件上都置有若干管脚。这些管脚需用导线连接。考虑到以后改变方便和管脚的细小。要求每个管脚最多连两条线。为避免信号干扰以及布线的简洁，要求导线总长度尽可能小。TSP问题举例计算机布线（续）问题容易转化为TSP问题，每个管脚对应于图的顶点，d(x,y)代表两管脚x与y的距离，原问题即为在图中寻求最小权H路径。电路板钻孔MetelcoSA是希腊的一个印刷电路板（PCCB）制造商。在板子上对应管脚的地方必须钻孔，以便以后电子元件焊在这板上。典型的电路板可能有500个管脚位置，大多数钻孔都由程序化的钻孔机完成，求最佳钻孔顺序。此问题其实就是求500个顶点的完备加权图的最佳H圈的问题，即TSP问题。用求解出的H圈来指导生产，使Metclo的钻孔时间缩短了30%，提高了生产效率。算法简介TSP问题是NP-hard问题，即不存在多项式时间算法.也就是说,对于大型网络(赋权图),目前还没有一个精确求解TSP问题的有效算法，因此只能找能求出相当好（不一定最优）的解的算法.算法简介近似算法或启发式算法1.一般是以构造型算法得到一个初始解，然后再用改进型算法逐步改进。2.常见的构造型算法有两种：Christofides最小权匹配算法，对角线完全算法。3.常见的改进型算法有两种：二次逐次修正法，Feiring矩阵逐次改进法。分枝定界法算法简介二次逐次修正法（1）任取初始H圈C0=v1,v2,…,vi,…,vj,…vm,v1（2）对所有的i,j,1＜i+1＜j＜m，若w(vi,vj)+w(vi+1,vj+1)＜w(vi,vi+1)+w(vj,vj+1)则在C0中删去边（vi,vi+1）和（vj,vj+1）而加入边（vi,vj）和(vi+1,vj+1)，形成新的H圈C，即C=v1,v2,…,vi,vj,vj-1,…,vi+1,vj+1,…,vi,v1（3）C0C,重复步骤（2），直到条件不满足为止，最后得到的C即为所求。例对下图的K6,用二边逐次修正法求较优H圈.较优H圈:其权为W(C3)=19213265413vvvvvvvC分析:这个解的近似程度可用最优H圈的权的下界与其比较而得出.即利用最小生成树可得最优H圈的一个下界.设C是G的一个最优H圈，则对G的任一顶点v,C-v是G-v的生成树.如果T是G-v的最小生成树,且e1是e2与v关联的边中权最小的两条边,则w(T)+w(e1)+w(e2)将是w(C)的一个下界.取v=v3,得G-v3的一最小生成树(实线),其权w(T)=122,与v3关联的权最小的两条边为v1v3和v2v3,w(T)+w(v1v3)+w(v2v3)=178.故最优H圈的权故w(C)应满足178w(C)192.对角线完全算法结论:若能在n×n距离矩阵中找出n个不同行也不同列的元素，使它们的和为最小值。若这n个元素构成一条哈米尔顿圈时，此圈便是最佳H圈。矩阵的简化:将矩阵的每一行的各元素减去本行的最小元素称为对行简化，从第i行减去的数称为第i行的约数，记为R（i）。将矩阵的每一列的各元素减去本列的最小元素称为对列简化，从第j列减去的数称为第j列的约数，记为R’(j)。各行各列的约数之和称为矩阵的约数，记为R。矩阵经行的简化和列的简化后所得矩阵称为该矩阵的简化矩阵。对角线完全算法例求下列距离矩阵D的简化矩阵及各行，各列的约数。其中107822624509161519253017527314025DD中各行的约数R(1)=25，R(2)=5，R(3)=1，R(4)=6，R(5)=7对角线完全算法D经行简化得求出D’各列的约数R’(1)=0，R’(2)=0，R’(3)=0，R’(4)=3，R’(5)=0015620122520'18145034418015103DU对角线完全算法D’经列简化得由于简化矩阵同一行各元素减同一数，同列各元素也是减同一数，因而每个H圈的权都减少同一数即R.0153120122220''18142034418015100D对角线完全算法定理设D’是图G的距离矩阵D的简化矩阵，则D’对应的图G’的最佳（有向）H圈也是原图G的最佳（有向）H圈。G’只是边权与G不同，去掉权之后完全一样。因此当简化矩阵中的零元素构成H圈时，该H圈也是原问题的最佳H圈。罚数:在图G的距离矩阵的简化矩阵D’中，第i行的最小元素与次小元素之差称为第i行的罚数，记为P(i)。第j列的最小元素与次小元素之差称为第j列的罚数，记为P’(j)，某行（或列）的罚数即是若H圈不选择该行（或列）的最小元素会使其权增加的最小值。对角线完全算法算法步骤输入：图的距离矩阵D（1）求D的简化矩阵D’以及各行各列的约数R(i)，R’(j)，罚数P(i)，P’(j)（2）计算在简化矩阵中零元素所在行与列的罚数和，即P(i,j)=P(i)+P’(j)。将P(i,j)由大到小排列后，依次选取可作为可行部分路的边（i,j）。这些边对应的零元素记为0*。用这些选择出来的边构成可行部分路。定义一个H圈的一些不相交路径称为可行部分路。对角线完全算法（3）构造新的距离矩阵称为重构距离矩阵：按上述可行部分路的顶点序重新排列简化距离D’的行，列也按使上述所有“0*”位于对角线上的次序重新排列。（4）产生D的子阵：设重构矩阵对角线上m个非零元素对应的边为(i1,j1),（i2,j2），…，（im,jm），则从D中取出相应的m行，m列构成一个m×m子阵D1。为保证选出的边与原来的可行部分路不形成子循环，有m条边不能选择，将其对应的元素置为∞。并将列作适当调整使对角线元素为∞。（5）对D1重复（1）—（4）步，直到重构矩阵对角线上的元素全为0为止，这时便可得到一个H圈。对角线完全算法例用对角线完全法求加权图K10的较佳H圈32059084847733535743846257032027065319890150290445644590270580197281304388586806848653580464573521410462600477198197464143130191388608335902815731436020362568357150304521130601403085204382903884101912001401984184624455864623883623081982205706448066006085684204182201098765432110987654321D对角线完全算法12345678910RiPi1∞019830034838811651942412022011620∞01101641900321247341980325658∞060516181150681406443824880∞0701971779067606754863021400∞8324915430456030645625861013∞700681171300716852011116354∞103243208410528587389191107840119∞73163197739532355200600108299113∞09001022814211837151572642030∞32015Rj2200000264670230Pj168520005161033034对角线完全算法2求出以上第一级简化阵中零元素对应的罚数，如P(1，2)=P(1，2)=P(1)+P′(2)=116+52=168，并将这些罚数按由大到小的次序排列如下：P（1，2）=168,P（2，1）=168,P（8，6）=124P（6，8）=103,P（4，5）=67,P（7，3）=52P（10，9）=45,P（9，10）=34,P（5，4）=30P（2，7）=6,P（3，4）=6,P（2，3）=0P（6，4）=0,P（9，5）=0对角线完全算法现依次从上述各边选择能形成可行部分路的边，先选第一边（1，2），之后（2，1），（2，1）不行，因（1，2），（2，1）形成子循环；接着(8，6),但（6，8）不行，（6，8）会与（8，6）构成子循环；再下是(4,5),(7,3),(10,9)，但(9,10)不能入选；(5,4)也不能入选，因会和前面选中的(4,5)构成子循环；接着是(2,7),(3,4),但(2,3)不能入选，否则与(2,7)会使2的出次大于1。同理（6，4），（9，5）也不能入选。综上得到可形成可行部分路的边为：(1,2),(8,6),(4,5),(7,3),(10,9),(2,7)和(3,4)。它们对应的零元素为0*。可行部分路：1-2-7-3-4-5，8-6和10-9，三条不相交路径。对角线完全算法2734586109110*20*70*30*40*528180·6477100·96443.以1，2，7，3，4，5，8，6，10，9的顺序重新排列D′的行，为使所有0*位于对角线上，D′的列按2，7，3，4，5，8，6，10，9，1的顺序排列，这样便得到第一级重构距离矩阵对角线完全算法4.对角线上有三个非零元素281，477和644，其对应的边为：（5，8），（6，10