旅行商问题(TSP)(精选PPT)课件.ppt

1、主讲：重庆大学 龚劬1主要内容基本概念算法简介TSP模型的应用最佳灾情巡视路线的模型的建立与求解引 例2： 1. 98 1. 98年全国大学生数学建模竞赛年全国大学生数学建模竞赛B B题题“最佳灾最佳灾 今年今年(1998(1998年年) )夏天某县遭受水灾夏天某县遭受水灾. . 为考察灾情、为考察灾情、组织自救，县领导决定，带领有关部门负责人到组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视全县各乡（镇）、村巡视. . 巡视路线指从县政府巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线府所在地的路线. .情巡

2、视路线情巡视路线”中的前两个问题：中的前两个问题：3： 1 1）若分三组（路）巡视，试设计总路程最）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线短且各组尽可能均衡的巡视路线. . 2 2）假定巡视人员在各乡（镇）停留时间）假定巡视人员在各乡（镇）停留时间T T=2=2小时，在各村停留时间小时，在各村停留时间t t=1=1小时，汽车行驶速度小时，汽车行驶速度V V=35=35公里公里/ /小时小时. . 要在要在2424小时内完成巡视，至少应分小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线几组；给出这种分组下最佳的巡视路线. .4公路边的数字为该路段的公里数公路边的

3、数字为该路段的公里数. .52. 2. 问题分析问题分析本题给出了某县的公路网络图，要求在不同的条件下，本题给出了某县的公路网络图，要求在不同的条件下，灾情巡视的最佳分组方案和路线灾情巡视的最佳分组方案和路线. . 将每个乡（镇）或村看作一个图的顶点，各乡镇、村之将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权行驶时间）看作对应边上的权，所给公路网就转化为加权图，问题就转化为图论中一类称之为旅行推销员问题，图，问题就转化为图论中一类称之为旅行推销

4、员问题，即在给定的加权网络图中寻找从给定点即在给定的加权网络图中寻找从给定点O O出发，行遍所有出发，行遍所有顶点至少一次再回到点顶点至少一次再回到点O O，使得总权（路程或时间）最小，使得总权（路程或时间）最小. .6旅行商问题旅行商问题(TSP(TSP，traveling salesman problem)traveling salesman problem) 一个商人欲到一个商人欲到n n个城市推销商品，每两个城市个城市推销商品，每两个城市i i和和j j之间的距离为之间的距离为d dijij，如何选择一条道路使得，如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路商人每个城市

5、正好走一遍后回到起点且所走路线最短。线最短。：7图论模型图论模型 构造一个图构造一个图G=G=（V V，E E），顶点表示城市，边），顶点表示城市，边表示连接两城市的路，边上的权表示连接两城市的路，边上的权W W（e e）表示距）表示距离（或时间或费用）。于是旅行推销员问题就离（或时间或费用）。于是旅行推销员问题就成为在加权图中寻找一条经过每个顶点正好一成为在加权图中寻找一条经过每个顶点正好一次的最短圈的问题，即求最佳次的最短圈的问题，即求最佳Hamilton Hamilton 圈的圈的问题。问题。 ：8基本概念基本概念1) 1) 哈米尔顿路径哈米尔顿路径(H(H路径路径) ): : 经过图经

6、过图G G每个顶点正好一次的路径每个顶点正好一次的路径; ;2) 2) 哈米尔顿圈哈米尔顿圈(H(H圈圈) )；经过；经过G G的每个顶点正好一次的圈的每个顶点正好一次的圈; ;3) 3) 哈米尔顿图哈米尔顿图(H(H图图) ): : 含含H H圈的图。圈的图。4) 4) 最佳最佳H H圈圈: : 在加权图在加权图G=G=（V V，E E）中，权最小的）中，权最小的H H圈；圈；5) 5) 最佳推销员回路最佳推销员回路: : 经过每个经过每个 顶点一次的权最小闭通路顶点一次的权最小闭通路; ;6) 6) TSPTSP问题问题: : 在完备加权图中求最佳在完备加权图中求最佳H H圈的问题。圈的问

