旅行商問題匯總課件

1第7章旅行商問題1第7章旅行商問題2第7章旅行商問題1.問題概述

2.求解算法

2.1.下界和上界算法2.2.分支定界法

目錄2.5.競賽題2.3.動態(tài)規(guī)劃法2.5.近似算法2第7章旅行商問題1.問題概述2.求解算3§7-1問題概述

一、數(shù)學模型

1.標準TSP

旅行商問題（簡稱TSP），也稱貨郎擔問題或旅行推銷員問題，是運籌學中一個著名的問題，其一般提法為：有一個旅行商從城市1出發(fā)，需要到城市2、3、…、n去推銷貨物，最后返回城市1，若任意兩個城市間的距離已知，則該旅行商應如何選擇其最佳行走路線？3§7-1問題概述一、數(shù)學模型4TSP在圖論意義下又常常被稱為最小Hamilton圈問題，Euler等人最早研究了該問題的雛形，后來由英國的Hamilton爵士作為一個懸賞問題而提出。但這個能讓普通人在幾分鐘內就可理解的游戲之作，卻延續(xù)至今仍未能完全解決，成了一個世界難題。

TSP有著明顯的實際意義，如，郵局里負責到各信箱開箱取信的郵遞員，以及去各分局送郵件的汽車等，都會遇到類似的問題。有趣的是，還有一些問題表面上看似乎與TSP無關，而實質上卻可以歸結為TSP來求解。已經證明，TSP是個NP難題，除非P=NP，否則不存在有效算法。4TSP在圖論意義下又常常被稱為最小H5

記為賦權圖G=(V,E)，V為頂點集，E為邊集，各頂點間的距離dij已知。設則經典的TSP可寫為如下的數(shù)學規(guī)劃模型：5記為賦權圖G=(V,E)，V為頂點6

模型中，為集合中所含圖的頂點數(shù)。約束（7－1）和（7－2）意味著對每個點而言，僅有一條邊進和一條邊出；約束（7－3）則保證了沒有任何子回路解的產生。于是，滿足約束（7－1）、（7－2）和（7－3）的解構成了一條Hamilton回路。6模型中，為集合中所含圖的頂點數(shù)。7

當dij=dji

(i,j∈V)時，問題被稱為對稱型TSP，否則稱為非對稱型TSP。若對所有1≤i,j,k≤n

，有不等式dij+djk≥dik成立，則問題被稱為是滿足三角形不等式的，簡稱為ΔTSP。7當dij=dji(i,j∈V)時，82.擴展TSP(1)瓶頸TSP

瓶頸問題是最早從TSP延伸出來的一種擴展型TSP，其含義與經典的TSP類似，僅目標不同，要求巡回路線中經過的最長距離最短，即最小化瓶頸距離。該情形體現(xiàn)了那些并不追求總巡回路線最短，而只希望在巡回路線中每次從一個地點至另一個地點的單次行程盡可能短的實際應用問題的特征。82.擴展TSP9

從嚴格的數(shù)學意義而言，瓶頸TSP（簡稱BTSP）并沒有降低問題的難度，也未能提供任何特殊的解決辦法。瓶頸TSP的數(shù)學模型與標準TSP類似，僅目標函數(shù)不同：

由于目標函數(shù)為瓶頸值，故求得的最佳巡回路線與標準TSP的往往截然不同。9從嚴格的數(shù)學意義而言，瓶頸TSP（10(2)最小比率TSP最小比率TSP（簡稱MRTSP）是從經典TSP引申出來的另一個變形問題，假定從一個城市走到另一個城市可得到某種收益（記為），則MRTSP的目標就是確定最佳行走路線，使得回路的總行程與總收益之比最小。這種優(yōu)化目標的思想類似于人們日常生活中經常使用的費用效益比，與單純的總行程最短相比，往往更具實際意義。10(2)最小比率TSP11

假定收益的數(shù)學性質與相同，則最小比率TSP的數(shù)學模型也與標準TSP類似，僅目標函數(shù)不同：

毫無疑問，由于目標函數(shù)中的非線性因素，最小比率TSP的求解比之標準TSP顯得更為困難。11假定收益的數(shù)學性質與相同，則最小比率12(3)多人TSP

若標準TSP中，出發(fā)點有多個推銷員同時出發(fā)，各自行走不同的路線，使得所有的城市都至少被訪問過一次，然后返回出發(fā)點，要求所有推銷員的總行程最短，則問題就成為一個多人的旅行商問題（簡記MTSP）。令決策變量則MTSP的數(shù)學模型為：12(3)多人TSP則MTSP的數(shù)學模型為：13

假定原問題為對稱型MTSP，V={v0,v1,…vn-1}，v0為名推銷員出發(fā)點，記V‘={v01,v02,…v0m;v0,v1,…vn-1}，擴大的m-1個頂點稱為“人造頂點”，其距離矩陣也相應擴大，其中，位于出發(fā)點的m個頂點相互間的距離設定為∞，其他數(shù)值不變。13假定原問題為對稱型MTSP，V=14二、多面體理論從上世紀70年代開始的關于算法復雜性的研究表明，要想為TSP找到一個好的算法，也即多項式算法，似乎是不可能的。由于推銷員的每條路線可以用一個以1開始的排列來表示，因此所有可能的路線有條。這樣，若用枚舉法來解決這一問題，即使不太大，例如n＝30，用目前最快的計算機，也要化幾百萬年才能求出一條最短的路線。14二、多面體理論15

早在1954年，Dantzig等人就曾提出過一種方法（非多項式算法），并且求出了一個42城市的TSP最優(yōu)解。到了1960年代，不少人用分支定界法解決了許多有幾十個城市的TSP。還有人提出了一些近似方法，也解決了許多有幾十個城市甚至上百個城市的TSP（有時找到的僅是近似解）。更值得注意的是，從1970年代中期開始，Grotschel與Padberg等人深入研究了TS多面體的最大面（facet），并從所得結果出發(fā)獲得了一種解TSP的新算法，可以解決一些有100多個城市的TSP，且都在不長的時間內找到了最優(yōu)解。15早在1954年，Dantzig16

