6旅行推销员问题的几种解法-王荣荣.doc

论文题目： 旅行推销员问题的几种解法 院 系： 数学科学学院 专 业： 应用数学 姓 名： 王荣荣 学 号： 02211044 指导教师： 郭爱萍 完成时间： 2005年5月16号 旅行推销员问题的几种解法王荣荣（包头师范学院数学科学学院）摘要：通过提出“旅行推销员问题traveling salesman problem”来介绍如何求解与生活息息相关的机床运行问题。最优哈密顿回路是“旅行推销员问题”的最优解，也是机床运行问题的最佳选择。关键词：旅行推销员问题，最优哈密顿回路，最优推销员回路。KEY WORD：traveling salesman problem，optimum Hamilton circuit，optimum salesman circuit.中图分类号：O1一个旅行推销员在返回他所在的城市之前，他要访遍上司安排他去的所有城市。我们如何能找到一条路线，使推销员以最小的总路程（或时间，旅费）访遍这些城市，最后再回到他所在的城市。这就是著名的“旅行推销员问题”。这个问题可以用图论语言说的更广义一些，“旅行推销员问题“就是在给定的连通加权图（G，W）。其中G的顶点视为各个城市，城市间的航线视为边，权视为两个城市间的踞离，也可以视为时间或旅费。 旅行推销员问题我们在实际工作中和理论研究中经常会遇到。在此我选取一个比较典型又实用的例子来求其最优哈密顿回路。例1:某一机械车间，每一工件可以不按顺序地但必须走遍n台不同机床的每一台。记这n台不同机床为v1,v2vn.然而，只要工件从机床vi到机床vj就需要调整时间tij。现在我要利用“旅行推销员问题“来确定每一工件走遍n台不同机床的最快路线。设连通加权无向图(G,W),即为本例的流程图。至少包含图G中每一个顶点的一次的回路称之为推销员回路（salesman circuit），而包含图G中每一个顶点只有一次的回路称之为哈密顿回路（Hamiltonian circuit），具有最小总长度的推销员回路称之为最优推销员回路（optimum salesman circuit），而且也是一般推销员问题的最优解。具有最小总长度的哈密顿回路称之为最优哈密顿回路（optimum Hamiltonian circuit），而且也是推销员问题的最优解。最优推销员回路不一定是最优哈密顿回路。例如：见下面所示的图。这个图的唯一的哈密顿回路是（a，b），（b，c），（c，a），总长度等于1+20+1=22。而通过顶点a点两次的最优推销员回路（a，b），（b，a），（a，c），（c，a）的总长度等于1+1+1+1=4。因此，最优推销员回路不一定是最优哈密顿。那什么情况下一般推销员问题的解才是哈密顿回路呢？a1 11 1 b 20 c 定理：如果图G中每一对x，y都存在a（x，y）a（x，z）+a（z，y）（对所有z不等于x，z不等于y）(1) 那么哈密顿回路就是图G一般推销员问题的最优解(如果存在的话)。（参见网络和图的最优化算美E.米涅尔 著 李家滢 赵关旗 译）从定理我们可以看出，如果图G满足三角不等式，那么图G推销员问题的最优解就是图G一般推销员问题的最优解。但遗憾的是并不是所有的图都具有哈密顿回路。因此，我们应该确定所研究的图是否具有哈密顿回路。（更详尽的关于哈密顿回路存在条件的分析可以参阅伯奇（Berge）1973专著）。下面我采用一种数学建模中用过的方法来求解上面提出的关于机床运行的问题。设n=5，5个不同的机床间调整时间用矩阵D表示如下：V1V2V3V4V5D=(tij)5*5 = V1 V2 V3 V4 V5其中tij表示vi到vj的调整时间。上面的矩阵是对称的，即从vi到vj的调整时间等于从vj到vi的调整时间。（此方法也可用于非对称型矩阵）每行抽取最小的元素，并令矩阵D的每行的所有元素都减去该行的最小元素，得：32211D1=再用D1各列的所有元素减去该列的最小元素，得：10=3+2+2+1+1+1D2=重要的结论在于以D为调整时间矩阵问题的解和以D2为调整时间的解是一样的。每行的所有元素减去该行的最小元素，相当于从该行所对应的机床到其它不同机床的调整时间一律减少，减少的时间量是相同的。每列的所有元素减去该列的最小元素，可看做是该列所对应的机床到其它不同机床的调整时间一律减少，而且减少的时间量是相同的。工件进入每个机床一次且仅一次，而且从该机床出去一次，也仅有一次。最佳路径仍是减少调整时间后的最佳路径。这就证明了我们的结论，反正进出都一次。下面讨论以D2为调整时间矩阵问题的解。D2的特点是每行每列都有零元素至少一个。例如：从v1出发必然选择v3作为下一站，因t13=0。在D2矩阵中划去t13元素所在的行和列，并将t13改为，这样是为了避免出现v1 v3 v1的现象，这不符合问题的要求。消去第一行及第三列的原因在于每点进出仅一次。10V2V3V4V5D3= V1 V2 V4 V5在矩阵D3中第一行无零元素出现，该行所有元素减去最小元素，得：12=10+2V2V3V4V5V1 V2 V4 V5V3的下一站必然是选V2了，因t32=0，t32所在的行和列去掉，t32改为。同时t21也改为，t32改为是避免v3 v2 v3，但t21改为是为了避免v1 v3 v2 v1，这也不符合旅行推销员问题的要求，得：V2V4V5D4= V1 V4 V5 同样D4的第一行减去第一行的最小元素5，第一列也减去第一列的最小元素2，得：V2V4V519=12+5+2D5= V1 V4 V5V2的下一站自然选V5，依上述办法得：V4V519 D6= V1 V4 故得一条路径v1 v3 v2 v5 v4 v1，总调整时间为19是否为最佳呢？以开始时v1 v3为例，若不取v1 v3究竟如何呢？若封锁v1 v3，在D2中令t13=可得10D7= 第一行减去该行的最小元素2，得：12=10+2V1V2V3V4V5 12是它的界，即封锁v1 v3后调整时间的下界，而下界也比v1 v3的调整时间长，所以只能取v1 v3。依此方法，我们可知所求得的路径是最佳路径。下面介绍另一种解决问题的方法：设G=(V,A)表示我们所研究的图。我们可以用最小费用流算法求得图G中最短哈密顿回路长度的下界L1（最小费用流算法参见网络和图的最优化算法第102页）,如果用最小费用流算法求得的流符合图G的一个回路，那么这个回路就是一个最优哈密顿回路，同时也就解决了推销员问题。但是，在任意实际的图中，有可能最终流相对应于拆开的回路。选择这些回路中的一个回路，并把包含在这个回路中的所有顶点表示为Vc=v1,v2,vk.在一个最优解中，工件离开顶点v1后,或通过不在Vc中的某个顶点，或通过Vc中的某一顶点。当是后者情况时，在工件离开顶点v2后，又有可能去不在Vc中的另一个顶点，或去在Vc中的另一个顶点，如此等等。所以最优解一定可以至少存在于下述各图的某一个图中。1 图G具有所有被删去的弧(v1,x),xVc2 图G具有所有被删去的弧(v2,x),xVc ，以及具有所有被删去的弧（v2，y），yVc3 图G具有所有被删去的弧(v1,x),(v2,x),xVc，以及具有所有被删去的弧（v3，y），yVc . . 。 。 。 。k图G具有所有被删去的弧(v1,x),(v2,x)(vk-1),xVc，以及具有所有被删去的弧（vk，y），yVc（注：删去一条弧等于给它一个无穷大的长度）分别称上述各图为G1,G2Gk.由于在每个带下标图Gi中一条弧的长度不会小于在图G中相应弧的长度，在图Gi中的一个最优哈密顿回路长度也不可能小于图G中的一个最优哈密顿回路的长度。而且,图G的一个最优解至少也是带下标的图G1,G2Gk这些图的一个最优解。其次，利用最小费用流算法求出每一个图G1,G2Gk的一个最优哈密顿回路长度的下界。分别称每一个图所得的下界为L1（G1），L1（G2）L1（Gk）。如果在某一个下标图Gc中的最小费用流相对应于一个哈密顿回路时，我们就需要再往下考虑任何其它的L1（Gi）L1（Gc）的下标图Gj。因为L1（Gc）已经是所需达到的下界。这样，我们就可以删去好几个下标图的研究。然后把剩下的不能删去的每一个下标图Gi重复上述过程并用图Gi1，Gi2来代替,计算每一个图Gij的一个最优哈密顿回路长度的下界L1(Gij),并如上一样,再删去尽可能多的双下标图.最终,能够找到一个其中具有最短的哈密顿回路的图,这个图将删去其它所有的图.这个哈密顿回路就一定是原图G的一个最短哈密顿回路.由于这种方法是从原图向其它一些图上分支,以及沿着每一条分支形成一个最优解的界限,所以这种方法就称之为分支界限求解法(branch and bound solution technique).下面举一个连通加权有向图的例子例;用分支界限求解法求解图G的最优哈密顿回路.由于图G较小我们立即可以看出,对于图G用最小费用流算法可以求出两个回路(V1,V2),(V2,V3),(V3,V1)与(V6,V5)(V5,V4),(V4,V6).这两个回路的总长度都是11.因此,L1(G)=11.对于第一个回路,利用顶点Vc=V1,V2,V3,我们可以得出如图G所示的三个图Ga,Gb,Gc.图Ga是从图G中删去从V1到V2或V3的一切弧,也即删去弧(V1,V2)所形成的图.图Gb是从图G中删去所有从V1到V4,V5,V6和从V2到V1和V3的弧所形成的图.因此图Gb就是图G中删去弧(V1,V4)与(V2,V3)所形成的图.图Gc则是删去所有从V1和V2到V4,V5,V6,以及从V3到V1和V2的弧后的图G,也就是删去弧(V1,V4),(V2,V4)与(V3,V1)后的图G.由于Ga,Gb与Gc较小,我们能够立即看出:最小费用流算法可以得出下列回路:图 回路 下界 L1Ga (V1,V4),(V4,V6),(V6,V5),(V5,V2),(V2,V3),(V3,V1) L1(Ga)=21 Gb (V1,V2),(V2, V5),(V5,V4),(V4,V6),(V6,V3),(V3,V1) L1(Gb)=12 Gc (V1,V2),(V2, V3),(V3,V6),(V6,V5),(V5,V4),(V4,V1) L1(Gc)=16图Gb的最小费用流法求得长度等于12的哈密顿回路.因而图Ga与图Gc,由于它们的下界都超过L1(Gb)=12,所以进一步研究时就可以删去.所以哈密顿回路(V1,V2),(V2,V5),(V5,V4),(V4,V6),