旅行商問題(TSP)課件

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

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

將每個鄉(xiāng)（鎮(zhèn)）或村看作一個圖的頂點，各鄉(xiāng)鎮(zhèn)、村之間的公路看作此圖對應頂點間的邊，各條公路的長度（或行駛時間）看作對應邊上的權，所給公路網就轉化為加權圖，問題就轉化為圖論中一類稱之為旅行推銷員問題，即在給定的加權網絡圖中尋找從給定點O出發(fā)，行遍所有頂點至少一次再回到點O，使得總權（路程或時間）最小.引例2.問題分析本題給出了某縣的公路網絡圖，要求在不同旅行商問題(TSP，travelingsalesmanproblem)

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

構造一個圖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圈的問題。：基本概念1)哈米爾頓路徑(H路徑):經過圖G每個頂點正好TSP問題舉例工件排序設有n個工件等待在一臺機床上加工，加工完i，接著加工j，這中間機器需要花費一定的準備時間tij，問如何安排加工順序使總調整時間最短？此問題可用TSP的方法求解，n個工件對應n個頂點，tij表示(i,j)上的權，因此需求圖中權最小的H路徑。計算機布線

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

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

一般是以構造型算法得到一個初始解，然后再用改進型算法逐步改進。常見的構造型算法有兩種：Christofides最小權匹配算法，對角線完全算法。常見的改進型算法有兩種：二次逐次修正法，Feiring矩陣逐次改進法。

分枝定界法算法簡介近似算法或啟發(fā)式算法算法簡介

二次逐次修正法（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即為所求。算法簡介二次逐次修正法（1）任取初始H圈例對下圖的K6,用二邊逐次修正法求較優(yōu)H圈.較優(yōu)H圈:其權為W(C3)=192例對下圖的K6,用二邊逐次修正法求較優(yōu)H圈.較優(yōu)H圈:其權為

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

設C是G的一個最優(yōu)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.故最優(yōu)H圈的權故w(C)應滿足178w(C)192.分析:這個解的近似程度可用最優(yōu)H圈的權的下界對角線完全算法結論:若能在n×n距離矩陣中找出n個不同行也不同列的元素，使它們的和為最小值。若這n個元素構成一條哈米爾頓圈時，此圈便是最佳H圈。矩陣的簡化

