旅行商問題(TSP)

1、主要內(nèi)容基本概念算法簡介TSP模型的應(yīng)用最佳災(zāi)情巡視路線的模型的建立與求解引 例： 1. 98 1. 98年全國大學(xué)生數(shù)學(xué)建模競賽年全國大學(xué)生數(shù)學(xué)建模競賽B B題題“最佳災(zāi)最佳災(zāi) 今年今年(1998(1998年年) )夏天某縣遭受水災(zāi)夏天某縣遭受水災(zāi). . 為考察災(zāi)情、為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視全縣各鄉(xiāng)（鎮(zhèn)）、村巡視. . 巡視路線指從縣政府巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線府所在地的路線. .情巡視路線情巡視路線”中的前

2、兩個問題：中的前兩個問題： 1 1）若分三組（路）巡視，試設(shè)計總路程最）若分三組（路）巡視，試設(shè)計總路程最短且各組盡可能均衡的巡視路線短且各組盡可能均衡的巡視路線. . 2 2）假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間）假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T T=2=2小時，在各村停留時間小時，在各村停留時間t t=1=1小時，汽車行駛速度小時，汽車行駛速度V V=35=35公里公里/ /小時小時. . 要在要在2424小時內(nèi)完成巡視，至少應(yīng)分小時內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下最佳的巡視路線幾組；給出這種分組下最佳的巡視路線. .公路邊的數(shù)字為該路段的公里數(shù)公路邊的數(shù)字為該路段的公里數(shù). .2.

3、 2. 問題分析問題分析本題給出了某縣的公路網(wǎng)絡(luò)圖，要求在不同的條件下，本題給出了某縣的公路網(wǎng)絡(luò)圖，要求在不同的條件下，災(zāi)情巡視的最佳分組方案和路線災(zāi)情巡視的最佳分組方案和路線. . 將每個鄉(xiāng)（鎮(zhèn)）或村看作一個圖的頂點，各鄉(xiāng)鎮(zhèn)、村之將每個鄉(xiāng)（鎮(zhèn)）或村看作一個圖的頂點，各鄉(xiāng)鎮(zhèn)、村之間的公路看作此圖對應(yīng)頂點間的邊，各條公路的長度（或間的公路看作此圖對應(yīng)頂點間的邊，各條公路的長度（或行駛時間）看作對應(yīng)邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)行駛時間）看作對應(yīng)邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)圖，問題就轉(zhuǎn)化為圖論中一類稱之為旅行推銷員問題，圖，問題就轉(zhuǎn)化為圖論中一類稱之為旅行推銷員問題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋

4、找從給定點即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點O O出發(fā)，行遍所有出發(fā)，行遍所有頂點至少一次再回到點頂點至少一次再回到點O O，使得總權(quán)（路程或時間）最小，使得總權(quán)（路程或時間）最小. .旅行商問題旅行商問題(TSP(TSP，traveling salesman problem)traveling salesman problem) 一個商人欲到一個商人欲到n n個城市推銷商品，每兩個城市個城市推銷商品，每兩個城市i i和和j j之間的距離為之間的距離為d dijij，如何選擇一條道路使得，如何選擇一條道路使得商人每個城市正好走一遍后回到起點且所走路商人每個城市正好走一遍后回到起點且所走路線最短

5、。線最短。：圖論模型圖論模型 構(gòu)造一個圖構(gòu)造一個圖G=G=（V V，E E），頂點表示城市，邊），頂點表示城市，邊表示連接兩城市的路，邊上的權(quán)表示連接兩城市的路，邊上的權(quán)W W（e e）表示距）表示距離（或時間或費用）。于是旅行推銷員問題就離（或時間或費用）。于是旅行推銷員問題就成為在加權(quán)圖中尋找一條經(jīng)過每個頂點正好一成為在加權(quán)圖中尋找一條經(jīng)過每個頂點正好一次的最短圈的問題，即求最佳次的最短圈的問題，即求最佳Hamilton Hamilton 圈的圈的問題。問題。 ：基本概念基本概念1) 1) 哈米爾頓路徑哈米爾頓路徑(H(H路徑路徑) ): : 經(jīng)過圖經(jīng)過圖G G每個頂點正好一次的路徑每個頂