7、题。：9TSP问题举例v工件排序 设有n个工件等待在一台机床上加工，加工完i，接着加工j，这中间机器需要花费一定的准备时间tij，问如何安排加工顺序使总调整时间最短？ 此问题可用TSP的方法求解，n个工件对应n个顶点，tij表示(i,j) 上的权，因此需求图中权最小的H路径。v计算机布线 一个计算机接口含几个组件。每个组件上都置有若干管脚。这些管脚需用导线连接。考虑到以后改变方便和管脚的细小。要求每个管脚最多连两条线。为避免信号干扰以及布线的简洁，要求导线总长度尽可能小。 10TSP问题举例v计算机布线（续） 问题容易转化为TSP问题，每个管脚对应于图的顶点，d(x,y)代表两管脚x与y的距离

8、，原问题即为在图中寻求最小权H路径。v电路板钻孔 MetelcoSA是希腊的一个印刷电路板（PCCB）制造商。在板子上对应管脚的地方必须钻孔，以便以后电子元件焊在这板上。典型的电路板可能有500个管脚位置，大多数钻孔都由程序化的钻孔机完成，求最佳钻孔顺序。此问题其实就是求500个顶点的完备加权图的最佳H圈的问题，即TSP问题。用求解出的H圈来指导生产，使Metclo的钻孔时间缩短了30%，提高了生产效率。 11算法简介算法简介 TSP TSP问题是问题是NP-hardNP-hard问题，即不存在多项式时间算法问题，即不存在多项式时间算法. .也就是说也就是说, ,对于大型网络对于大型网络( (

9、赋权图赋权图),),目前还没有一个精确求解目前还没有一个精确求解TSPTSP问题的有效算法，因此只能找能求出相当好（不一定最问题的有效算法，因此只能找能求出相当好（不一定最优）的解的算法优）的解的算法. .12算法简介算法简介v近似算法或近似算法或启发式算法启发式算法 1.1. 一般是以构造型算法得到一个初始解，然后再用改一般是以构造型算法得到一个初始解，然后再用改进型算法逐步改进。进型算法逐步改进。2.2.常见的构造型算法有两种：常见的构造型算法有两种：ChristofidesChristofides最小权匹最小权匹配算法配算法 ，对角线完全算法。，对角线完全算法。3.3.常见的改进型算法有

10、两种：二次逐次修正法，常见的改进型算法有两种：二次逐次修正法，FeiringFeiring矩阵逐次改进法。矩阵逐次改进法。v 分枝定界法分枝定界法13算法简介算法简介v 二次逐次修正法二次逐次修正法（1）任取初始H圈 C0=v1,v2,vi,vj,vm,v1（2）对所有的i,j,1i+1jm，若 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）C0C,重复步骤（2

11、），直到条件不满足为止，最后得到的C即为所求。 14例对下图的K6,用二边逐次修正法求较优H圈.较优较优H圈圈:其权为其权为W(C3)=19213265413vvvvvvvC 15 分析分析: 这个解的近似程度可用最优这个解的近似程度可用最优H圈的权圈的权的下界与的下界与其比较而得出其比较而得出.即利用最小生成树可得最即利用最小生成树可得最优优H圈的一个下界圈的一个下界. 设设C是是G的一个最优的一个最优H圈，则对圈，则对G的任一顶点的任一顶点v, C-v是是G-v的生成树的生成树.如果如果T是是G-v的的最小生成树最小生成树,且且e1是是e2与与v关联关联的边中权最小的两条的边中权最小的两条

12、边边,则则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)应满足应满足178 w(C) 192.16对角线完全算法 结论: 若能在nn距离矩阵中找出n个不同行也不同列的元素，使它们的和为最小值。若这n个元素构成一条哈米尔顿圈时，此圈便是最佳H圈。 矩阵的简化 :将矩阵的每一行的各元素减去本行的最小元素称为对行简化，从第

