旅行商問題(TSP)課件

旅行商問題(TSP)參考書：1.龔劬《圖論與網(wǎng)絡(luò)最優(yōu)化算法》重慶大學(xué)出版社,20092.西北工業(yè)大學(xué)數(shù)學(xué)建模指導(dǎo)委員會(huì)《數(shù)學(xué)建模簡(jiǎn)明教程》高等教育出版社主講：重慶大學(xué)龔劬MathematicaModeling旅行商問題(TSP)主要內(nèi)容基本概念算法簡(jiǎn)介TSP模型的應(yīng)用最佳災(zāi)情巡視路線的模型的建立與求解引例旅行商問題(TSP)：引例1.98年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題“最佳災(zāi)

今年(1998年)夏天某縣遭受水災(zāi).為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視.巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線.情巡視路線”中的前兩個(gè)問題：旅行商問題(TSP)：引例1）若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線.2）假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車行駛速度V=35公里/小時(shí).要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下最佳的巡視路線.旅行商問題(TSP)引例公路邊的數(shù)字為該路段的公里數(shù).旅行商問題(TSP)引例2.問題分析本題給出了某縣的公路網(wǎng)絡(luò)圖，要求在不同的條件下，災(zāi)情巡視的最佳分組方案和路線.

將每個(gè)鄉(xiāng)（鎮(zhèn)）或村看作一個(gè)圖的頂點(diǎn)，各鄉(xiāng)鎮(zhèn)、村之間的公路看作此圖對(duì)應(yīng)頂點(diǎn)間的邊，各條公路的長(zhǎng)度（或行駛時(shí)間）看作對(duì)應(yīng)邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)圖，問題就轉(zhuǎn)化為圖論中一類稱之為旅行推銷員問題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)O出發(fā)，行遍所有頂點(diǎn)至少一次再回到點(diǎn)O，使得總權(quán)（路程或時(shí)間）最小.旅行商問題(TSP)旅行商問題(TSP，travelingsalesmanproblem)

一個(gè)商人欲到n個(gè)城市推銷商品，每?jī)蓚€(gè)城市i和j之間的距離為dij，如何選擇一條道路使得商人每個(gè)城市正好走一遍后回到起點(diǎn)且所走路線最短。：原始問題旅行商問題(TSP)圖論模型

構(gòu)造一個(gè)圖G=（V，E），頂點(diǎn)表示城市，邊表示連接兩城市的路，邊上的權(quán)W（e）表示距離（或時(shí)間或費(fèi)用）。于是旅行推銷員問題就成為在加權(quán)圖中尋找一條經(jīng)過每個(gè)頂點(diǎn)正好一次的最短圈的問題，即求最佳Hamilton圈的問題。

：原始問題旅行商問題(TSP)基本概念1)哈米爾頓路徑(H路徑):經(jīng)過圖G每個(gè)頂點(diǎn)正好一次的路徑;2)哈米爾頓圈(H圈)；經(jīng)過G的每個(gè)頂點(diǎn)正好一次的圈;3)哈米爾頓圖(H圖):含H圈的圖。4)最佳H圈:在加權(quán)圖G=（V，E）中，權(quán)最小的H圈；5)最佳推銷員回路:經(jīng)過每個(gè)頂點(diǎn)一次的權(quán)最小閉通路;6)TSP問題:在完備加權(quán)圖中求最佳H圈的問題。：旅行商問題(TSP)TSP問題舉例工件排序設(shè)有n個(gè)工件等待在一臺(tái)機(jī)床上加工，加工完i，接著加工j，這中間機(jī)器需要花費(fèi)一定的準(zhǔn)備時(shí)間tij，問如何安排加工順序使總調(diào)整時(shí)間最短？此問題可用TSP的方法求解，n個(gè)工件對(duì)應(yīng)n個(gè)頂點(diǎn)，tij表示(i,j)上的權(quán)，因此需求圖中權(quán)最小的H路徑。計(jì)算機(jī)布線