6、點正好一次的路徑; ;2) 2) 哈米爾頓圈哈米爾頓圈(H(H圈圈) )；經(jīng)過；經(jīng)過G G的每個頂點正好一次的圈的每個頂點正好一次的圈; ;3) 3) 哈米爾頓圖哈米爾頓圖(H(H圖圖) ): : 含含H H圈的圖。圈的圖。4) 4) 最佳最佳H H圈圈: : 在加權(quán)圖在加權(quán)圖G=G=（V V，E E）中，權(quán)最小的）中，權(quán)最小的H H圈；圈；5) 5) 最佳推銷員回路最佳推銷員回路: : 經(jīng)過每個經(jīng)過每個 頂點一次的權(quán)最小閉通路頂點一次的權(quán)最小閉通路; ;6) 6) TSPTSP問題問題: : 在完備加權(quán)圖中求最佳在完備加權(quán)圖中求最佳H H圈的問題。圈的問題。：TSP問題舉例v工件排序 設(shè)有n

7、個工件等待在一臺機(jī)床上加工，加工完i，接著加工j，這中間機(jī)器需要花費一定的準(zhǔn)備時間tij，問如何安排加工順序使總調(diào)整時間最短？ 此問題可用TSP的方法求解，n個工件對應(yīng)n個頂點，tij表示(i,j) 上的權(quán)，因此需求圖中權(quán)最小的H路徑。v計算機(jī)布線 一個計算機(jī)接口含幾個組件。每個組件上都置有若干管腳。這些管腳需用導(dǎo)線連接?？紤]到以后改變方便和管腳的細(xì)小。要求每個管腳最多連兩條線。為避免信號干擾以及布線的簡潔，要求導(dǎo)線總長度盡可能小。 TSP問題舉例v計算機(jī)布線（續(xù)） 問題容易轉(zhuǎn)化為TSP問題，每個管腳對應(yīng)于圖的頂點，d(x,y)代表兩管腳x與y的距離，原問題即為在圖中尋求最小權(quán)H路徑。v電路板

8、鉆孔 MetelcoSA是希臘的一個印刷電路板（PCCB）制造商。在板子上對應(yīng)管腳的地方必須鉆孔，以便以后電子元件焊在這板上。典型的電路板可能有500個管腳位置，大多數(shù)鉆孔都由程序化的鉆孔機(jī)完成，求最佳鉆孔順序。此問題其實就是求500個頂點的完備加權(quán)圖的最佳H圈的問題，即TSP問題。用求解出的H圈來指導(dǎo)生產(chǎn)，使Metclo的鉆孔時間縮短了30%，提高了生產(chǎn)效率。 算法簡介算法簡介 TSP TSP問題是問題是NP-hardNP-hard問題，即不存在多項式時間算法問題，即不存在多項式時間算法. .也就是說也就是說, ,對于大型網(wǎng)絡(luò)對于大型網(wǎng)絡(luò)( (賦權(quán)圖賦權(quán)圖),),目前還沒有一個精確求解目前還

9、沒有一個精確求解TSPTSP問題的有效算法，因此只能找能求出相當(dāng)好（不一定最問題的有效算法，因此只能找能求出相當(dāng)好（不一定最優(yōu)）的解的算法優(yōu)）的解的算法. .算法簡介算法簡介v近似算法或近似算法或啟發(fā)式算法啟發(fā)式算法 1.1. 一般是以構(gòu)造型算法得到一個初始解，然后再用改一般是以構(gòu)造型算法得到一個初始解，然后再用改進(jìn)型算法逐步改進(jìn)。進(jìn)型算法逐步改進(jìn)。2.2.常見的構(gòu)造型算法有兩種：常見的構(gòu)造型算法有兩種：ChristofidesChristofides最小權(quán)匹最小權(quán)匹配算法配算法 ，對角線完全算法。，對角線完全算法。3.3.常見的改進(jìn)型算法有兩種：二次逐次修正法，常見的改進(jìn)型算法有兩種：二次逐

10、次修正法，F(xiàn)eiringFeiring矩陣逐次改進(jìn)法。矩陣逐次改進(jìn)法。v 分枝定界法分枝定界法算法簡介算法簡介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,重復(fù)步驟（2），直到條件不滿足為止，最后得到的C即為所求。 例對下圖