13、i行减去的数称为第i行的约数，记为R（i）。将矩阵的每一列的各元素减去本列的最小元素称为对列简化，从第j列减去的数称为第j列的约数，记为R(j)。各行各列的约数之和称为矩阵的约数，记为R。矩阵经行的简化和列的简化后所得矩阵称为该矩阵的简化矩阵。 17对角线完全算法 例 求下列距离矩阵D的简化矩阵及各行，各列的约数。其中107822624509161519253017527314025DD中各行的约数R(1)=25，R(2)=5，R(3)=1，R(4)=6，R(5)=718对角线完全算法 D经行简化得求出D各列的约数R(1)=0，R(2)=0，R(3)=0，R(4)=3，R(5)=0015620

14、12252018145034418015103DU19对角线完全算法 D经列简化得由于简化矩阵同一行各元素减同一数，同列各元素也是减同一数，因而每个H圈的权都减少同一数即R.015312012222018142034418015100D20对角线完全算法 定理 设D是图G的距离矩阵D的简化矩阵，则D对应的图G的最佳（有向）H圈也是原图G的最佳（有向）H圈。G只是边权与G不同，去掉权之后完全一样。因此当简化矩阵中的零元素构成H圈时，该H圈也是原问题的最佳H圈。 罚数: 在图G的距离矩阵的简化矩阵D中，第i行的最小元素与次小元素之差称为第i行的罚数，记为P(i)。第j列的最小元素与次小元素之差称为

15、第j列的罚数，记为P(j)，某行（或列）的罚数即是若H圈不选择该行（或列）的最小元素会使其权增加的最小值。21对角线完全算法 算法步骤输入：图的距离矩阵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圈的一些不相交路径称为可行部分路。22对角线完全算法 （3）构造新的距离矩阵称为重构距离矩阵：按上述可行部分路的顶点序重新排列

16、简化距离D的行，列也按使上述所有“0*”位于对角线上的次序重新排列。（4）产生D的子阵：设重构矩阵对角线上m个非零元素对应的边为(i1,j1),（i2,j2），（im,jm），则从D中取出相应的m行，m列构成一个mm子阵D1。为保证选出的边与原来的可行部分路不形成子循环，有m条边不能选择，将其对应的元素置为。并将列作适当调整使对角线元素为。（5）对D1重复（1）（4）步，直到重构矩阵对角线上的元素全为0为止，这时便可得到一个H圈。23对角线完全算法 例 用对角线完全法求加权图K10的较佳H圈 320590848477335357438462570320270653198901502904456

17、44590270580197281304388586806848653580464573521410462600477198197464143130191388608335902815731436020362568357150304521130601403085204382903884101912001401984184624455864623883623081982205706448066006085684204182201098765432110987654321D24对角线完全算法 1 12 23 34 45 56 67 78 89 91010RiRiPiPi1 10 019819830

18、03003483483883881161165195194244241201202202201161162 20 00 01101101641641901900 032132124724734341981980 03 325625658580 0606051516 618118115015068681401406 64 443843824824880800 0707019719717717790906767606067675 54864863023021401400 0838324924915415430304545606030306 645645625825861610 0131370700

19、 068681171171301300 07 716816852520 0111111163163545410310324324320820841041052528 858758738938919119110710784840 0119119737316316319719773739 953253235535520020060600 01081082992991131130 090900 01010228228142142118118373715151571572642642032030 03203201515RjRj22220 00 00 00 00 026426467670 0230230

20、PjPj16816852520 00 00 051516 61031033030343425对角线完全算法 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）=026对角线完全算法 现依次从上述各边选择能形成可

21、行部分路的边，现依次从上述各边选择能形成可行部分路的边， 先选第一边先选第一边（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)

22、会使会使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，三条不相交路径。，三条不相交路径。 27对角线完全算法 2734586109110*20*70*30*40*528180647710096443. 以1，2，7，3，4，5，8，6，10，9的顺序重新排列D的行，为使所有0*位