考慮個頂點的完全圖Kn

，則解TSP就相當于在中求一條總長度最短的Hamilton回路。現(xiàn)在，對每條邊ej，定義一個變量xj與之對應，這樣，TSP的一條路線T，即Kn的一條Hamilton回路，就可對應一個向量X={x1,x2,….xm}，其中，16考慮個頂點的完全圖Kn，則解17

稱X為路線T的關聯(lián)向量，其m=n(n-2)/2個分量中，恰好有個為1，其余的都為0。圖有許多Hamilton回路，設為T1,T2…Ts,，對應的關聯(lián)向量記為X1,X2…Xs

，在m維空間Rm中，考慮這些向量生成的凸包（convexhull）Qn

：17稱X為路線T的關聯(lián)向量，其m=n18

Qn是Rm中的一個凸多面體，稱做TS多面體。顯然，Qn是有界的，其極點正好是Kn的Hamilton回路關聯(lián)向量。研究Qn的面非常重要的，因為根據(jù)線性不等式及凸多面體的理論，Qn一定是某一個有限線性不等式組的解集合，或者說，Qn一定是有限多個半空間的交。因此，如果能找出定義Qn的線性不等式組來，就可將TSP作為一個線性規(guī)劃來解。18Qn是Rm中的一個凸多面體，稱做19TS多面體研究中的一個重要問題就是尋找能導出Qn最大面的不等式，Grotschel等人發(fā)現(xiàn)了一類很重要的能導出最大面的梳子不等式，并予以了證明。此外，還有其它能導出最大面的不等式，如團樹不等式等。可見，Qn的最大面極多，曾經計算過由梳子不等式所導出的最大面?zhèn)€數(shù)如表7－1所示：n6810203050120c(n)604142088419701.5*10181.5*103110602*10179表7－119TS多面體研究中的一個重要問題就20

可以看出，當增大時，最大面?zhèn)€數(shù)增長得非?？?。在TS多面體理論的基礎上，可以考慮先解TSP的松弛問題，如果得到的最優(yōu)解正好是某一條路線的關聯(lián)向量，那么就找到TSP的最優(yōu)解了；否則，就設法找一些新的不等式作為額外約束，再解新的線性規(guī)劃，直至找到恰好是關聯(lián)向量的最優(yōu)解。這種做法的基本思想與解整數(shù)規(guī)劃的割平面法是同一類的，Gotschel等人曾用這種方法解過有120個城市的TSP，所增加的不等式只有子回路消去不等式與梳子不等式兩類，在進行了13輪計算后，即解了13個線性規(guī)劃后，就找到了TSP的精確最優(yōu)解，每一輪的當時計算時間僅在30秒至2分鐘之間。有趣的是，當n=120時，僅梳子不等式就有2*10179個，但在計算過程中，總共卻只（憑經驗）添加了96個子回路消去不等式與梳子不等式。20可以看出，當增大時，最大面?zhèn)€數(shù)增長得21

當然，用該方法有時會找不到TSP的最優(yōu)解，因為很可能在進行了幾輪迭代后，卻找不到新的不等式。Padborg與Hong曾計算了74個TSP，其中54個得到了最優(yōu)解，其余的雖未得到最優(yōu)解，卻得到了很好的下界，如果與近似方法配合，可以估計近似解的精確程度。如，他們解過一個有313個城市的TSP，獲得一個下界41236.46，而用近似方法能得到一條長為41349的路線，于是可估計出所得近似解與最優(yōu)解的誤差不超過0.26%。21當然，用該方法有時會找不到22§7-2求解算法一、下界和上界算法1.下界（1）下界b1和b2

針對TSP對應圖的鄰接矩陣，將矩陣中每一行最小的元素相加，就可得到一個簡單的下界b1。經進一步改進，可得到更好的下界：考慮一個TSP的完整解，在每條路徑上，每個城市都有兩條鄰接邊，一條進，一條出，那么，如果把矩陣中每一行最小的兩個元素相加再除以2（不失一般性，可假定圖中所有距離權重都為整數(shù)），再對其結果向上取整，就可得到一個合理的下界b2。顯然，b2≥b1，因此，一般不采用b1作為TSP的下界。22§7-2求解算法一、下界和上界算法23例1已知TSP及其距離矩陣如圖7－1所示，試求其下界271563134253984(a)無向圖圖7－1無向圖及距離矩陣(b)距離矩陣23例1已知TSP及其距離矩陣如圖7－1所示，試求其下界24解：將矩陣中每一行最小的元素相加，1+3+1+3+2=10，即得b1=10。將矩陣中每一行最小的兩個元素相加再除以2，再對結果向上取整，即可得b2=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14。24解：將矩陣中每一行最小的元素相加，1+3+1+3+225（2）下界b3為便于描述下界b3，先定義如下符號：T：對稱TSP問題；n：結點總個數(shù)；w(i,j)：結點i與j之間距離；dmin(i,k)：與第i個結點關聯(lián)的所有邊中第k(k=1,2,3)長邊的長度；dmin_j(i,k)：與第i個結點關聯(lián)的所有邊中第k(k=1,2,3)長邊的另一個結點的編號(其中一個結點編號為i)；node_base(i)=dmin_j(i,1)+dmin_j(i,2)：表示與i點關聯(lián)邊中長度最短的兩條邊之和；C*(T)：最優(yōu)回路長度；25（2）下界b326

于是，dmin(i,1)代表與第i個結點關聯(lián)的所有邊中最長邊的長度，dmin_j(i,1)代表與第i個結點關聯(lián)的所有邊中次長邊的另一個結點編號(其中一個結點編號為i)，第i結點的dmin(i,k)和dmin_j(i,k)可由距離矩陣w輕易求得。通過對下界b2進行改進，可以得出一個求對稱型TSP更好的下界b3。在求b2的過程中，只有當與每一結點關聯(lián)的邊中長度最小的兩條邊都出現(xiàn)在最優(yōu)TSP回路中時，等號才成立，下面就來分析如何提高這個下界。26于是，dmin(i,1)代表與第27