一個(gè)計(jì)算機(jī)接口含幾個(gè)組件。每個(gè)組件上都置有若干管腳。這些管腳需用導(dǎo)線連接。考慮到以后改變方便和管腳的細(xì)小。要求每個(gè)管腳最多連兩條線。為避免信號(hào)干擾以及布線的簡(jiǎn)潔，要求導(dǎo)線總長(zhǎng)度盡可能小。旅行商問題(TSP)TSP問題舉例計(jì)算機(jī)布線（續(xù)）問題容易轉(zhuǎn)化為TSP問題，每個(gè)管腳對(duì)應(yīng)于圖的頂點(diǎn)，d(x,y)代表兩管腳x與y的距離，原問題即為在圖中尋求最小權(quán)H路徑。電路板鉆孔

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

一般是以構(gòu)造型算法得到一個(gè)初始解，然后再用改進(jìn)型算法逐步改進(jìn)。常見的構(gòu)造型算法有兩種：Christofides最小權(quán)匹配算法，對(duì)角線完全算法。常見的改進(jìn)型算法有兩種：二次逐次修正法，F(xiàn)eiring矩陣逐次改進(jìn)法。

分枝定界法旅行商問題(TSP)算法簡(jiǎn)介

二次逐次修正法（1）任取初始H圈

C0=v1,v2,…,vi,…,vj,…vm,v1（2）對(duì)所有的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）C0C,重復(fù)步驟（2），直到條件不滿足為止，最后得到的C即為所求。旅行商問題(TSP)例對(duì)下圖的K6,用二邊逐次修正法求較優(yōu)H圈.較優(yōu)H圈:其權(quán)為W(C3)=192旅行商問題(TSP)

分析:這個(gè)解的近似程度可用最優(yōu)H圈的權(quán)的下界與其比較而得出.即利用最小生成樹可得最優(yōu)H圈的一個(gè)下界.

設(shè)C是G的一個(gè)最優(yōu)H圈，則對(duì)G的任一頂點(diǎn)v,C-v是G-v的生成樹.如果T是G-v的最小生成樹,且e1是e2與v關(guān)聯(lián)的邊中權(quán)最小的兩條邊,則w(T)+w(e1)+w(e2)將是w(C)的一個(gè)下界.取v=v3,得G-v3的一最小生成樹(實(shí)線),其權(quán)w(T)=122,與v3關(guān)聯(lián)的權(quán)最小的兩條邊為v1v3和v2v3,w(T)+w(v1v3)+w(v2v3)=178.故最優(yōu)H圈的權(quán)故w(C)應(yīng)滿足178w(C)192.旅行商問題(TSP)對(duì)角線完全算法結(jié)論:若能在n×n距離矩陣中找出n個(gè)不同行也不同列的元素，使它們的和為最小值。若這n個(gè)元素構(gòu)成一條哈米爾頓圈時(shí)，此圈便是最佳H圈。矩陣的簡(jiǎn)化

:將矩陣的每一行的各元素減去本行的最小元素稱為對(duì)行簡(jiǎn)化，從第i行減去的數(shù)稱為第i行的約數(shù)，記為R（i）。將矩陣的每一列的各元素減去本列的最小元素稱為對(duì)列簡(jiǎn)化，從第j列減去的數(shù)稱為第j列的約數(shù)，記為R’(j)。各行各列的約數(shù)之和稱為矩陣的約數(shù)，記為R。矩陣經(jīng)行的簡(jiǎn)化和列的簡(jiǎn)化后所得矩陣稱為該矩陣的簡(jiǎn)化矩陣。旅行商問題(TSP)對(duì)角線完全算法例求下列距離矩陣D的簡(jiǎn)化矩陣及各行，各列的約數(shù)。其中D中各行的約數(shù)R(1)=25，R(2)=5，R(3)=1，R(4)=6，R(5)=7旅行商問題(TSP)對(duì)角線完全算法D經(jīng)行簡(jiǎn)化得求出D’各列的約數(shù)R’(1)=0，R’(2)=0，R’(3)=0，R’(4)=3，R’(5)=0旅行商問題(TSP)對(duì)角線完全算法D’經(jīng)列簡(jiǎn)化得由于簡(jiǎn)化矩陣同一行各元素減同一數(shù)，同列各元素也是減同一數(shù)，因而每個(gè)H圈的權(quán)都減少同一數(shù)即R.旅行商問題(TSP)對(duì)角線完全算法定理設(shè)D’是圖G的距離矩陣D的簡(jiǎn)化矩陣，則D’對(duì)應(yīng)的圖G’的最佳（有向）H圈也是原圖G的最佳（有向）H圈。G’只是邊權(quán)與G不同，去掉權(quán)之后完全一樣。因此當(dāng)簡(jiǎn)化矩陣中的零元素構(gòu)成H圈時(shí)，該H圈也是原問題的最佳H圈。罰數(shù):在圖G的距離矩陣的簡(jiǎn)化矩陣D’中，第i行的最小元素與次小元素之差稱為第i行的罰數(shù)，記為P(i)。第j列的最小元素與次小元素之差稱為第j列的罰數(shù)，記為P’(j)，某行（或列）的罰數(shù)即是若H圈不選擇該行（或列）的最小元素會(huì)使其權(quán)增加的最小值。旅行商問題(TSP)對(duì)角線完全算法算法步驟輸入：圖的距離矩陣D（1）求D的簡(jiǎn)化矩陣D’以及各行各列的約數(shù)R(i)，