23、于对角线上，D的列按2，7，3，4，5，8，6，10，9，1的顺序排列，这样便得到第一级重构距离矩阵28对角线完全算法 4. 对角线上有三个非零元素对角线上有三个非零元素281，477和和644，其对应的边为：，其对应的边为：（5，8），（），（6，10）和（）和（8，1），相应的行数为），相应的行数为5，6，9；列数为列数为8，10，1。从。从原始权矩阵原始权矩阵D中取出这三行，三列构成中取出这三行，三列构成一个一个33型的型的D的子阵的子阵：181052813356608477964427029对角线完全算法 5. 重复步骤（重复步骤（1）-（4），得到），得到第二级简化矩阵及相应的约数，

24、罚数第二级简化矩阵及相应的约数，罚数 1810R（i）P(i)505428154600477092430270243R(j)13100P(j)243054计算各零元素的罚数并按由大到小排列如下：计算各零元素的罚数并按由大到小排列如下：P（6，1）=243 P（9，8）=243 P（5，8）=54 P（6，10）=54依次选择依次选择可行边：（可行边：（6，1）和（）和（9，8）。它们对应的零元素记为。它们对应的零元素记为0*。与原来已经选出的边一起形成可行部分路如下：与原来已经选出的边一起形成可行部分路如下：1-2-7-3-4-5；8-6-1；10-9-8，或更清楚地应为：或更清楚地应为：10

25、-9-8-6-1-2-7-3-4-5。 30对角线完全算法 上述顶点序得到上述顶点序得到第二级重构距离矩阵第二级重构距离矩阵 98612734510100*90*80*60*10*20*70*30*40*5335最后还剩一个元素（最后还剩一个元素（5，10）不为零，没有选择余地，第三迭代必定是选）不为零，没有选择余地，第三迭代必定是选（5，10）与前面得到的可行部分将一起构成）与前面得到的可行部分将一起构成H圈圈10-9-8-6-1-2-7-3-4-5-10.31对角线完全算法 因此第三级重构距离矩阵只需在第二级距离矩阵中因此第三级重构距离矩阵只需在第二级距离矩阵中335换换成成0*即可。即可

26、。第三级重构距离矩阵第三级重构距离矩阵为：为： 98612734510100*90*80*60*10*20*70*30*40*50*故所求故所求H圈为：圈为：10-9-8-6-1-2-7-3-4-5-10，其权：，其权：W=3022。32旅行商问题的数学规划模型旅行商问题的数学规划模型01(10) ( . ) s.t. 1,()1,dijxijijd xij iji jAxi Vijj Vxjij V设是 与 之间的距离，或表示连线，表示不连线 .则有:min ; 每个点只有一条边出去 ； ,()j V 每个点只有一条边进入 （除起点与终点外，各边不构成圈）33旅行商问题的数学规划模型旅行商问

27、题的数学规划模型11,min. .1,1, .1,1,| 1,2 |2,1,2, 0,1,1, ,.nijijijnijjnijiiji j Sijd xstxinxjnxSSnSnxi jnij或34旅行商问题的数学规划模型旅行商问题的数学规划模型例例 用用LINGO软件求解软件求解(33) (36) MODEL: 1sets: 2 cities/1.10/:level; !level(i)= the level of city; 3 link(cities, cities): 4 distance, !The distance matrix; 5 x; ! x(i,j)=1 if we u

28、se link i,j; 6endsets 7data: !Distance matrix, it need not be symmetirc; 8 distance = 0 8 5 9 12 14 12 16 17 2235旅行商问题的数学规划模型旅行商问题的数学规划模型 9 8 0 9 15 16 8 11 18 14 22 10 5 9 0 7 9 11 7 12 12 17 11 9 15 7 0 3 17 10 7 15 15 12 12 16 9 3 0 8 10 6 15 15 13 14 8 11 17 8 0 9 14 8 16 14 12 11 7 10 10 9 0 8