11、的K6,用二邊逐次修正法求較優(yōu)H圈.較優(yōu)較優(yōu)H圈圈:其權(quán)為其權(quán)為W(C3)=19213265413vvvvvvvC 分析分析: 這個解的近似程度可用最優(yōu)這個解的近似程度可用最優(yōu)H圈的權(quán)圈的權(quán)的下界與的下界與其比較而得出其比較而得出.即利用最小生成樹可得最即利用最小生成樹可得最優(yōu)優(yōu)H圈的一個下界圈的一個下界. 設(shè)設(shè)C是是G的一個最優(yōu)的一個最優(yōu)H圈，則對圈，則對G的任一頂點的任一頂點v, C-v是是G-v的生成樹的生成樹.如果如果T是是G-v的的最小生成樹最小生成樹,且且e1是是e2與與v關(guān)聯(lián)關(guān)聯(lián)的邊中權(quán)最小的兩條的邊中權(quán)最小的兩條邊邊,則則w(T)+w(e1)+w(e2)將是將是w(C)的一個下

12、界的一個下界.取取v=v3,得得G-v3的一的一最小生成樹最小生成樹(實線實線),其權(quán)其權(quán)w(T)=122,與與v3關(guān)聯(lián)關(guān)聯(lián)的權(quán)最的權(quán)最小的兩條邊為小的兩條邊為v1v3和和v2v3,w(T)+w(v1v3)+w(v2v3)=178. 故最優(yōu)故最優(yōu)H圈的權(quán)圈的權(quán)故故w(C)應(yīng)滿足應(yīng)滿足178 w(C) 192.對角線完全算法 結(jié)論: 若能在nn距離矩陣中找出n個不同行也不同列的元素，使它們的和為最小值。若這n個元素構(gòu)成一條哈米爾頓圈時，此圈便是最佳H圈。 矩陣的簡化 :將矩陣的每一行的各元素減去本行的最小元素稱為對行簡化，從第i行減去的數(shù)稱為第i行的約數(shù)，記為R（i）。將矩陣的每一列的各元素減去

13、本列的最小元素稱為對列簡化，從第j列減去的數(shù)稱為第j列的約數(shù)，記為R(j)。各行各列的約數(shù)之和稱為矩陣的約數(shù)，記為R。矩陣經(jīng)行的簡化和列的簡化后所得矩陣稱為該矩陣的簡化矩陣。 對角線完全算法 例 求下列距離矩陣D的簡化矩陣及各行，各列的約數(shù)。其中107822624509161519253017527314025DD中各行的約數(shù)R(1)=25，R(2)=5，R(3)=1，R(4)=6，R(5)=7對角線完全算法 D經(jīng)行簡化得求出D各列的約數(shù)R(1)=0，R(2)=0，R(3)=0，R(4)=3，R(5)=001562012252018145034418015103DU對角線完全算法 D經(jīng)列簡化得

14、由于簡化矩陣同一行各元素減同一數(shù)，同列各元素也是減同一數(shù)，因而每個H圈的權(quán)都減少同一數(shù)即R.015312012222018142034418015100D對角線完全算法 定理 設(shè)D是圖G的距離矩陣D的簡化矩陣，則D對應(yīng)的圖G的最佳（有向）H圈也是原圖G的最佳（有向）H圈。G只是邊權(quán)與G不同，去掉權(quán)之后完全一樣。因此當(dāng)簡化矩陣中的零元素構(gòu)成H圈時，該H圈也是原問題的最佳H圈。 罰數(shù): 在圖G的距離矩陣的簡化矩陣D中，第i行的最小元素與次小元素之差稱為第i行的罰數(shù)，記為P(i)。第j列的最小元素與次小元素之差稱為第j列的罰數(shù)，記為P(j)，某行（或列）的罰數(shù)即是若H圈不選擇該行（或列）的最小元素會

15、使其權(quán)增加的最小值。對角線完全算法 算法步驟輸入：圖的距離矩陣D（1）求D的簡化矩陣D以及各行各列的約數(shù)R(i)， R(j)，罰數(shù)P(i)，P(j)（2）計算在簡化矩陣中零元素所在行與列的罰數(shù) 和，即P(i,j)=P(i)+P(j)。將P(i,j)由大到小 排列后，依次選取可作為可行部分路的邊 （i,j）。這些邊對應(yīng)的零元素記為0*。用這些 選擇出來的邊構(gòu)成可行部分路。定義 一個H圈的一些不相交路徑稱為可行部分路。對角線完全算法 （3）構(gòu)造新的距離矩陣稱為重構(gòu)距離矩陣：按上述可行部分路的頂點序重新排列簡化距離D的行，列也按使上述所有“0*”位于對角線上的次序重新排列。（4）產(chǎn)生D的子陣：設(shè)重構(gòu)