R’(j)，罰數(shù)P(i)，P’(j)（2）計(jì)算在簡(jiǎn)化矩陣中零元素所在行與列的罰數(shù)和，即P(i,j)=P(i)+P’(j)。將P(i,j)由大到小排列后，依次選取可作為可行部分路的邊（i,j）。這些邊對(duì)應(yīng)的零元素記為0*。用這些選擇出來的邊構(gòu)成可行部分路。定義一個(gè)H圈的一些不相交路徑稱為可行部分路。旅行商問題(TSP)對(duì)角線完全算法（3）構(gòu)造新的距離矩陣稱為重構(gòu)距離矩陣：按上述可行部分路的頂點(diǎn)序重新排列簡(jiǎn)化距離D’的行，列也按使上述所有“0*”位于對(duì)角線上的次序重新排列。（4）產(chǎn)生D的子陣：設(shè)重構(gòu)矩陣對(duì)角線上m個(gè)非零元素對(duì)應(yīng)的邊為(i1,j1),（i2,j2），…，（im,jm），則從D中取出相應(yīng)的m行，m列構(gòu)成一個(gè)m×m子陣D1。為保證選出的邊與原來的可行部分路不形成子循環(huán)，有m條邊不能選擇，將其對(duì)應(yīng)的元素置為∞。并將列作適當(dāng)調(diào)整使對(duì)角線元素為∞。（5）對(duì)D1重復(fù)（1）—（4）步，直到重構(gòu)矩陣對(duì)角線上的元素全為0為止，這時(shí)便可得到一個(gè)H圈。旅行商問題(TSP)對(duì)角線完全算法例用對(duì)角線完全法求加權(quán)圖K10的較佳H圈旅行商問題(TSP)對(duì)角線完全算法12345678910RiPi1∞019830034838811651942412022011620∞01101641900321247341980325658∞060516181150681406443824880∞0701971779067606754863021400∞8324915430456030645625861013∞700681171300716852011116354∞103243208410528587389191107840119∞73163197739532355200600108299113∞09001022814211837151572642030∞32015Rj2200000264670230Pj168520005161033034旅行商問題(TSP)對(duì)角線完全算法2求出以上第一級(jí)簡(jiǎn)化陣中零元素對(duì)應(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旅行商問題(TSP)對(duì)角線完全算法現(xiàn)依次從上述各邊選擇能形成可行部分路的邊，先選第一邊（1，2），之后（2，1），（2，1）不行，因（1，2），（2，1）形成子循環(huán)；接著(8，6),但（6，8）不行，（6，8）會(huì)與（8，6）構(gòu)成子循環(huán)；再下是(4,5),(7,3),(10,9)，但(9,10)不能入選；(5,4)也不能入選，因會(huì)和前面選中的(4,5)構(gòu)成子循環(huán)；接著是(2,7),(3,4),但(2,3)不能入選，否則與(2,7)會(huì)使2的出次大于1。同理（6，4），（9，5）也不能入選。綜上得到可形成可行部分路的邊為：(1,2),(8,6),(4,5),(7,3),(10,9),(2,7)和(3,4)。它們對(duì)應(yīng)的零元素為0*。

可行部分路：1-2-7-3-4-5，8-6和10-9，三條不相交路徑。旅行商問題(TSP)對(duì)角線完全算法2734586109110*20*70*30*40*528180·6477100·96443.以1，2，7，3，4，5，8，6，10，9的順序重新排列D′的行，為使所有0*位于對(duì)角線上，D′的列按2，7，3，4，5，8，6，10，9，1的順序排列，這樣便得到第一級(jí)重構(gòu)距離矩陣旅行商問題(TSP)對(duì)角線完全算法4.對(duì)角線上有三個(gè)非零元素281，477和644，其對(duì)應(yīng)的邊為：（5，8），（6，10）和（8，1），相應(yīng)的行數(shù)為5，6，9；列數(shù)為8，10，1。從原始權(quán)矩陣D中取出這三行，三列構(gòu)成一個(gè)3×3型的D的子陣：18105∞2813356608∞4779644270∞旅行商問題(TSP)對(duì)角線完全算法5.重復(fù)步驟（1）-（4），得到第二級(jí)簡(jiǎn)化矩陣及相應(yīng)的約數(shù)，罰數(shù)

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

98612734510100*90**80*60**10*20*70*30*40*5335最后還剩一個(gè)元素（5，10）不為零，沒有選擇余地，第三迭代必定是選（5，10）與前面得到的可行部分將一起構(gòu)成H圈10-9-8-6-1-2-7-3-4-5-10.旅行商問題(TSP)對(duì)角線完全算法因此第三級(jí)重構(gòu)距離矩陣只需在第二級(jí)距離矩陣中335換成0***即可。第三級(jí)重構(gòu)距離矩陣為：98612734510100*90**80*60**10*20*70*30*40*50***故所求H圈為：10-9-8-6-1-2-7-3-4-5-10，其權(quán)：W=3022。旅行商問題(TSP)旅行商問題的數(shù)學(xué)規(guī)劃模型旅行商問題(TSP)旅行商問題的數(shù)學(xué)規(guī)劃模型或旅行商問題(TSP)旅行商問題的數(shù)學(xué)規(guī)劃模型例用LINGO軟件求解

MODEL:1]sets:2]cities/1..10/:level;!level(i)=thelevelofcity;3]link(cities,cities):4]distance,!Thedistancematrix;5]x;!x(i,j)=1ifweuselinki,j;6]endsets7]data:!Distancematrix,itneednotbesymmetirc;8]distance=0859121412161722旅行商問題(TSP)旅行商問題的數(shù)學(xué)規(guī)劃模型9]809151681118142210]5907911712121711]91570317107151512]12169308106151513]14811178091481614]12117101090861115]161812761480111116]1714121515861101017]2222171515161111100;18]enddata19]n=@size(cities);!Themodelsize;20]!Minimizetotaldistanceofthelinks;旅行商問題(TSP)旅行商問題的數(shù)學(xué)規(guī)劃模型