29、6 11 15 16 18 12 7 6 14 8 0 11 11 16 17 14 12 15 15 8 6 11 0 10 17 22 22 17 15 15 16 11 11 10 0; 18enddata 19n=size(cities); !The model size; 20! Minimize total distance of the links;36旅行商问题的数学规划模型旅行商问题的数学规划模型 21min=sum(link(i,j)|i #ne# j: distance(i,j)*x(i,j); 22!For city i; 23for(cities(i) : 24! I

30、t must be entered; 25 sum(cities(j)| j #ne# i: x(j,i)=1; 26! It must be departed; 27 sum(cities(j)| j #ne# i: x(i,j)=1; 28! level(j)=levle(i)+1, if we link j and i; 29 for(cities(j)| j #gt# 1 #and# j #ne# i : 30 level(j) = level(i) + x(i,j) 31 - (n-2)*(1-x(i,j) + (n-3)*x(j,i); 32 ); 33);37旅行商问题的数学规划

31、模型旅行商问题的数学规划模型 34! Make the xs 0/1; 35for(link : bin(x); 36! For the first and last stop; 37for(cities(i) | i #gt# 1 : 38 level(i)=1+(n-2)*x(i,1); 40); END水平变量水平变量(level)仍然是用来保证所选的边除第仍然是用来保证所选的边除第1点外不构成圈的点外不构成圈的.计算结果如下：计算结果如下：38旅行商问题的数学规划模型旅行商问题的数学规划模型Global optimal solution found at iteration: 90Ob

32、jective value: 73.00000 Variable Value Reduced Cost X( 1, 2) 1.000000 8.000000 X( 2, 6) 1.000000 8.000000 X( 3, 1) 1.000000 5.000000 X( 4, 3) 1.000000 7.000000 X( 5, 4) 1.000000 3.000000 X( 6, 9) 1.000000 8.000000 X( 7, 10) 1.000000 11.00000 X( 8, 5) 1.000000 6.000000 X( 9, 7) 1.000000 6.000000 X( 1

33、0, 8) 1.000000 11.0000039旅行商问题的数学规划模型旅行商问题的数学规划模型旅行商经过旅行商经过10 个城镇的最短距离为个城镇的最短距离为73公里，其连公里，其连接情况如图所示接情况如图所示.40最佳灾情巡视路线的模型的建立与求解最佳灾情巡视路线的模型的建立与求解问题转化为在问题转化为在给定的加权网给定的加权网络图中寻找从络图中寻找从给定点给定点O O出发出发, ,行遍所有顶点行遍所有顶点至少一次再回至少一次再回回到点回到点O ,O ,使得使得总权总权( (路程或时路程或时时间时间) )最小最小, ,即即最佳旅行推销最佳旅行推销员问题员问题. .41最佳旅行推销员问题是最

34、佳旅行推销员问题是NPNP完全问题完全问题, ,采用一种采用一种近似算法求其一个近似最优解，来代替最优解近似算法求其一个近似最优解，来代替最优解. .算法一算法一 求加权图的最佳旅行推销员回路近似算法求加权图的最佳旅行推销员回路近似算法: : 1) 1) 用图论软件包求出用图论软件包求出G G中任意两个顶点间的最短路中任意两个顶点间的最短路, , 构造出完全图构造出完全图),(,),(),(yxEyxEVG);,(minyxdG2) 2) 输入图输入图 的一个初始的一个初始H H圈；圈；G3) 3) 用对角线完全算法产生一个初始圈用对角线完全算法产生一个初始圈; ;4) 4) 随机搜索出随机搜