16、矩陣對角線上m個非零元素對應(yīng)的邊為(i1,j1),（i2,j2），（im,jm），則從D中取出相應(yīng)的m行，m列構(gòu)成一個mm子陣D1。為保證選出的邊與原來的可行部分路不形成子循環(huán)，有m條邊不能選擇，將其對應(yīng)的元素置為。并將列作適當(dāng)調(diào)整使對角線元素為。（5）對D1重復(fù)（1）（4）步，直到重構(gòu)矩陣對角線上的元素全為0為止，這時便可得到一個H圈。對角線完全算法 例 用對角線完全法求加權(quán)圖K10的較佳H圈 3205908484773353574384625703202706531989015029044564459027058019728130438858680684865358046457352141

17、0462600477198197464143130191388608335902815731436020362568357150304521130601403085204382903884101912001401984184624455864623883623081982205706448066006085684204182201098765432110987654321D對角線完全算法 1 12 23 34 45 56 67 78 89 91010RiRiPiPi1 10 019819830030034834838838811611651951942442412012022022011611

18、62 20 00 01101101641641901900 032132124724734341981980 03 325625658580 0606051516 618118115015068681401406 64 443843824824880800 0707019719717717790906767606067675 54864863023021401400 0838324924915415430304545606030306 645645625825861610 0131370700 068681171171301300 07 716816852520 011111116316354

19、5410310324324320820841041052528 858758738938919119110710784840 0119119737316316319719773739 953253235535520020060600 01081082992991131130 090900 01010228228142142118118373715151571572642642032030 03203201515RjRj22220 00 00 00 00 026426467670 0230230PjPj16816852520 00 00 051516 610310330303434對角線完全算法

20、 2 求出以上第一級簡化陣中零元素對應(yīng)的罰數(shù)，如P(1，2)=P(1，2)=P(1)+P(2)=116+52=168，并將這些罰數(shù)按由大到小的次序排列如下：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對角線完全算法 現(xiàn)依次從上述各邊選擇能形成可行部分路的邊，現(xiàn)依次從上述各邊選擇能形成可行部分路的邊， 先選第一邊先選第一邊（1，2）， 之后（之后（2，1

21、），（），（2，1）不行，）不行，因（因（1，2），（），（2，1）形成子循環(huán)；）形成子循環(huán)； 接著接著(8，6),但（但（6，8）不行，（）不行，（6，8）會與（）會與（8，6）構(gòu)）構(gòu)成子循環(huán)；成子循環(huán)； 再下是再下是(4,5),(7,3),(10,9)，但，但(9,10)不能入選；不能入選；(5,4)也不能也不能入選，因會和前面選中的入選，因會和前面選中的(4,5)構(gòu)成子循環(huán)；構(gòu)成子循環(huán)； 接著是接著是(2,7),(3,4),但但(2,3)不能入選，否則與不能入選，否則與(2,7)會使會使2的的出次大于出次大于1。同理（。同理（6，4），（），（9，5）也不能入選。）也不能入選。 綜上得到

22、可形成可行部分路的邊為：綜上得到可形成可行部分路的邊為：(1,2), (8,6), (4,5), (7,3),(10,9),(2,7)和和(3,4)。它們對應(yīng)的零元素為。它們對應(yīng)的零元素為0*。 可行部分路：可行部分路：1-2-7-3-4-5，8-6和和10-9，三條不相交路徑。，三條不相交路徑。 對角線完全算法 2734586109110*20*70*30*40*528180647710096443. 以1，2，7，3，4，5，8，6，10，9的順序重新排列D的行，為使所有0*位于對角線上，D的列按2，7，3，4，5，8，6，10，9，1的順序排列，這樣便得到第一級重構(gòu)距離矩陣對角線完全算法