21]min=@sum(link(i,j)|i#ne#j:distance(i,j)*x(i,j));22]!Forcityi;23]@for(cities(i):24]!Itmustbeentered;25]@sum(cities(j)|j#ne#i:x(j,i))=1;26]!Itmustbedeparted;27]@sum(cities(j)|j#ne#i:x(i,j))=1;28]!level(j)=levle(i)+1,ifwelinkjandi;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]);旅行商問題(TSP)旅行商問題的數(shù)學(xué)規(guī)劃模型34]!Makethex's0/1;35]@for(link:@bin(x));36]!Forthefirstandlaststop;37]@for(cities(i)|i#gt#1:38]level(i)<=n-1-(n-2)*x(1,i);39]level(i)>=1+(n-2)*x(i,1);40]);END水平變量(level)仍然是用來保證所選的邊除第1點(diǎn)外不構(gòu)成圈的.計(jì)算結(jié)果如下：旅行商問題(TSP)旅行商問題的數(shù)學(xué)規(guī)劃模型Globaloptimalsolutionfoundatiteration:90Objectivevalue:73.00000VariableValueReducedCostX(1,2)1.0000008.000000X(2,6)1.0000008.000000X(3,1)1.0000005.000000X(4,3)1.0000007.000000X(5,4)1.0000003.000000X(6,9)1.0000008.000000X(7,10)1.00000011.00000X(8,5)1.0000006.000000X(9,7)1.0000006.000000X(10,8)1.00000011.00000旅行商問題(TSP)旅行商問題的數(shù)學(xué)規(guī)劃模型旅行商經(jīng)過10個(gè)城鎮(zhèn)的最短距離為73公里，其連接情況如圖所示.旅行商問題(TSP)最佳災(zāi)情巡視路線的模型的建立與求解問題轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)O出發(fā),行遍所有頂點(diǎn)至少一次再回回到點(diǎn)O,使得總權(quán)(路程或時(shí)時(shí)間)最小,即最佳旅行推銷員問題.旅行商問題(TSP)最佳旅行推銷員問題是NP—完全問題,采用一種近似算法求其一個(gè)近似最優(yōu)解，來代替最優(yōu)解.算法一求加權(quán)圖的最佳旅行推銷員回路近似算法:1)用圖論軟件包求出G中任意兩個(gè)頂點(diǎn)間的最短路,

構(gòu)造出完全圖2)輸入圖的一個(gè)初始H圈；3)用對(duì)角線完全算法產(chǎn)生一個(gè)初始圈;4)隨機(jī)搜索出中若干個(gè)H圈，例如2000個(gè)；5)對(duì)第2)，3)，4)步所得的每個(gè)H圈，用二邊逐次修正法進(jìn)行優(yōu)化，得到近似最優(yōu)H圈；6)在第5)步求出的所有H圈中，找出權(quán)最小的一個(gè),此即要找的最優(yōu)H圈的近似解.因二邊逐次修正法的結(jié)果與初始圈有關(guān),故本算法第2)，3)，4)步分別用三種方法產(chǎn)生初始圈，以保證能得到較優(yōu)的計(jì)算結(jié)果.旅行商問題(TSP)