35、索出 中若干个中若干个H H圈，例如圈，例如20002000个；个；G5) 5) 对第对第2)2)，3)3)，4)4)步所得的每个步所得的每个H H圈，用二边逐次圈，用二边逐次修正法进行优化，得到近似最优修正法进行优化，得到近似最优H H圈；圈；6) 6) 在第在第5)5)步求出的所有步求出的所有H H圈中，找出权最小的一个圈中，找出权最小的一个, , 此即要找的最优此即要找的最优H H圈的近似解圈的近似解. .因二边逐次修正法的结果与初始圈有关因二边逐次修正法的结果与初始圈有关, ,故本算法故本算法第第2)2)，3)3)，4)4)步分别用三种方法产生初始圈，以保步分别用三种方法产生初始圈，以

36、保证能得到较优的计算结果证能得到较优的计算结果. .42 问题一问题一 若分为三组巡视，设计总路程最短且各若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线组尽可能均衡的巡视路线. . 此问题是多个推销员的最佳旅行推销员问题此问题是多个推销员的最佳旅行推销员问题. .4)min)(1niiC43 此问题包含两方面：此问题包含两方面：a)a)对顶点分组对顶点分组, b), b)在每组中在每组中求求( (单个推销员单个推销员) )最佳旅行推销员回路最佳旅行推销员回路. . 因单个推销员的最佳旅行推销员回路问题不存因单个推销员的最佳旅行推销员回路问题不存存在多项式时间内的精确算法存在多项式时间

37、内的精确算法. .44 而图中节点数较多，为而图中节点数较多，为5353个，我们只能去寻求个，我们只能去寻求一种较合理的划分准则，对图一种较合理的划分准则，对图1 1进行初步划分后进行初步划分后, ,求求出各部分的近似最佳旅行推销员回路的权出各部分的近似最佳旅行推销员回路的权, ,再进一再进一步进行调整，使得各部分满足均衡性条件步进行调整，使得各部分满足均衡性条件3).3). 从从O O点出发去其它点，要使路程较小应尽量走点出发去其它点，要使路程较小应尽量走O O点到该点的最短路点到该点的最短路. . 故用软件包求出故用软件包求出O O点到其余顶点的最短路点到其余顶点的最短路. . 这些最短路

38、构成一棵这些最短路构成一棵O O为树根的树为树根的树. .将从将从O O点出发的树枝称为点出发的树枝称为干枝干枝. .45从从O点出发到其它点共有点出发到其它点共有6条干枝，它们的名称条干枝，它们的名称分别为，分别为，. 在分组时应遵从准则：在分组时应遵从准则： 准则准则1 尽量使同一干枝上及其分枝上的点分在同一组尽量使同一干枝上及其分枝上的点分在同一组.准则准则2 应将相邻的干枝上的点分在同一组；应将相邻的干枝上的点分在同一组； 准则准则3 尽量将长的干枝与短的干枝分在同一组尽量将长的干枝与短的干枝分在同一组.由上述分组准则，我们找到两种分组形式如下：由上述分组准则，我们找到两种分组形式如下

39、：分组分组1:（，），（，），（，）（，），（，），（，）分组分组2:（，），（，），（，）（，），（，），（，）分组分组1极不均衡极不均衡,故考虑分组故考虑分组2.46分组分组2:(,),(,),(,) 对分组对分组2 2中每组顶点的生成子图中每组顶点的生成子图, ,用算法一求用算法一求出近似最优解及相应的巡视路线出近似最优解及相应的巡视路线. . 在每个子图所构造的完全图中在每个子图所构造的完全图中, ,取一个尽量包含取一个尽量包含上图中树上的边的上图中树上的边的H H圈作为其第圈作为其第2)2)步输入的初始圈步输入的初始圈. .47分组分组2的近似解的近似解 48因为该分组的均衡度因为该