23、 4. 對角線上有三個非零元素對角線上有三個非零元素281，477和和644，其對應(yīng)的邊為：，其對應(yīng)的邊為：（5，8），（），（6，10）和（）和（8，1），相應(yīng)的行數(shù)為），相應(yīng)的行數(shù)為5，6，9；列數(shù)為列數(shù)為8，10，1。從。從原始權(quán)矩陣原始權(quán)矩陣D中取出這三行，三列構(gòu)成中取出這三行，三列構(gòu)成一個一個33型的型的D的子陣的子陣：1810528133566084779644270對角線完全算法 5. 重復(fù)步驟（重復(fù)步驟（1）-（4），得到），得到第二級簡化矩陣及相應(yīng)的約數(shù)，罰數(shù)第二級簡化矩陣及相應(yīng)的約數(shù)，罰數(shù) 1810R（i）P(i)505428154600477092430270243R(j

24、)13100P(j)243054計算各零元素的罰數(shù)并按由大到小排列如下：計算各零元素的罰數(shù)并按由大到小排列如下：P（6，1）=243 P（9，8）=243 P（5，8）=54 P（6，10）=54依次選擇依次選擇可行邊：（可行邊：（6，1）和（）和（9，8）。它們對應(yīng)的零元素記為。它們對應(yīng)的零元素記為0*。與原來已經(jīng)選出的邊一起形成可行部分路如下：與原來已經(jīng)選出的邊一起形成可行部分路如下：1-2-7-3-4-5；8-6-1；10-9-8，或更清楚地應(yīng)為：或更清楚地應(yīng)為：10-9-8-6-1-2-7-3-4-5。 對角線完全算法 上述頂點序得到上述頂點序得到第二級重構(gòu)距離矩陣第二級重構(gòu)距離矩陣

25、98612734510100*90*80*60*10*20*70*30*40*5335最后還剩一個元素（最后還剩一個元素（5，10）不為零，沒有選擇余地，第三迭代必定是選）不為零，沒有選擇余地，第三迭代必定是選（5，10）與前面得到的可行部分將一起構(gòu)成）與前面得到的可行部分將一起構(gòu)成H圈圈10-9-8-6-1-2-7-3-4-5-10.對角線完全算法 因此第三級重構(gòu)距離矩陣只需在第二級距離矩陣中因此第三級重構(gòu)距離矩陣只需在第二級距離矩陣中335換換成成0*即可。即可。第三級重構(gòu)距離矩陣第三級重構(gòu)距離矩陣為：為： 98612734510100*90*80*60*10*20*70*30*40*50

26、*故所求故所求H圈為：圈為：10-9-8-6-1-2-7-3-4-5-10，其權(quán)：，其權(quán)：W=3022。旅行商問題的數(shù)學(xué)規(guī)劃模型旅行商問題的數(shù)學(xué)規(guī)劃模型01(10) ( . ) s.t. 1,()1,dijxijijd xij iji jAxi Vijj Vxjij V設(shè)是 與 之間的距離，或表示連線，表示不連線 .則有:min ; 每個點只有一條邊出去 ； ,()j V 每個點只有一條邊進(jìn)入 （除起點與終點外，各邊不構(gòu)成圈）旅行商問題的數(shù)學(xué)規(guī)劃模型旅行商問題的數(shù)學(xué)規(guī)劃模型11,min. .1,1, .1,1,| 1,2 |2,1,2, 0,1,1, ,.nijijijnijjnijiiji

27、j Sijd xstxinxjnxSSnSnxi jnij或旅行商問題的數(shù)學(xué)規(guī)劃模型旅行商問題的數(shù)學(xué)規(guī)劃模型例例 用用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 use link i,j; 6endsets 7data: !Distance matrix, it need not be symmetirc

28、; 8 distance = 0 8 5 9 12 14 12 16 17 22旅行商問題的數(shù)學(xué)規(guī)劃模型旅行商問題的數(shù)學(xué)規(guī)劃模型 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 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