問題一

若分為三組巡視，設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線.

此問題是多個(gè)推銷員的最佳旅行推銷員問題.4)旅行商問題(TSP)

此問題包含兩方面：a)對(duì)頂點(diǎn)分組,b)在每組中求(單個(gè)推銷員)最佳旅行推銷員回路.

因單個(gè)推銷員的最佳旅行推銷員回路問題不存存在多項(xiàng)式時(shí)間內(nèi)的精確算法.旅行商問題(TSP)

而圖中節(jié)點(diǎn)數(shù)較多，為53個(gè)，我們只能去尋求一種較合理的劃分準(zhǔn)則，對(duì)圖1進(jìn)行初步劃分后,求出各部分的近似最佳旅行推銷員回路的權(quán),再進(jìn)一步進(jìn)行調(diào)整，使得各部分滿足均衡性條件3).

從O點(diǎn)出發(fā)去其它點(diǎn)，要使路程較小應(yīng)盡量走O點(diǎn)到該點(diǎn)的最短路.

故用軟件包求出O點(diǎn)到其余頂點(diǎn)的最短路.

這些最短路構(gòu)成一棵O為樹根的樹.將從O點(diǎn)出發(fā)的樹枝稱為干枝.旅行商問題(TSP)從O點(diǎn)出發(fā)到其它點(diǎn)共有6條干枝，它們的名稱分別為①，②，③，④，⑤，⑥.

在分組時(shí)應(yīng)遵從準(zhǔn)則：準(zhǔn)則1

盡量使同一干枝上及其分枝上的點(diǎn)分在同一組.準(zhǔn)則2應(yīng)將相鄰的干枝上的點(diǎn)分在同一組；準(zhǔn)則3

盡量將長(zhǎng)的干枝與短的干枝分在同一組.由上述分組準(zhǔn)則，我們找到兩種分組形式如下：分組1:（⑥，①），（②，③），（⑤，④）分組2:（①，②），（③，④），（⑤，⑥）分組1極不均衡,故考慮分組2.旅行商問題(TSP)分組2:(①,②),(③,④),(⑤,⑥)

對(duì)分組2中每組頂點(diǎn)的生成子圖,用算法一求出近似最優(yōu)解及