對結點i而言，設e(i)1與e(i)2分別為與結點i關聯(lián)的邊中長度最小的兩條邊，其長度分別為dmin(i,1)和dmin(i,2)。在對稱型TSP回路中，由于有且僅有兩條邊與每一結點關聯(lián)，因此，并不是與每個結點關聯(lián)的最小兩條邊都能出現(xiàn)在最優(yōu)TSP回路中，這意味可以在node_base(i)的基礎上增加TSP回路的長度，將在這種情況下增加的長度記為Adjust(T)，現(xiàn)在分析如何計算Adjust(T)。27對結點i而言，設e(i)1與e28

對結點i的e(i)1，邊e(i)1的一個結點為i，另一個結點為j=dmin_j(i,1)，若e(i)1也是結點j關聯(lián)邊中最小的兩條邊之一，即i=dmin_j(j,1)或i=dmin_j(j,2)，則對邊e(i)1來說就不需要調整，否則按以下方式調整：28對結點i的e(i)1，邊e29若e(i)1不是結點j=dmin_j(i,1)關聯(lián)邊中最小的兩條邊之一，則只有以下兩種情況：①選中e(i)1到TSP回路中此時對結點i不需調整，對結點j來說，由于邊e(i)1出現(xiàn)在最優(yōu)回路中，而e(i)1不是結點j關聯(lián)邊中最小的兩條邊之一，因此會造成結點j關聯(lián)邊中最小的兩條邊中至少有一條不會出現(xiàn)在最優(yōu)回路中，從而對結點j而言，在node_base(i)的基礎上至少會增加的長度為dmin(i,1)–dmin(j,2)。29若e(i)1不是結點j=dmin_j(i,1)關聯(lián)邊中30②不選中e(i)1到TSP回路中此時對結點i需要調整，由于邊e(i)1不在回路中，故其在node_base(i)的基礎上至少會增加的長度為dmin(i,3)–dmin(i,1)。此時對結點j來說，由于與它關聯(lián)的最短兩條邊仍然可能在回路中，因此不須調整。30②不選中e(i)1到TSP回路中31

對于①和②，必須有且僅有一種情況出現(xiàn)，現(xiàn)取兩種情況中增加長度小的值，因而回路的長路一定會在b2的基礎上增加：add_node(i,1)=1/2*min(dmin(i,3)–dmin(i,1),dmin(i,1)–dmin(j,2))。對結點i的e(i)2，邊e(i)2的一個結點為i，另一個結點為j=dmin_j(i,2)，若e(i)2也是結點j關聯(lián)邊中最小的兩條邊之一，則對邊e(i)2來說不需要調整，否則按與前面類似的方法計算調整值。經分析，其在base(T)的基礎上至少要增加：add_node(i,2)=1/2*min(dmin(i,3)–dmin(i,2),dmin(i,2)–dmin(j,2))。31對于①和②，必須有且僅有一種32

將每個結點都按上述方法進行一次調整，其調整累加和就是Adjust(T)，可寫成如下公式：32將每個結點都按上述方法進行一次33

將問題T中所有結點的基本長度node_base(T)累加之和的一半稱為T的基本長度，并用base(T)來表示，可寫成如下公式：33將問題T中所有結點的基本長度nod34