29、17 15 15 16 11 11 10 0; 18enddata 19n=size(cities); !The model size; 20! Minimize total distance of the links;旅行商問題的數(shù)學(xué)規(guī)劃模型旅行商問題的數(shù)學(xué)規(guī)劃模型 21min=sum(link(i,j)|i #ne# j: distance(i,j)*x(i,j); 22!For city i; 23for(cities(i) : 24! It must be entered; 25 sum(cities(j)| j #ne# i: x(j,i)=1; 26! It must be dep

30、arted; 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);旅行商問題的數(shù)學(xué)規(guī)劃模型旅行商問題的數(shù)學(xué)規(guī)劃模型 34! Make the xs 0/1; 35for(link : bin(x); 36! For the first an

31、d last stop; 37for(cities(i) | i #gt# 1 : 38 level(i)=1+(n-2)*x(i,1); 40); END水平變量水平變量(level)仍然是用來保證所選的邊除第仍然是用來保證所選的邊除第1點外不構(gòu)成圈的點外不構(gòu)成圈的.計算結(jié)果如下：計算結(jié)果如下：旅行商問題的數(shù)學(xué)規(guī)劃模型旅行商問題的數(shù)學(xué)規(guī)劃模型Global optimal solution found at iteration: 90Objective value: 73.00000 Variable Value Reduced Cost X( 1, 2) 1.000000 8.000000

32、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( 10, 8) 1.000000 11.00000旅行商問題的數(shù)學(xué)規(guī)劃模型旅行商問題的數(shù)學(xué)規(guī)劃模型旅行商經(jīng)過旅行商經(jīng)過10 個城鎮(zhèn)的最短距離為個城鎮(zhèn)的最短距離為7

33、3公里，其連公里，其連接情況如圖所示接情況如圖所示.最佳災(zāi)情巡視路線的模型的建立與求解最佳災(zāi)情巡視路線的模型的建立與求解問題轉(zhuǎn)化為在問題轉(zhuǎn)化為在給定的加權(quán)網(wǎng)給定的加權(quán)網(wǎng)絡(luò)圖中尋找從絡(luò)圖中尋找從給定點給定點O O出發(fā)出發(fā), ,行遍所有頂點行遍所有頂點至少一次再回至少一次再回回到點回到點O ,O ,使得使得總權(quán)總權(quán)( (路程或時路程或時時間時間) )最小最小, ,即即最佳旅行推銷最佳旅行推銷員問題員問題. .最佳旅行推銷員問題是最佳旅行推銷員問題是NPNP完全問題完全問題, ,采用一種采用一種近似算法求其一個近似最優(yōu)解，來代替最優(yōu)解近似算法求其一個近似最優(yōu)解，來代替最優(yōu)解. .算法一算法一 求加權(quán)

34、圖的最佳旅行推銷員回路近似算法求加權(quán)圖的最佳旅行推銷員回路近似算法: : 1) 1) 用圖論軟件包求出用圖論軟件包求出G G中任意兩個頂點間的最短路中任意兩個頂點間的最短路, , 構(gòu)造出完全圖構(gòu)造出完全圖),(,),(),(yxEyxEVG);,(minyxdG2) 2) 輸入圖輸入圖 的一個初始的一個初始H H圈；圈；G3) 3) 用對角線完全算法產(chǎn)生一個初始圈用對角線完全算法產(chǎn)生一個初始圈; ;4) 4) 隨機(jī)搜索出隨機(jī)搜索出 中若干個中若干個H H圈，例如圈，例如20002000個；個；G5) 5) 對第對第2)2)，3)3)，4)4)步所得的每個步所得的每個H H圈，用二邊逐次圈，用二

35、邊逐次修正法進(jìn)行優(yōu)化，得到近似最優(yōu)修正法進(jìn)行優(yōu)化，得到近似最優(yōu)H H圈；圈；6) 6) 在第在第5)5)步求出的所有步求出的所有H H圈中，找出權(quán)最小的一個圈中，找出權(quán)最小的一個, , 此即要找的最優(yōu)此即要找的最優(yōu)H H圈的近似解圈的近似解. .因二邊逐次修正法的結(jié)果與初始圈有關(guān)因二邊逐次修正法的結(jié)果與初始圈有關(guān), ,故本算法故本算法第第2)2)，3)3)，4)4)步分別用三種方法產(chǎn)生初始圈，以保步分別用三種方法產(chǎn)生初始圈，以保證能得到較優(yōu)的計算結(jié)果證能得到較優(yōu)的計算結(jié)果. . 問題一問題一 若分為三組巡視，設(shè)計總路程最短且各若分為三組巡視，設(shè)計總路程最短且各組盡可能均衡的巡視路線組盡可能均衡