40、分组的均衡度54.2%9 .2415 .1259 .241)(max)()(3 , 2 , 1210iiCCC.所以此分法的均衡性很差所以此分法的均衡性很差. . 为改善均衡性，将第为改善均衡性，将第组中的顶点组中的顶点C C,2,3,2,3,D D,4,4分给第分给第组（顶点组（顶点2 2为这两组的公共点），重新分为这两组的公共点），重新分分组后的近似最优解见表分组后的近似最优解见表2.2.4950%.69.114 .2161 .1914 .216)(max)()(3 , 2 , 1130iiCCC因该分组的均衡度因该分组的均衡度 所以这种分法的均衡性较好所以这种分法的均衡性较好. . 问题

41、二问题二 当巡视人员在各乡（镇）、村的停留当巡视人员在各乡（镇）、村的停留停留时间一定停留时间一定, ,汽车的行驶速度一定汽车的行驶速度一定, ,要在要在2424小时内小时内完成巡视完成巡视, ,至少要分几组及最佳旅行的巡视路线至少要分几组及最佳旅行的巡视路线. .51 由于由于T T=2=2小时小时, ,t t=1=1小时小时, ,V V=35=35公里公里/ /小时小时, ,需访问需访问的乡镇共有的乡镇共有1717个，村共有个，村共有3535个个. . 计算出在乡计算出在乡( (镇镇) )及及村的总停留时间为村的总停留时间为17 2+35=6917 2+35=69小时，要在小时，要在242

42、4小时小时内完成巡回，若不考虑行走时间，有内完成巡回，若不考虑行走时间，有: 69/: 69/i24(ii24(i为为分的组数分的组数). ). 得得i i最小为最小为4 4，故，故至少要分至少要分4 4组组. . 由于该网络的乡由于该网络的乡( (镇镇) )、村分布较为均匀、村分布较为均匀, ,故有可故有可能找出停留时间尽量均衡的分组能找出停留时间尽量均衡的分组, ,当分当分4 4组时各组停组时各组停停留时间大约为停留时间大约为69/4=17.2569/4=17.25小时，则每组分配在路小时，则每组分配在路路途上的时间大约为路途上的时间大约为24-17.25=6.7524-17.25=6.7

43、5小时小时. .而前面讨而前面讨论过论过, ,分三组时有个总路程分三组时有个总路程599.8599.8公里的巡视路线，公里的巡视路线，分分4 4组时的总路程不会比组时的总路程不会比599.8599.8公里大太多公里大太多, ,不妨以不妨以599.8599.8公里来计算公里来计算. .路上约用路上约用599.8/35=17599.8/35=17小时小时, ,若平若平均分配给均分配给4 4个组个组, ,每个组约需每个组约需17/4=4.2517/4=4.25小时小时6.756.75小小小时小时, ,故分成故分成4 4组是可能办到的组是可能办到的. .52 现在尝试将顶点分为现在尝试将顶点分为4 4

44、组组. .分组的原则：除遵从分组的原则：除遵从前面准则前面准则1 1、2 2、3 3外，还应遵从以下准则：外，还应遵从以下准则：准则准则4 4 尽量使各组的停留时间相等尽量使各组的停留时间相等. . 用上述原则在下图上将图分为用上述原则在下图上将图分为4 4组，同时计算组，同时计算各组的停留时间各组的停留时间, ,然后用算法一算出各组的近似最然后用算法一算出各组的近似最最佳旅行推销员巡回，得出路线长度及行走时间最佳旅行推销员巡回，得出路线长度及行走时间, ,从而得出完成巡视的近似最佳时间从而得出完成巡视的近似最佳时间. . 用算法一计用算法一计计算时，初始圈的输入与分三组时同样处理计算时，初始圈的输入与分三组时同样处理. .这这4 4组的近似最优解见表组的近似最优解见表3.3.5354表表3符号说明：加有底纹的表示前面经过并停留过符号说明：加有底纹的表示前面经过并停留过,此次只经过不停留此次只经过不停留;加框的表示此点只经过不停留加框的表示此点只经过不停留. 可看出可看出,表表3分组的均衡度很好分组的均衡度很好,且完全满足且完全满足24小时完成巡视的要求小时完成巡视的要求. 该分组实际均衡度该分组实际均衡度 4.62% 74.2269.2174.22055