:將矩陣的每一行的各元素減去本行的最小元素稱為對行簡化，從第i行減去的數稱為第i行的約數，記為R（i）。將矩陣的每一列的各元素減去本列的最小元素稱為對列簡化，從第j列減去的數稱為第j列的約數，記為R’(j)。各行各列的約數之和稱為矩陣的約數，記為R。矩陣經行的簡化和列的簡化后所得矩陣稱為該矩陣的簡化矩陣。對角線完全算法結論:若能在n×n距離矩陣中找出n個不同行對角線完全算法例求下列距離矩陣D的簡化矩陣及各行，各列的約數。其中D中各行的約數R(1)=25，R(2)=5，R(3)=1，R(4)=6，R(5)=7對角線完全算法例求下列距離矩陣D的簡化矩陣及各行，各列對角線完全算法D經行簡化得求出D’各列的約數R’(1)=0，R’(2)=0，R’(3)=0，R’(4)=3，R’(5)=0對角線完全算法D經行簡化得求出D’各列的約數對角線完全算法D’經列簡化得由于簡化矩陣同一行各元素減同一數，同列各元素也是減同一數，因而每個H圈的權都減少同一數即R.對角線完全算法D’經列簡化得由于簡化矩陣同一行各元素減同一對角線完全算法定理設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’是圖G的距離矩陣D的簡化矩陣，對角線完全算法算法步驟輸入：圖的距離矩陣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圈的一些不相交路徑稱為可行部分路。對角線完全算法算法步驟定義一個H圈的一些不相交路徑稱為對角線完全算法（3）構造新的距離矩陣稱為重構距離矩陣：按上述可行部分路的頂點序重新排列簡化距離D’的行，列也按使上述所有“0*”位于對角線上的次序重新排列。（4）產生D的子陣：設重構矩陣對角線上m個非零元素對應的邊為(i1,j1),（i2,j2），…，（im,jm），則從D中取出相應的m行，m列構成一個m×m子陣D1。為保證選出的邊與原來的可行部分路不形成子循環(huán)，有m條邊不能選擇，將其對應的元素置為∞。并將列作適當調整使對角線元素為∞。（5）對D1重復（1）—（4）步，直到重構矩陣對角線上的元素全為0為止，這時便可得到一個H圈。對角線完全算法（3）構造新的距離矩陣稱為重構距離矩陣：按上對角線完全算法例用對角線完全法求加權圖K10的較佳H圈對角線完全算法例用對角線完全法求加權圖K10的較佳對角線完全算法12345678910RiPi1∞019830034838811651942412022011620∞01101641900321247341980325658∞060516181150681406443824880∞0701971779067606754863021400∞8324915430456030645625861013∞700681171300716852011116354∞103243208410528587389191107840119∞73163197739532355200600108299113∞09001022814211837151572642030∞32015Rj2200000264670230Pj168520005161033034對角線完全算法12345678910RiPi1∞01983對角線完全算法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對角線完全算法2求出以上第一級簡化陣中零元素對應的罰數，對角線完全算法現依次從上述各邊選擇能形成可行部分路的邊，先選第一邊（1，2），之后（2，1），（2，1）不行，因（1，2），（2，1）形成子循環(huán)；接著(8，6),但（6，8）不行，（6，8）會與（8，6）構成子循環(huán)；再下是(4,5),(7,3),(10,9)，但(9,10)不能入選；(5,4)也不能入選，因會和前面選中的(4,5)構成子循環(huán)；接著是(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的順序排列，這樣便得到第一級重構距離矩陣對角線完全算法2734586109110*20*70*30對角線完全算法4.對角線上有三個非零元素281，477和644，其對應的邊為：（5，8），（6，10）和（8，1），相應的行數為5，6，9；列數為8，10，1。從原始權矩陣D中取出這三行，三列構成一個3×3型的D的子陣：18105∞2813356608∞4779644270∞對角線完全算法4.對角線上有三個非零元素281，477和對角線完全算法5.重復步驟（1）-（4），得到第二級簡化矩陣及相應的約數，罰數

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

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.對角線完全算法上述頂點序得到第二級重構距離矩陣98612對角線完全算法因此第三級重構距離矩陣只需在第二級距離矩陣中335換成0***即可。第三級重構距離矩陣為：98612734510100*90**80*60**10*20*70*30*40*50***故所求H圈為：10-9-8-6-1-2-7-3-4-5-10，其權：W=3022。對角線完全算法因此第三級重構距離矩陣只需在第二級距離矩陣中旅行商問題的數學規(guī)劃模型旅行商問題的數學規(guī)劃模型旅行商問題的數學規(guī)劃模型或旅行商問題的數學規(guī)劃模型或旅行商問題的數學規(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旅行商問題的數學規(guī)劃模型例用LINGO軟件求解MOD旅行商問題的數學規(guī)劃模型9]809151681118142210]5907911712121711]91570317107151512]12169308106151513]14811178091481614]12117101090861115]161812761480111116]1714121515861101017]2222171515161111100;18]enddata19]n=@size(cities);!Themodelsize;20]!Minimizetotaldistanceofthelinks;旅行商問題的數學規(guī)劃模型9]旅行商問題的數學規(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]);旅行商問題的數學規(guī)劃模型21]min=@sum(link旅行商問題的數學規(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點外不構成圈的.計算結果如下：旅行商問題的數學規(guī)劃模型34]!Makethex旅行商問題的數學規(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旅行商問題的數學規(guī)劃模型Globaloptimalsol旅行商問題的數學規(guī)劃模型旅行商經過10個城鎮(zhèn)的最短距離為73公里，其連接情況如圖所示.旅行商問題的數學規(guī)劃模型旅行商經過10個城鎮(zhèn)的最短距離為7最佳災情巡視路線的模型的建立與求解問題轉化為在給定的加權網絡圖中尋找從給定點O出發(fā),行遍所有頂點至少一次再回回到點O,使得總權(路程或時時間)最小,即最佳旅行推銷員問題.最佳災情巡視路線的模型的建立與求解問題轉化為在給定的加權網絡最佳旅行推銷員問題是NP—完全問題,采用一種近似算法求其一個近似最優(yōu)解，來代替最優(yōu)解.算法一求加權圖的最佳旅行推銷員回路近似算法:1)用圖論軟件包求出G中任意兩個頂點間的最短路,

構造出完全圖2)輸入圖的一個初始H圈；3)用對角線完全算法產生一個初始圈;4)隨機搜索出中若干個H圈，例如2000個；5)對第2)，3)，4)步所得的每個H圈，用二邊逐次修正法進行優(yōu)化，得到近似最優(yōu)H圈；6)在第5)步求出的所有H圈中，找出權最小的一個,此即要找的最優(yōu)H圈的近似解.因二邊逐次修正法的結果與初始圈有關,故本算法第2)，3)，4)步分別用三種方法產生初始圈，以保證能得到較優(yōu)的計算結果.最佳旅行推銷員問題是NP—完全問題,采用一種近似算法求其一個

問題一

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

此問題是多個推銷員的最佳旅行推銷員問題.4)問題一若分為三組巡視，設計總路程最短且各組盡可能均衡的巡

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

因單個推銷員的最佳旅行推銷員回路問題不存存在多項式時間內的精確算法.此問題包含兩方面：a)對頂點分組,b)在每組中求(單個

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

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

故用軟件包求出O點到其余頂點的最短路.

這些最短路構成一棵O為樹根的樹.將從O點出發(fā)的樹枝稱為干枝.而圖中節(jié)點數較多，為53個，我們只能去尋求一種較合理的劃從O點出發(fā)到其它點共有6條干枝，它們的名稱分別為①，②，③，④，⑤，⑥.

在分組時應遵從準則：準則1

盡量使同一干枝上及其分枝上的點分在同一組.準則2應將相鄰的干枝上的點分在同一組；準則3

盡量將長的干枝與短的干枝分在同一組.由上述分組準則，我們找到兩種分組形式如下：分組1:（⑥，①），（②，③），（⑤，④）分組2:（①，②），（③，④），（⑤，⑥）分組1極不均衡,故考慮分組2.從O點出發(fā)到其它點共有6條干枝，它們的名稱分別為①，②，③，分組2:(①,②),(③,④),(⑤,⑥)

對分組2中每組頂點的生成子圖,用算法一求出近似最優(yōu)解及相應的巡視路線.