36、的巡視路線. . 此問題是多個推銷員的最佳旅行推銷員問題此問題是多個推銷員的最佳旅行推銷員問題. .4)min)(1niiC 此問題包含兩方面：此問題包含兩方面：a)a)對頂點分組對頂點分組, b), b)在每組中在每組中求求( (單個推銷員單個推銷員) )最佳旅行推銷員回路最佳旅行推銷員回路. . 因單個推銷員的最佳旅行推銷員回路問題不存因單個推銷員的最佳旅行推銷員回路問題不存存在多項式時間內(nèi)的精確算法存在多項式時間內(nèi)的精確算法. . 而圖中節(jié)點數(shù)較多，為而圖中節(jié)點數(shù)較多，為5353個，我們只能去尋求個，我們只能去尋求一種較合理的劃分準(zhǔn)則，對圖一種較合理的劃分準(zhǔn)則，對圖1 1進(jìn)行初步劃分后進(jìn)

37、行初步劃分后, ,求求出各部分的近似最佳旅行推銷員回路的權(quán)出各部分的近似最佳旅行推銷員回路的權(quán), ,再進(jìn)一再進(jìn)一步進(jìn)行調(diào)整，使得各部分滿足均衡性條件步進(jìn)行調(diào)整，使得各部分滿足均衡性條件3).3). 從從O O點出發(fā)去其它點，要使路程較小應(yīng)盡量走點出發(fā)去其它點，要使路程較小應(yīng)盡量走O O點到該點的最短路點到該點的最短路. . 故用軟件包求出故用軟件包求出O O點到其余頂點的最短路點到其余頂點的最短路. . 這些最短路構(gòu)成一棵這些最短路構(gòu)成一棵O O為樹根的樹為樹根的樹. .將從將從O O點出發(fā)的樹枝稱為點出發(fā)的樹枝稱為干枝干枝. .從從O點出發(fā)到其它點共有點出發(fā)到其它點共有6條干枝，它們的名稱條

38、干枝，它們的名稱分別為，分別為，. 在分組時應(yīng)遵從準(zhǔn)則：在分組時應(yīng)遵從準(zhǔn)則： 準(zhǔn)則準(zhǔn)則1 盡量使同一干枝上及其分枝上的點分在同一組盡量使同一干枝上及其分枝上的點分在同一組.準(zhǔn)則準(zhǔn)則2 應(yīng)將相鄰的干枝上的點分在同一組；應(yīng)將相鄰的干枝上的點分在同一組； 準(zhǔn)則準(zhǔn)則3 盡量將長的干枝與短的干枝分在同一組盡量將長的干枝與短的干枝分在同一組.由上述分組準(zhǔn)則，我們找到兩種分組形式如下：由上述分組準(zhǔn)則，我們找到兩種分組形式如下：分組分組1:（，），（，），（，）（，），（，），（，）分組分組2:（，），（，），（，）（，），（，），（，）分組分組1極不均衡極不均衡,故考慮分組故考慮分組2.分組分組2:(,),

39、(,),(,) 對分組對分組2 2中每組頂點的生成子圖中每組頂點的生成子圖, ,用算法一求用算法一求出近似最優(yōu)解及相應(yīng)的巡視路線出近似最優(yōu)解及相應(yīng)的巡視路線. . 在每個子圖所構(gòu)造的完全圖中在每個子圖所構(gòu)造的完全圖中, ,取一個盡量包含取一個盡量包含上圖中樹上的邊的上圖中樹上的邊的H H圈作為其第圈作為其第2)2)步輸入的初始圈步輸入的初始圈. .分組分組2的近似解的近似解 因為該分組的均衡度因為該分組的均衡度54.2%9 .2415 .1259 .241)(max)()(3 , 2 , 1210iiCCC.所以此分法的均衡性很差所以此分法的均衡性很差. . 為改善均衡性，將第為改善均衡性，將第組中的頂點組中的頂點C C,2,3,2,3,D D,4,4分給第分給第組（頂點組（頂點2 2為這兩組的公共點），重新分為這兩組的公共點），重新分分組后的近似最優(yōu)解見表分組后的近似最優(yōu)解見表2.2.%.69.114 .2161 .1914 .216)(max)()(3 , 2 , 1130iiCCC因該分組的均衡度因該分組的均衡度 所以這種分法的均衡性較好所以這種分法的均衡性較好. . 問題二問題二 當(dāng)巡視人員在各鄉(xiāng)（鎮(zhèn)）、村的停留當(dāng)巡視人員在各鄉(xiāng)（鎮(zhèn)）、村的停留停留時間一定停留時間一定, ,汽車的行駛速度一定汽車的行駛速度一定, ,要在要在2424小時內(nèi)小時內(nèi)完成巡視完成巡