于是，有C*(T)≥base(T)+Adjust(T)=b3，即b3=b2+Adjust(T)。由以上分析，不難得出求對稱TSP下界b3的算法：34于是，有C*(T)≥base(T35Step1.計算base(T)：

get_base()

{

i:LongFori=1Tonbase=base+dmin(i,1)+dmin(i,2)}35Step1.計算base(T)：36Step2.計算Adjust(T)：get_adjust(){i,ii1,ii2:LongFori=1Ton{ii1=dmin_j(i,1);ii2=dmin_j(i,2)Ifi<>dmin_j(ii1,1)Andi<>dmin_j(ii1,2)adjust=adjust+min(dmin(i,3)-dmin(i,1),dmin(i,1)-dmin(ii1,2))Ifi<>dmin_j(ii2,1)Andi<>dmin_j(ii2,2)adjust=adjust+min(dmin(i,3)-dmin(i,2),dmin(i,2)-dmin(ii2,2))}}36Step2.計算Adjust(T)：37對例1而言，可計算其b3如下：dmin(1,1)=1；dmin_j(1,1)=3；dmin(1,2)=3；dmin_j(1,2)=2；dmin(1,3)=5；dmin_j(1,3)=4；dmin(2,1)=3；dmin_j(2,1)=1；dmin(2,2)=6；dmin_j(2,2)=3；dmin(2,3)=7；dmin_j(2,3)=4；dmin(3,1)=1；dmin_j(3,1)=1；dmin(3,2)=2；dmin_j(3,2)=5；dmin(3,3)=4；dmin_j(3,3)=4；271563134253984(a)無向圖圖7－1無向圖37對例1而言，可計算其b3如下：271563134253938dmin(4,1)=3；dmin_j(4,1)=5；dmin(4,2)=4；dmin_j(4,2)=3；dmin(4,3)=5；dmin_j(4,3)=1；dmin(5,1)=2；dmin_j(5,1)=3；dmin(5,2)=3；dmin_j(5,2)=4；dmin(5,3)=8；dmin_j(5,3)=1；271563134253984(a)無向圖圖7－1無向圖38dmin(4,1)=3；dmin_j(4,1)=5；39add_node(1,1)=0;add_node(1,2)=0;add_node(2,1)=0;add_node(2,2)=1/2×min((7-6),(6-2))=1/2;add_node(3,1)=0;add_node(3,2)=1/2×min((5-4),(4-2))=1/2;

add_node(4,1)=0;add_node(4,2)=0

;add_node(5,1)=0;add_node(5,2)=

0;

所以，Adjust(T)=1/2+1/2=1，得b3=b2+Adjust(T)=14+1=15。39add_node(1,1)=0;add_node(1402.上界事實上，TSP的任何可行解都是上界，這里，給出求TSP上界U1的貪心方法思想。算法步驟如下：402.上界41Step1.圖G={V,E}中頂點個數(shù)為n=|V|，邊的條數(shù)m=|E|，令i為出發(fā)點，TSP_edge_n為加入到TSP回路中邊的條數(shù)且TSP_edge_n=0，TSP_edge為已加入到TSP回路中的邊集合且TSP_edge={}，k為當前頂點且k=i。Step2.從邊集

中選中一條代價最小的一條邊(k,h)，并執(zhí)行

TSP_edge_n=TSP_edge_n+1；

TSP_edge=TSP_edge+{(k,h)}；

k=h。Step3.若TSP_edge_n<(n-1)，則轉Step2。Step4.將邊(k,i)加入到TSP_edge中。41Step1.圖G={V,E}中頂點個數(shù)為n=42

求解結束后，TSP_edge中的邊都在TSP回路中。對例1，可用上述算法求得其路徑為：1→3→5→4→2→1，路徑長度1+2+3+7+3=16，這是TSP的一個上界U1。綜合上下界，就可得到例1目標函數(shù)的界為[15,16]。271563134253984(a)無向圖圖7－1無向圖42求解結束后，TSP_edge中的邊都在43二、分支定界法二、分支定界法分支定界法是一種在表示問題解空間的樹上進行系統(tǒng)搜索的精確算法，這里，介紹兩種求解TSP的分支定界方法。43二、分支定界法二、分支定界法44.基于上下界的分支定界法為用分支定界法求解TSP，需要計算某些邊在TSP回路中和某些邊不在TSP回路中等情況下的下界。若采用下界b2計算，由于每個頂點最多只有兩個關聯(lián)邊在TSP回路中，已在TSP回路中的邊則限制該邊的其它鄰接邊加入，因此，針對每個頂點，分4種情況來計算：44.基于上下界的分支定界法45(1)若某頂點沒有關聯(lián)邊在TSP回路中，則該頂點的計算方法與計算b2的方法相同，即把該頂點關聯(lián)的最短兩邊長度之和的一半加入到下界中；(2)若某頂點關聯(lián)的邊已有兩條邊e1和e2在TSP回路中，則不需要再加入與該頂點關聯(lián)最小兩條邊的長度，即此時把e1和e2長度之和的一半加入到下界中；(3)若某頂點關聯(lián)的邊已有一條邊e1在TSP回路中，則只需要再加入與該頂點關聯(lián)的最小邊長度，即把e1和該頂點關聯(lián)的最短一條邊的長度之和的一半加入到下界中；(4)若某頂點關聯(lián)邊集的子集E1不能出現(xiàn)在TSP回路中，則將E1從圖中刪除再計算b2即可；如某頂點已有兩關聯(lián)邊在回路中，則可將其它關聯(lián)邊刪除，同樣，可以將會與已加入到回路中的邊形成子圈的邊刪除。45(1)若某頂點沒有關聯(lián)邊在TSP回路中，則該頂點的計算46

如例1中所示的無向圖，若其TSP回路包含邊(1,4)，則該部分解的下界b2=((1+5)+(3+6)+(1+2)+(3+5)+(2+3))/2=16，此時計算其下界時，由于邊(1,4)已在回路中，故與頂點1關聯(lián)的邊只需再加入一條最短邊(1,3)。若TSP回路包含邊(1,2)和(2,4)，則這時的下界b2=((1+3)+(3+7)+(1+2)+(3+7)+(2+3))/2=16。271563134253984(a)無向圖圖7－1無向圖46如例1中所示的無向圖，若其TSP回47

為描述方便，用eij

=1表示邊(i,j)在TSP回路中，eij

=0表示邊(i,j)不在TSP回路中。下面給出用分支定界法求解例1的過程（如圖7－2所示）：47為描述方便，用eij=1表示邊(48圖7－2分支定界求解過程U1=16e13=0e13=1b2=17.5>U1,故剪支e12=0e12=1b2=17>U1,故剪支得最優(yōu)解e12=e13=e24=e35=e54=1,

e14=e15=e23=e25=e34=0e25=0e25=1b2=18.5>U1=16,故剪支此時有e14=e15=e23=0此時有e24=e35=e54=1,e34=048圖7－2分支定界求解過程U1=16e13=0e149(1)用貪心算法求得上界U1=16；

(2)假定邊(1,3)不在TSP回路中，即e13=0，此時，b2=((5+3)+(3+6)+(4+2)+(3+4)+(2+3))/2=17.5，由于b2=17.5>U1=16，因此邊(1,3)一定在回路中，即e13=1；(3)在e13=1的情況下，假定e12=0，此時b2=((1+5)+(6+7)+(1+2)+(3+4)+(2+3))/2=17，由于b2=17>U1=16，因此邊(1,2)一定在回路中，即e12=1；49(1)用貪心算法求得上界U1=16；50(4)在e12=e13=1的情況下，由于頂點1已有兩條關聯(lián)邊在最優(yōu)回路中，因此在圖7－1中刪去邊(1,4)和(1,5)，由于邊(2,3)與邊(1,2)、(1,3)形成圈，因此在圖7－1中刪去邊(2,3)，即此時e14=e15=e23=0；(5)在e12=e13=1，e14=e15=e23=0的情況下，假定e25=1，此時b2=((1+3)+(3+9)+(1+2)+(3+4)+(2+9))/2=18.5，由于b2=18.5>U1=16，因此邊(2,5)一定不在回路中，即e25=0；50(4)在e12=e13=1的情況下，由于頂點51在e12=e13=1，e14=e15=e23=e25=0的情況下，由于與頂點2關聯(lián)的邊有且只有2條在回路中，因此有e24=1，進而有e35=e54=1，e34=0。

至此，得到最優(yōu)解：e12=e13=e24=e35=e54=1，e14=e15=e23=e25=e34=0；最優(yōu)目標值：1+2+3+7+3=16。51在e12=e13=1，e14=e15=e522.基于降階的分支定界法對于有向TSP的距離距陣，可通過不同情況下上下界的對比來確定某些邊(i,j)一定在或不在回路中。如果能確定(i,j)一定在回路中，由于每個頂點分別有且只有一條入邊和出邊，從而可確定頂點i的其它出邊一定不在回路中，也可以確定頂點j的其它出邊一定不在回路中，因此可將這些邊從距離距陣中去掉，從而達到降低矩陣階數(shù)的目的。這里，以一個具體的例子來予以說明。522.基于降階的分支定界法53例2已知有向TSP的距離矩陣如下：53例2已知有向TSP的距離矩陣如下：54解:

由于每個頂點都必須有一條入邊和出邊，因此將頂點i的所有出邊的權值減去所有出邊權值的最小值min_out(i)，不會影響最優(yōu)解，僅最優(yōu)值在原來的基礎上減少了min_out(i)。于是，可以將距離矩陣的每一行和每一列都減去該行或該列的最小值，直至每行每列都含有0為止。將上述矩陣的每行分別減去該行的最小值3,4,16,7,25,3，就得到如下縮減之后的矩陣：54解:由于每個頂點都必須有一條入邊和出邊，因此將頂點i55

該縮減矩陣所對應TSP的最優(yōu)解與原來的相同，但最優(yōu)值比原來減少了3+4+16+7+25+3=58。由于矩陣中第3、4列中不含0元素，因此可繼續(xù)縮減成：55該縮減矩陣所對應TSP的最優(yōu)解56該縮減矩陣所對應TSP的最優(yōu)解與原來的相同，但最優(yōu)值比原來減少了3+4+16+7+25+3=58。由于矩陣中第3、4列中不含0元素，因此可繼續(xù)縮減成：56該縮減矩陣所對應TSP的最優(yōu)解與原來的相同，但最優(yōu)值比原57

其最優(yōu)值比原來減少58+15+8=81，這個81可作為該TSP初始的下界值b。57其最優(yōu)值比原來減少58+15+58按e63=1和e63=0將解分成兩種情況：(1)e63=0

此時，邊(6,3)不能出現(xiàn)在回路中，其權值在這種情況下為∞，因此，距離矩陣可修改為：58按e63=1和e63=0將解分成兩種情況：59

由于第3列沒有0元素，故用第3列各元素減去其最小元素48，得如下縮減矩陣：

此時的下界b=81+48=129。59由于第3列沒有0元素，故用第60(2)e63=1

此時，邊(6,3)已出現(xiàn)在回路中，從頂點6出發(fā)的其它邊都不可能在回路中，因此可刪去第6行；同理，進入到頂點3的其它邊都不可能在回路中，因此又可刪去第3列。此時，邊(3,6)不可能出現(xiàn)在回路中，令邊(3,6)的權值為∞，矩陣化為：60(2)e63=161繼續(xù)依次計算，并實施分支和定界，具體過程如圖7－3所示：圖7－3降階分支定界過程b=81e63=0e63=1b=129e46=0e46=1b=113e21=0e21=1b=81b=81b=84b=101e14=1e14=0b=84b=112得可行回路(1,4,6,3,5,2,1),回路總長104，由此可將下界b大于104的分支剪去。61繼續(xù)依次計算，并實施分支和定界，具體過程如圖7－3所示：62e63=1，e46=0下的縮減矩陣：62e63=1，e46=0下的縮減矩陣：63e63=e46=1下的縮減矩陣：63e63=e46=1下的縮減矩陣：64e63=e46=1，e21=0下的縮減矩陣：64e63=e46=1，e21=0下的縮減矩陣：65e63=e46=e21=1下的縮減矩陣：65e63=e46=e21=1下的縮減矩陣：66e63=e46=e21=1，e14=0下的縮減矩陣：66e63=e46=e21=1，e14=0下67e63=e46=e21=e14=1下的縮減矩陣：67e63=e46=e21=e14=1下的縮68e63=e46=1，e21=e51=0下的縮減矩陣：68e63=e46=1，e21=e51=0下69e63=e46=e51=1，e21=0下的縮減矩陣：69e63=e46=e51=1，e21=0下的70e63=e46=e51=1，e21=e14=0下的縮減矩陣：70e63=e46=e51=1，e21=e171e63=e46=e51=e14=1，e21=0下的縮減矩陣：71e63=e46=e51=e14=1，e272

最后可得到兩個最優(yōu)TSP回路：(1,4,6,3,2,5,1)和(1,4,6,3,5,2,1)，最優(yōu)回路長度為104。若將無向圖中的每條邊看成有向圖中方向相反的兩條邊，則無向圖也可看成是有向圖，因此，基于降階的分支定界法也可用來求解無向TSP問題。72最后可得到兩個最優(yōu)TSP回路：73三、動態(tài)規(guī)劃法定理1TSP滿足最優(yōu)性原理。

最優(yōu)化原理可以表述為：“一個過程的最優(yōu)策略具有這樣的性質,即無論初始狀態(tài)和初始決策如何,對于先前決策所形成的狀態(tài)而言,其以后的所有決策必構成最優(yōu)策略，”73三、動態(tài)規(guī)劃法定理1TSP滿足最優(yōu)性原理。74證：設s,s1,s2,…,sp,s是從s出發(fā)的一條總長最短的簡單回路，假設從s到下一個城市s1已經求出，則問題轉化為求從s1到s的最短路徑，顯然s1,s2,…,sp,s一定構成一條從s1到s的最短路徑。若不然，設s1,r1,r2,…,rq,s是一條從s1到s的最短路徑且經過n-1個不同城市，則s,s1,r1,r2,…,rq,s將是一條從s出發(fā)的路徑長度最短的簡單回路且比s,s1,s2,…,sp,s要短，從而導致矛盾。所以，TSP滿足最優(yōu)性原理。74證：設s,s1,s2,…,sp,s是從s出75

設TSP頂點編號分別為0，1，2，…，n，假設從頂點0出發(fā)，令d(i,V')表示從頂點i出發(fā)經過V'中各頂點一次且僅一次，最后回到出發(fā)點0的最短路徑長度，中間計算過程中的d(k,V'－{k})也表示從頂點k

出發(fā)經過V'－{k}

中各頂點一次且僅一次，最后回到出發(fā)點0（注意不是k）的最短路徑長度。開始時，V'=V－{i}，cij為頂點i至頂點j的距離，于是，TSP的動態(tài)規(guī)劃遞推函數(shù)可寫成：75設TSP頂點編號分別為0，1，276d(i,V')=min{cik

+d(k,V'－{k})}(k∈V')d(k,{})=ck0

(k≠0

)例3求解有向TSP：76d(i,V')=min{cik+d(k77解：從城市0出發(fā)經城市1、2、3然后回到城市0的最短路徑長度為：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}這是最后一個階段的決策，而d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}，d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}，d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}；這一階段的決策又依賴于下述計算結果：77解：從城市0出發(fā)經城市1、2、3然后回到城市0的最短78d(1,{2})=c12+d(2,{})，d(2,{3})=c23+d(3,{})，d(3,{2})=c32+d(2,{})，d(1,{3})=c13+d(3,{})，d(2,{1})=c21+d(1,{})，d(3,{1})=c31+d(1,{})；而下式可以直接獲得（括號中是該決策引起的狀態(tài)轉移）：d(1,{})=c10=5(1→0)，d(2,{})=c20=6(2→0)，d(3,{})=c30=3(3→0)；78d(1,{2})=c12+d(2,{})79再向前倒推，有：d(1,{2})=c12+d(2,{})=2+6=8(1→2)，d(1,{3})=c13+d(3,{})=3+3=6(1→3)，d(2,{3})=c23+d(3,{})=2+3=5(2→3)，d(2,{1})=c21+d(1,{})=4+5=9(2→1)，d(3,{1})=c31+d(1,{})=7+5=12(3→1)，d(3,{2})=c32+d(2,{})=5+6=11(3→2)；79再向前倒推，有：80再向前倒推，有：d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}=min{2+5,3+11}=7(1→2)，d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}=min{4+6,2+12}=10(2→1)，d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}=min{7+8,5+9}=14(3→2)；80再向前倒推，有：81最后有：

d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}=min{3+7,6+10,7+14}=10(0→1)。即，從頂點0出發(fā)的TSP最短回路長度為10，回路路徑為：0→1→2→3→0。81最后有：82四、近似算法

由于精確式算法所能求解的問題規(guī)模非常有限，實際中真正使用的往往都是多項式階數(shù)的近似算法或啟發(fā)式算法，算法的好壞用C/C*≤ε來衡量，其中，C為近似算法所得的總行程，C*為最優(yōu)總行程，ε為最“壞“情況下近似與最優(yōu)總行程之比所不超過的上界值。這里，列舉幾個常見的TSP快速近似算法。82四、近似算法由于精確式算法所能求83

旅行售貨員問題的一些特殊性質：比如，費用函數(shù)w往往具有三角不等式性質，即對任意的3個頂點u,v,w∈V，有：w(u,w)≤w(u,v)+w(v,w)。當圖G中的頂點就是平面上的點，任意2頂點間的費用就是這2點間的歐氏距離時，費用函數(shù)w就具有三角不等式性質。

對于給定的無向圖G，可以利用找圖G的最小生成樹的算法設計找近似最優(yōu)的旅行售貨員回路的算法。

83旅行售貨員問題的一些特殊性質：84

當費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。

voidapproxTSP(Graphg){(1)選擇g的任一頂點r；

(2)用Prim算法找出帶權圖g的一棵以r為根的最小生成樹T；

(3)前序遍歷樹T得到的頂點表L；

(4)將r加到表L的末尾，按表L中頂點次序組成回路H，作為計算結果返回；}84當費用函數(shù)滿足三角不等式時，算法85(b)表示找到的最小生成樹T；(c)表示對T作前序遍歷的次序；(d)表示L產生的哈密頓回路H；(e)是G的一個最小費用旅行售貨員回路。

為什么：當費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。85(b)表示找到的最小生成樹T；(c)表示對T作前序遍歷的86答：存在一個最優(yōu)TSP回路TSPOPT，TSPOPT中共有n條邊，現(xiàn)去掉TOPT中最長的一條邊，得路徑POPT，POPT中共有n-1條邊，其總權值之和WTSP大于等于最小生成樹的總權值之和WT；即WTSP≥WT,下面只需證明該算法求得的TSP回路總長度之和WA小于等于2WT即可；把最小生成樹中的邊重復一次，再根據(jù)三角不等式就可得出結論（多次利用三角不等式）。

為什么：當費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。86答：存在一個最優(yōu)TSP回路TSPOPT，TSPOPT中87

把最小生成樹中的邊重復一次，再根據(jù)三角不等式就可得出結論（多次利用三角不等式）。（d）中藍色的邊為原來不在最小生成樹中的邊，最小生成樹中的邊重復一次及不在(d)中，但在(b)中的邊反復利用三角不等式就可得出結論。87把最小生成樹中的邊重復一次，再根881.插入算法插入型算法可按插入規(guī)則的不同而分為若干類，其一般思想為：Step1.通過某種插入方式選擇插入邊(i,j)和插入點k，將k

插入i

和j之間,形成{…,i,k,j,…}。Step2.依次進行，直至形成回路解。適用范圍：對稱型△TSP。具體實施中，可將出發(fā)點取遍V中各點而得到多個解，并從中選擇最好的一個，但此時的時間復雜度增加了n倍。主要的插入型算法有：881.插入算法89(1)最近插入法最壞情況：ε=2；時間復雜度：O(n2)。(2)最小插入法最壞情況：ε=2；時間復雜度：O(n2lgn)。(3)任意插入法最壞情況：ε=21gn+0.16；時間復雜度：O(n2)。(4)最遠插入法最壞情況：ε=21gn+0.16；時間復雜度：O(n2)。(5)凸核插入法最壞情況：ε=未知；時間復雜度：O(n2lgn)。89(1)最近插入法90插入法(InsertionMethod)

1任選一節(jié)點為起點a；2尋找距離節(jié)點a最近的節(jié)點b作為下一個造訪的節(jié)點，形成a-b-a的子回路；3尋找距離子回路最近的節(jié)點k作為下一個插入點；4尋找插入成本最小的位置(i-j)，將k插入i-j之間，形成新的子回路；

?插入成本：Cik+Ckj-Cij5重復步驟3~4，直到所有節(jié)點均已插入回路之中，即形成一個TSP的可行解。90插入法(InsertionMethod)

1任選一91插入法14235743875534814141333373337317224525727421455885845455582145541任選一節(jié)點為起點a；2尋找距離節(jié)點a最近的節(jié)點b作為下一個造訪的節(jié)點，形成a-b-a的子回路；3尋找距離子回路最近的節(jié)點k作為下一個插入點；4尋找插入成本最小的位置(i-j)，將k插入i-j之間，形成新的子回路；

?插入成本：Cik+Ckj-Cij5重復步驟3~4，直到所有節(jié)點均已插入回路之中，即形成一個TSP的可行解。91插入法1423574387553481414133337922.最近鄰算法Step1.任取一出發(fā)點。Step2.依次取最近的點加入當前解中，直至形成回路解。適用范圍：對稱型△TSP。具體實施中，可將出發(fā)點取遍V中各點而得到多個解，從中選擇最好的一個，但此時的時間復雜度增加了n倍。最壞情況：ε=(1gn+1)/2；時間復雜度：O(n2)。922.最近鄰算法93最近鄰點法(Nearest-neighborHeuristic)1任選一節(jié)點為起點x；2尋找距離節(jié)點x最近的節(jié)點y作為下一個造訪的節(jié)點；3尋找距離節(jié)點y最近的節(jié)點z作為下一個造訪的節(jié)點；4重復以上步驟，直到所有節(jié)點均已訪問；5連接最后一個節(jié)點與起點，即形成一個TSP的可行解；93最近鄰點法(Nearest-neighborHeuri94最近鄰點法14235743875534814235123451－473824－755377－344353－858548－94最近鄰點法14235743875534814235123953.雙生成樹算法Step1.首先求出最小生成樹。Step2.將樹中各邊都添一重復邊形成Euler圖，并求出其Euler回路。Step3.在Euler回路點序列中去除重復點，形成TSP回路解。適用范圍：對稱型△TSP。最壞情況：ε=2；時間復雜度：O(n2)。953.雙生成樹算法964Christofides算法Step1.首先求出最小生成樹。Step2.對樹中所有奇頂點求解最小權匹配問題。Step3.將匹配邊添入生成樹，并求出其Euler回路。Step4.在Euler回路點序列中去除重復點，形成TSP回路解。適用范圍：對稱型△TSP。最壞情況：ε=3/2；時間復雜度：O(n3)。964Christofides算法975.r-opt算法該方法是一種局部改進搜索算法，由Lin等人（1965）提出，其核心思想就是對給定的初始回路，通過每次交換r條邊來改進當前的解。適用范圍：對稱型△TSP。顯然，對不同的r，其優(yōu)劣次序為：2-opt，3-opt…r-opt。但是，大量計算發(fā)現(xiàn)，3-opt比2-opt好，而4-opt、5-opt等卻并不比3-opt來得優(yōu)越，況且r越大，運算時間越長。對于3-opt，有一個經驗公式告訴我們，其求得最優(yōu)解的概率近似為2-n/10，例如，對于n=50,有p=2-50/10=0.03，即，只要隨機選取150條初始路線，則求得最優(yōu)解的概率可達0.99。迄今為止，3-opt法仍是一種相當有效的近似算法。最壞情況:ε=2(n≥8,r≤n/4)；時間復雜度：O(nr

)。975.r-opt算法986.混合算法用某個近似算法求得初始解，然后借助一個或若干個r-opt算法對解加以改進。這種混合型的算法往往能獲得較好的解，但同時也很耗時，一般僅在對解有較高要求時采用。986.混合算法992-opt交換法先構建一個起始可行解在可行解中任選兩個不相鄰的節(jié)線(ab,cd)，以及另外兩條對應之替換節(jié)線(ac,bd)，計算替換后總成本是否降低(即檢查替換成本是否小于0)。?替換成本：Cac+Cbd-Cab-Ccd(對稱型TSP)

若替換后總成本有降低，則予以替換，同時變更中間相關弧線的行走方向。重復步驟2~3，直到所有可能的替換均無法再降低成本為止992-opt交換法先構建一個起始可行解1002-opt

交換法1423574387553481002-opt交換法142357438755348101如：98年全國數(shù)學建模競賽題B題是TSP問題

的一個變形

從縣城出發(fā)分三個小組巡視受災的地區(qū)各地的災情，已知每個村鎮(zhèn)所需要的停留時間以及行車速度，問如何設計各組的巡視路線才能以最快的速度掌握整個地區(qū)全部的受災情況？101如：98年全國數(shù)學建模競賽題B題是TSP問題

的一個變102災情巡視路線(CUMCM-1998B)多人TSP問題的擴展102災情巡視路線(CUMCM-1998B)多人TSP問題的103考慮用一個3個結點來代替縣城結點，

將問題轉化為一個TSP問題：103考慮用一個3個結點來代替縣城結點，

將問題轉化為一個T104再將三點收縮成一點，就得到

一個三個巡視組的TSP巡視路線

接下來的工作是要均衡各個巡視小組的工作時間（十分復雜的工作?。?04再將三點收縮成一點，就得到

一個三個巡視組的TSP巡視105TheEndThanks105TheEndThanks106第7章旅行商問題1第7章旅行商問題107第7章旅行商問題1.問題概述

2.求解算法

2.1.下界和上界算法2.2.分支定界法

目錄2.5.競賽題2.3.動態(tài)規(guī)劃法2.5.近似算法2第7章旅行商問題1.問題概述2.求解算108§7-1問題概述

一、數(shù)學模型

1.標準TSP

旅行商問題（簡稱TSP），也稱貨郎擔問題或旅行推銷員問題，是運籌學中一個著名的問題，其一般提法為：有一個旅行商從城市1出發(fā)，需要到城市2、3、…、n去推銷貨物，最后返回城市1，若任意兩個城市間的距離已知，則該旅行商應如何選擇其最佳行走路線？3§7-1問題概述一、數(shù)學模型109TSP在圖論意義下又常常被稱為最小Hamilton圈問題，Euler等人最早研究了該問題的雛形，后來由英國的Hamilton爵士作為一個懸賞問題而提出。但這個能讓普通人在幾分鐘內就可理解的游戲之作，卻延續(xù)至今仍未能完全解決，成了一個世界難題。

TSP有著明顯的實際意義，如，郵局里負責到各信箱開箱取信的郵遞員，以及去各分局送郵件的汽車等，都會遇到類似的問題。有趣的是，還有一些問題表面上看似乎與TSP無關，而實質上卻可以歸結為TSP來求解。已經證明，TSP是個NP難題，除非P=NP，否則不存在有效算法。4TSP在圖論意義下又常常被稱為最小H110

記為賦權圖G=(V,E)，V為頂點集，E為邊集，各頂點間的距離dij已知。設則經典的TSP可寫為如下的數(shù)學規(guī)劃模型：5記為賦權圖G=(V,E)，V為頂點111

模型中，為集合中所含圖的頂點數(shù)。約束（7－1）和（7－2）意味著對每個點而言，僅有一條邊進和一條邊出；約束（7－3）則保證了沒有任何子回路解的產生。于是，滿足約束（7－1）、（7－2）和（7－3）的解構成了一條Hamilton回路。6模型中，為集合中所含圖的頂點數(shù)。112

當dij=dji

(i,j∈V)時，問題被稱為對稱型TSP，否則稱為非對稱型TSP。若對所有1≤i,j,k≤n

，有不等式dij+djk≥dik成立，則問題被稱為是滿足三角形不等式的，簡稱為ΔTSP。7當dij=dji(i,j∈V)時，1132.擴展TSP(1)瓶頸TSP

瓶頸問題是最早從TSP延伸出來的一種擴展型TSP，其含義與經典的TSP類似，僅目標不同，要求巡回路線中經過的最長距離最短，即最小化瓶頸距離。該情形體現(xiàn)了那些并不追求總巡回路線最短，而只希望在巡回路線中每次從一個地點至另一個地點的單次行程盡可能短的實際應用問題的特征。82.擴展TSP114

從嚴格的數(shù)學意義而言，瓶頸TSP（簡稱BTSP）并沒有降低問題的難度，也未能提供任何特殊的解決辦法。瓶頸TSP的數(shù)學模型與標準TSP類似，僅目標函數(shù)不同：

由于目標函數(shù)為瓶頸值，故求得的最佳巡回路線與標準TSP的往往截然不同。9從嚴格的數(shù)學意義而言，瓶頸TSP（115(2)最小比率TSP最小比率TSP（簡稱MRTSP）是從經典TSP引申出來的另一個變形問題，假定從一個城市走到另一個城市可得到某種收益（記為），則MRTSP的目標就是確定最佳行走路線，使得回路的總行程與總收益之比最小。這種優(yōu)化目標的思想類似于人們日常生活中經常使用的費用效益比，與單純的總行程最短相比，往往更具實際意義。10(2)最小比率TSP116

假定收益的數(shù)學性質與相同，則最小比率TSP的數(shù)學模型也與標準TSP類似，僅目標函數(shù)不同：

毫無疑問，由于目標函數(shù)中的非線性因素，最小比率TSP的求解比之標準TSP顯得更為困難。11假定收益的數(shù)學性質與相同，則最小比率117(3)多人TSP

若標準TSP中，出發(fā)點有多個推銷員同時出發(fā)，各自行走不同的路線，使得所有的城市都至少被訪問過一次，然后返回出發(fā)點，要求所有推銷員的總行程最短，則問題就成為一個多人的旅行商問題（簡記MTSP）。令決策變量則MTSP的數(shù)學模型為：12(3)多人TSP則MTSP的數(shù)學模型為：118

假定原問題為對稱型MTSP，V={v0,v1,…vn-1}，v0為名推銷員出發(fā)點，記V‘={v01,v02,…v0m;v0,v1,…vn-1}，擴大的m-1個頂點稱為“人造頂點”，其距離矩陣也相應擴大，其中，位于出發(fā)點的m個頂點相互間的距離設定為∞，其他數(shù)值不變。13假定原問題為對稱型MTSP，V=119二、多面體理論從上世紀70年代開始的關于算法復雜性的研究表明，要想為TSP找到一個好的算法，也即多項式算法，似乎是不可能的。由于推銷員的每條路線可以用一個以1開始的排列來表示，因此所有可能的路線有條。這樣，若用枚舉法來解決這一問題，即使不太大，例如n＝30，用目前最快的計算機，也要化幾百萬年才能求出一條最短的路線。14二、多面體理論120

早在1954年，Dantzig等人就曾提出過一種方法（非多項式算法），并且求出了一個42城市的TSP最優(yōu)解。到了1960年代，不少人用分支定界法解決了許多有幾十個城市的TSP。還有人提出了一些近似方法，也解決了許多有幾十個城市甚至上百個城市的TSP（有時找到的僅是近似解）。更值得注意的是，從1970年代中期開始，Grotschel與Padberg等人深入研究了TS多面體的最大面（facet），并從所得結果出發(fā)獲得了一種解TSP的新算法，可以解決一些有100多個城市的TSP，且都在不長的時間內找到了最優(yōu)解。15早在1954年，Dantzig121

考慮個頂點的完全圖Kn

，則解TSP就相當于在中求一條總長度最短的Hamilton回路?，F(xiàn)在，對每條邊ej，定義一個變量xj與之對應，這樣，TSP的一條路線T，即Kn的一條Hamilton回路，就可對應一個向量X={x1,x2,….xm}，其中，16考慮個頂點的完全圖Kn，則解122

稱X為路線T的關聯(lián)向量，其m=n(n-2)/2個分量中，恰好有個為1，其余的都為0。圖有許多Hamilton回路，設為T1,T2…Ts,，對應的關聯(lián)向量記為X1,X2…Xs

，在m維空間Rm中，考慮這些向量生成的凸包（convexhull）Qn

：17稱X為路線T的關聯(lián)向量，其m=n123

Qn是Rm中的一個凸多面體，稱做TS多面體。顯然，Qn是有界的，其極點正好是Kn的Hamilton回路關聯(lián)向量。研究Qn的面非常重要的，因為根據(jù)線性不等式及凸多面體的理論，Qn一定是某一個有限線性不等式組的解集合，或者說，