第4章物流運(yùn)輸路徑規(guī)劃4.1圖與網(wǎng)絡(luò)的基本概念4.2最短路徑問題4.3運(yùn)輸流量問題4.4單回路運(yùn)輸路線問題4.5多回路運(yùn)輸路線第4章物流運(yùn)輸路徑規(guī)劃本章重點(diǎn)：圖論是運(yùn)籌學(xué)的一個(gè)分支，是建立和處理離散數(shù)學(xué)模型的一個(gè)重要工具。本章中學(xué)生要了解圖論的基本概念，掌握最短路徑問題的狄克斯屈標(biāo)號(hào)法和運(yùn)輸流量問題的福特—富爾克遜標(biāo)號(hào)法，了解單回路運(yùn)輸路線問題和多回路運(yùn)輸路徑。返回4.1圖與網(wǎng)絡(luò)的基本概念圖論（TheoryofGraphs或GraphTheory）是應(yīng)用非常廣泛的運(yùn)籌學(xué)分支，是建立和處理離散數(shù)學(xué)模型的一個(gè)重要工具。圖論的起源最早可追溯到1736年歐拉所發(fā)表的一篇關(guān)于解決著名的“哥尼斯堡七橋問題”的論文。直到20世紀(jì)中葉，隨著離散數(shù)學(xué)和計(jì)算機(jī)技術(shù)的發(fā)展，圖和網(wǎng)絡(luò)的研究更是得到了飛速發(fā)展。目前，網(wǎng)絡(luò)分析的理論已經(jīng)在工程設(shè)計(jì)、管理科學(xué)、交通規(guī)劃、通信網(wǎng)絡(luò)規(guī)劃等眾多領(lǐng)域中得到廣泛應(yīng)用，并取得了豐富的成果。下一頁返回4.1圖與網(wǎng)絡(luò)的基本概念4.1.1圖和圖解1.圖的基本結(jié)構(gòu)首先看一個(gè)圖的實(shí)例。圖4-1是某地7個(gè)村鎮(zhèn)之間的道路交通示意圖，點(diǎn)①、②、③、④、⑤、⑥、⑦分別表示7個(gè)村鎮(zhèn)，各村鎮(zhèn)之間的連線稱為道路。（1）結(jié)點(diǎn)用來表示物理實(shí)體或事物，一般用vi來表示。例如，圖4-1中的結(jié)點(diǎn)就是各村鎮(zhèn)。（2）邊是結(jié)點(diǎn)間的連線，表示兩結(jié)點(diǎn)之間的關(guān)系，一般表示為e=（vi，vj）。下一頁返回上一頁4.1圖與網(wǎng)絡(luò)的基本概念2.無向圖和有向圖若某一圖中所有邊之間都沒有方向，則稱該圖為無向圖。無向圖一般用G=（V，E）表示，其中，V={v1，v2，…，vn}表示點(diǎn)的集合，E={eij

}表示邊的集合。若某一圖中所有邊都有方向，則稱該圖為有向圖。在有向圖中，有方向的邊又稱為弧。有向圖用D=（V，A）表示，A={aij

}表示弧的集合，其中a=（vi，vj）。下一頁返回上一頁4.1圖與網(wǎng)絡(luò)的基本概念3.圖解若用平面上的點(diǎn)表示圖G的結(jié)點(diǎn)，用連接相應(yīng)的結(jié)點(diǎn)而不經(jīng)過其他結(jié)點(diǎn)的線表示圖G的邊，所畫出的圖形稱為圖G的平面圖解，簡(jiǎn)稱圖解。由于對(duì)結(jié)點(diǎn)的位置和邊的形狀的選取具有隨意性，因此一個(gè)圖可以有幾種形狀迥異的圖解。圖4-2（a）和（b）為同一個(gè)無向圖的圖解，圖4-2（c）和（d）為同一個(gè)有向圖的圖解。下一頁返回上一頁4.1圖與網(wǎng)絡(luò)的基本概念4.1.2幾個(gè)基本概念1.端點(diǎn)，關(guān)聯(lián)邊，相鄰。若有e=（vi，vj），則稱vi，vj是e的端點(diǎn)，稱e是vi，vj的關(guān)聯(lián)邊。若點(diǎn)vi與vj跟同一條邊相關(guān)聯(lián)，則稱點(diǎn)vi與vj相鄰，若邊ei與ej有一個(gè)公共端點(diǎn)，則稱邊ei與ej相鄰。2.環(huán)，多重邊，簡(jiǎn)單圖。若一條邊的兩個(gè)端點(diǎn)是同一結(jié)點(diǎn)，則稱該邊為環(huán)；若兩個(gè)端點(diǎn)之間不止一條邊，稱為具有多重邊；無環(huán)也無多重邊的圖稱為簡(jiǎn)單圖。以下討論的圖多指簡(jiǎn)單圖。下一頁返回上一頁4.1圖與網(wǎng)絡(luò)的基本概念3.次，奇點(diǎn)，偶點(diǎn)。點(diǎn)v的關(guān)聯(lián)邊的數(shù)目稱為點(diǎn)v的次。次為奇數(shù)的點(diǎn)稱為奇點(diǎn)，次為偶數(shù)的點(diǎn)稱為偶點(diǎn)。圖4-2（a）中v1的次為3，所以是奇點(diǎn)；圖4-2（c）中v1的次為2，所以是偶點(diǎn)。4.鏈，圈，路。一個(gè)圖中相鄰結(jié)點(diǎn)與相鄰邊的序列{v1，e1，v2，e2，…，en-1，vn}稱為一條從v1到vn的鏈μ。若v1與vn重合，則該鏈為閉鏈，在一個(gè)閉鏈μ中，若任意兩點(diǎn)均不同，且所有的邊也均不相同，則稱μ為一個(gè)圈。若交替序列是有向圖D=（V，A）的一條鏈，則稱μ是圖D的一條從v1到vn的路。下一頁返回上一頁4.1圖與網(wǎng)絡(luò)的基本概念5.連通圖。在一個(gè)圖種，若任意兩點(diǎn)之間至少存在一條鏈，則稱該圖為連通圖，否則稱為不連通圖。圖4-1和圖4-2都是連通圖，而圖4-3不是連通圖。6.網(wǎng)絡(luò)，權(quán)。一個(gè)圖連同定義在其邊集上的實(shí)函數(shù)w（vi，vj）一起稱為一個(gè)網(wǎng)絡(luò)。網(wǎng)絡(luò)一般是連通圖。記wij=w（vi，vj），稱為邊（vi，vj）的權(quán)數(shù)。返回上一頁4.2最短路徑問題4.2.1狄克斯屈標(biāo)號(hào)法該法是Dijkstra在1959年提出的，適用于所有權(quán)數(shù)均為非負(fù)（即一切wij≥0）的網(wǎng)絡(luò)（對(duì)于負(fù)權(quán)網(wǎng)絡(luò)，該法有時(shí)失效），能夠求出網(wǎng)絡(luò)的任一點(diǎn)到其他各點(diǎn)的最短路，使目前求這類網(wǎng)絡(luò)最短路的最好算法。該法直接在網(wǎng)絡(luò)上對(duì)每一個(gè)點(diǎn)標(biāo)號(hào)，標(biāo)號(hào)分為兩種：臨時(shí)標(biāo)號(hào)T（vj）和固定標(biāo)號(hào)P（vj）。在網(wǎng)絡(luò)中，固定標(biāo)號(hào)以帶括號(hào)的數(shù)字表示，臨時(shí)標(biāo)號(hào)不帶括號(hào)。網(wǎng)絡(luò)中一個(gè)點(diǎn)的臨時(shí)標(biāo)號(hào)表示從始點(diǎn)到該點(diǎn)的最短路長(zhǎng)的上界，固定標(biāo)號(hào)表示最短路長(zhǎng)。在標(biāo)號(hào)過程中，臨時(shí)標(biāo)號(hào)不斷被新的更小的臨時(shí)標(biāo)號(hào)所替代，直到不能再減小為止，就得到該點(diǎn)的固定標(biāo)號(hào)。計(jì)算步驟如下：下一頁返回4.2最短路徑問題（1）給始點(diǎn)標(biāo)固定標(biāo)號(hào)（0）；（2）給與（0）點(diǎn)相鄰的各點(diǎn)標(biāo)上臨時(shí)標(biāo)號(hào)，標(biāo)號(hào)數(shù)值為始點(diǎn)固定標(biāo)號(hào)值加上始點(diǎn)到該點(diǎn)間邊的權(quán)數(shù)；（3）從所有的臨時(shí)標(biāo)號(hào)里找最小的確定為固定標(biāo)號(hào)，對(duì)該最小臨時(shí)標(biāo)號(hào)打上括號(hào)；（4）從新得到的固定標(biāo)號(hào)出發(fā)，給相鄰的沒有固定標(biāo)號(hào)的點(diǎn)打上臨時(shí)標(biāo)號(hào)。對(duì)于沒有標(biāo)號(hào)的點(diǎn)，標(biāo)號(hào)數(shù)值為出發(fā)點(diǎn)的固定標(biāo)號(hào)值加上兩點(diǎn)間邊的權(quán)數(shù)；對(duì)于已有臨時(shí)標(biāo)號(hào)的點(diǎn)，新的臨時(shí)標(biāo)號(hào)比原有臨時(shí)標(biāo)號(hào)小的，替換為新的臨時(shí)標(biāo)號(hào)，否則保持原有臨時(shí)標(biāo)號(hào)不變；（5）回到3，重復(fù)上述步驟，直到所有的點(diǎn)都被標(biāo)上固定標(biāo)號(hào)為止。下一頁返回上一頁4.2最短路徑問題例4-1求圖4-1中點(diǎn)1到點(diǎn)7的最短路。解：在圖4-1所示網(wǎng)絡(luò)中，先給出始點(diǎn)①的三條關(guān)聯(lián)邊的終點(diǎn)②、③、④的臨時(shí)標(biāo)號(hào)，分別為T（2）=0+3=3，T（3）=0+4=4，T（4）=0+7=7；從中選出最小標(biāo)號(hào)3，改為固定標(biāo)號(hào)（3），此時(shí)，T（2）=3改為P（2）=（3），實(shí)際上得到了點(diǎn)①到點(diǎn)②的最短路長(zhǎng)為3，如圖4-4（a）所示。從新得到的固定標(biāo)號(hào)點(diǎn)②出發(fā)，檢查與其相鄰并且沒有固定標(biāo)號(hào)的點(diǎn)③、④、⑤，確定臨時(shí)標(biāo)號(hào)如下：下一頁返回上一頁4.2最短路徑問題點(diǎn)③：min{T（3），P（2）+w23}=min{4，3+3}=4，即T（3）=4點(diǎn)④：min{T（4），P（2）+w24}=min{7，3+2}=5，即T（4）=5點(diǎn)⑤：min{T（5），P（2）+w25}=min{∞，3+4}=7，即T（5）=7從所有的臨時(shí)標(biāo)號(hào)中選出點(diǎn)③的最小標(biāo)號(hào)4，改為固定標(biāo)號(hào)（4），此時(shí)，T（3）=4改為P（3）=（4），又得到了點(diǎn)①到點(diǎn)③的最短路長(zhǎng)為4，如圖4-4（b）所示。從新得到的固定標(biāo)號(hào)點(diǎn)③出發(fā)，檢查與其相鄰并且沒有固定標(biāo)號(hào)的點(diǎn)⑤、⑥，確定臨時(shí)標(biāo)號(hào)如下：下一頁返回上一頁4.2最短路徑問題點(diǎn)⑤：min{T（5），P（3）+w35}=min{7，4+5}=7，即T（5）=7點(diǎn)⑥：min{T（6），P（3）+w36}=min{∞，4+7}=11，即T（6）=11從所有的臨時(shí)標(biāo)號(hào)中選出點(diǎn)④的最小標(biāo)號(hào)5，改為固定標(biāo)號(hào)（5），此時(shí)，T（4）=5改為P（4）=（5），又得到了點(diǎn)①到點(diǎn)④的最短路長(zhǎng)為5，如圖4-4（c）所示。從新得到的固定標(biāo)號(hào)點(diǎn)④出發(fā)，檢查與其相鄰并且沒有固定標(biāo)號(hào)的點(diǎn)⑤，⑦，確定臨時(shí)標(biāo)號(hào)如下：下一頁返回上一頁4.2最短路徑問題點(diǎn)⑤：min{T（5），P（4）+w45}=min{7，5+2}=7，即T（5）=7點(diǎn)⑦：min{T（7），P（4）+w47}=min{∞，5+6}=11，即T（7）=11從所有的臨時(shí)標(biāo)號(hào)中選出點(diǎn)⑤的最小標(biāo)號(hào)7，改為固定標(biāo)號(hào)（7），此時(shí)，T（5）=7改為P（5）=（7），我們又得到了點(diǎn)①到點(diǎn)⑤的最短路長(zhǎng)為7，如圖4-4（d）所示。從新得到的固定標(biāo)號(hào)點(diǎn)⑤出發(fā)，檢查與其相鄰并且沒有固定標(biāo)號(hào)的點(diǎn)⑥，⑦，確定臨時(shí)標(biāo)號(hào)如下：下一頁返回上一頁4.2最短路徑問題點(diǎn)⑥：min{T（6），P（5）+w56}=min{11，7+1}=8，即T（6）=8點(diǎn)⑦：min{T（7），P（5）+w57}=min{11，7+4}=11，即T（7）=11從所有的臨時(shí)標(biāo)號(hào)中選出點(diǎn)⑥的最小標(biāo)號(hào)8，改為固定標(biāo)號(hào)（8），此時(shí)，T（6）=11改為P（6）=（8），我們又得到了點(diǎn)①到點(diǎn)⑥的最短路長(zhǎng)為8，如圖4-4（e）所示。從新得到的固定標(biāo)號(hào)點(diǎn)⑥出發(fā)，檢查與其相鄰并且沒有固定標(biāo)號(hào)的點(diǎn)⑦，確定臨時(shí)標(biāo)號(hào)如下：下一頁返回上一頁4.2最短路徑問題點(diǎn)⑦：min{T（7），P（6）+w67}=min{11，8+2}=10，即T（7）=10此時(shí)，只有一個(gè)臨時(shí)標(biāo)號(hào)10，將其改為固定標(biāo)號(hào)，T（7）=11改為P（7）=（10），得到了點(diǎn)①到點(diǎn)⑦的最短路長(zhǎng)為10，如圖4-4（f）所示。至此，所有的點(diǎn)都已得到固定標(biāo)號(hào)，問題求解結(jié)束。由此可以看出，點(diǎn)①到點(diǎn)⑦的最短路有兩條：①→②→④→⑤→⑥→⑦①→②→⑤→⑥→⑦下一頁返回上一頁4.2最短路徑問題4.2.2距離矩陣摹乘法該算法適用于求任何網(wǎng)絡(luò)的最短路，它比狄克斯屈標(biāo)號(hào)法要復(fù)雜些，但應(yīng)用范圍廣，對(duì)于任何含負(fù)權(quán)的網(wǎng)絡(luò)都適用。1.網(wǎng)絡(luò)的距離矩陣設(shè)一個(gè)網(wǎng)絡(luò)N中有n個(gè)結(jié)點(diǎn)，對(duì)于網(wǎng)絡(luò)中相鄰的點(diǎn)，兩點(diǎn)間的距離即為邊的權(quán)數(shù)；不相鄰的兩點(diǎn)，其距離設(shè)為∞。這樣可以定義一個(gè)矩陣W=（wij）n×n稱為網(wǎng)絡(luò)N的直接距離矩陣，簡(jiǎn)稱距離矩陣。如圖4-1所示的網(wǎng)絡(luò)的距離矩陣為：下一頁返回上一頁4.2最短路徑問題2.求各點(diǎn)至某點(diǎn)的最短路（1）建立網(wǎng)絡(luò)的直接距離矩陣，行表示“從”列表示“至”。下一頁返回上一頁4.2最短路徑問題（2）找出到達(dá)的點(diǎn)所在的列，右摹乘距離矩陣，進(jìn)行摹乘運(yùn)算。所謂摹乘運(yùn)算，顧名思義，是模仿矩陣相乘運(yùn)算，在矩陣相乘中，對(duì)應(yīng)元素相乘后求和，得到新矩陣對(duì)應(yīng)元素，而在摹乘運(yùn)算中，是對(duì)應(yīng)元素相加后求最小值，得到新矩陣對(duì)應(yīng)元素。（3）得到的列向量繼續(xù)右摹乘距離矩陣，直到與前一個(gè)摹乘結(jié)果相同則得到最短路長(zhǎng)。（4）在距離矩陣中尋找與列向量相加得到最短路長(zhǎng)的元素，給該元素加標(biāo)記。（5）按每行加標(biāo)記數(shù)字對(duì)應(yīng)的“從/至”關(guān)系，就得到各點(diǎn)到某點(diǎn)的最短路。下一頁返回上一頁4.2最短路徑問題例4-2求圖4-1中各點(diǎn)至點(diǎn)⑦的最短路。解：已知網(wǎng)絡(luò)的直接距離矩陣，求各點(diǎn)到點(diǎn)⑦的最短路，從距離矩陣中找出v7的列向量d1，右摹乘距離矩陣W。中的元素計(jì)算式如下：min{0+∞,3+∞,4+∞,7+6,∞+4,∞+2,∞+0}=13min{3+∞,0+∞,3+∞,2+6,4+4,∞+2,∞+0}=8min{4+∞,3+∞,0+∞,∞+6,5+4,7+2,∞+0}=9min{7+∞,2+∞,∞+∞,0+6,2+4,∞+2,6+0}=6

以下依次類推。下一頁返回上一頁4.2最短路徑問題要注意的是，給元素加標(biāo)記時(shí)，除了v7至v7，對(duì)角線的其他0元素一律不予考慮。按照標(biāo)記數(shù)字對(duì)應(yīng)的從\至關(guān)系，得到各點(diǎn)到v7的最短路：v1→v2

v2→v5

v3→v5

v4→v5

v5→v6

v6→v7

v7→v7下一頁返回上一頁4.2最短路徑問題下一頁返回上一頁4.2最短路徑問題乍看似乎有些點(diǎn)未達(dá)到v7，但根據(jù)最短路的特性，有：下一頁返回上一頁4.2最短路徑問題為了書寫簡(jiǎn)便，上述迭代過程可簡(jiǎn)寫如下：下一頁返回上一頁4.2最短路徑問題3.求某點(diǎn)至各點(diǎn)的最短路（1）建立網(wǎng)絡(luò)的距離矩陣，行表示“從”列表示“至”。（2）找出出發(fā)的點(diǎn)所在的行，左摹乘距離矩陣，進(jìn)行摹乘運(yùn)算。下一頁返回上一頁4.2最短路徑問題（3）得到的行向量繼續(xù)左摹乘距離矩陣，直到與前一個(gè)摹乘結(jié)果相同則得到最短路長(zhǎng)。（4）在距離矩陣中尋找行向量與之相加得到最短路長(zhǎng)的元素，給該元素加標(biāo)記。（5）按每列加圈數(shù)字對(duì)應(yīng)的“從/至”關(guān)系，就得到某點(diǎn)到各點(diǎn)的最短路。例4-3求圖4-5中v1至各點(diǎn)的最短路解：寫出網(wǎng)絡(luò)的直接距離矩陣，從距離矩陣中找出v1的行向量l1，左摹乘距離矩陣W。同樣要注意的是，給元素加標(biāo)記時(shí)，除了v1至v1，對(duì)角線的其他0元素一律不予考慮。網(wǎng)絡(luò)的直接距離矩陣W為：下一頁返回上一頁4.2最短路徑問題具體計(jì)算過程可簡(jiǎn)寫如下：下一頁返回上一頁4.2最短路徑問題按照標(biāo)記數(shù)字對(duì)應(yīng)的從\至關(guān)系，得到v1到各點(diǎn)的最短路：v1→v1，v4→v2，v1→v3，v3→v4，v4→v5，v2→v6進(jìn)而有：下一頁返回上一頁4.2最短路徑問題4．求各點(diǎn)至各點(diǎn)的最短路（1）確定摹乘次數(shù)：根據(jù)公式p>lg（n-1）/lg2，p為整數(shù)，確定p為最后摹乘矩陣下標(biāo)；（2）建立初始網(wǎng)絡(luò)距離矩陣D1；（3）根據(jù)公式，其中1≤s≤n，求D2中的各個(gè)元素。（4）依次類推，直到求出Dp，即為各點(diǎn)至各點(diǎn)的最短距離矩陣。例4-4求圖4-1各村間的最短距離。下一頁返回上一頁4.2最短路徑問題解：先估算摹乘次數(shù)值：p>lg（n-1）/lg2=lg（7-1）/lg2=lg6/lg2=2.6故p=3，應(yīng)計(jì)算到D3。已知網(wǎng)絡(luò)的距離矩陣W，按上面的公式依次計(jì)算如下。其中，D2矩陣中的數(shù)字由D1矩陣中數(shù)字計(jì)算而來，例如，D2矩陣中第二行第五列的數(shù)字為4，是這樣計(jì)算出來的：下一頁返回上一頁4.2最短路徑問題返回上一頁4.3運(yùn)輸流量問題在生產(chǎn)和經(jīng)濟(jì)生活中，許多系統(tǒng)都存在著各種各樣的流。所謂最大流問題，就是在一定條件下，使網(wǎng)絡(luò)系統(tǒng)中的某種流的流量達(dá)到最大的問題。4.3.1基本概念1.網(wǎng)絡(luò)流所謂網(wǎng)絡(luò)流，是指在一定條件下流過一個(gè)網(wǎng)絡(luò)的某種流在各邊上的流量的集合。這里的一定條件，一般指：下一頁返回4.3運(yùn)輸流量問題（1）網(wǎng)絡(luò)有一個(gè)始點(diǎn)vs和一個(gè)終點(diǎn)vt；（2）流過網(wǎng)絡(luò)的流量具有一定的方向，各弧的方向就是流量通過的方向；（3）每一個(gè)弧都有一個(gè)容量，表示允許通過該弧的最大流量。2.可行流滿足以下兩個(gè)條件的流稱為一個(gè)可行流：（1）弧流量限制條件，即每一弧上通過的流量非負(fù)且必須不大于該弧容量；（2）中間點(diǎn)平衡條件，所謂中間點(diǎn)是指除了始點(diǎn)與終點(diǎn)的網(wǎng)絡(luò)中的其他點(diǎn)，這些點(diǎn)的流入量必須等于其流出量，二者必須平衡。下一頁返回上一頁4.3運(yùn)輸流量問題3.最大流在一個(gè)網(wǎng)絡(luò)中，流量最大的可行流稱為最大流。4.鏈的前向弧與后向弧網(wǎng)絡(luò)中一條鏈上與鏈方向一致的弧稱為前向弧，鏈上與鏈方向相反的弧稱為后向弧。5.增廣鏈所謂增廣鏈?zhǔn)侵改晨尚辛魃希刂鴱氖键c(diǎn)到終點(diǎn)的某條鏈調(diào)整各弧上的流量，可以使網(wǎng)絡(luò)的流量增大，得到一個(gè)比原可行流流量更大的可行流。增廣鏈必須滿足的條件如下：下一頁返回上一頁4.3運(yùn)輸流量問題（1）該鏈上前向弧流量小于容量，即流量可以增加；（2）該鏈上后向弧流量大于零，即流量可以減少。若網(wǎng)絡(luò)中存在增廣鏈，則當(dāng)前可行流就不是最大流，調(diào)整方法如下：（1）沿著增廣鏈觀察，計(jì)算所有前向弧的最大可增加量（即每條前向弧容量與當(dāng)前流量的差值），及所有后向弧的最大可減少量（即后項(xiàng)弧上的流量），其中的最小值即為調(diào)整量θ。（2）令當(dāng)前可行流的該增廣鏈上所有前向弧加上調(diào)整量，所有后向弧減去調(diào)整量。下一頁返回上一頁4.3運(yùn)輸流量問題6.截集與截量在一個(gè)網(wǎng)絡(luò)中，把所有結(jié)點(diǎn)的集合V分為兩個(gè)非空集合和，使，，且中各點(diǎn)不需經(jīng)由中的點(diǎn)而均連通，則把始點(diǎn)在中而終點(diǎn)在中的一切弧所構(gòu)成的集合，稱為一個(gè)分離vs和vt的截集，記為（，）。某一個(gè)截集的所有弧的容量之和稱為該截集的容量，簡(jiǎn)稱截量，記為r（，）。例如，圖4-6的所有不同的截集及其截量見表4-1?？梢姡粋€(gè)很簡(jiǎn)單的網(wǎng)絡(luò)也有較多不同的截集。下一頁返回上一頁4.3運(yùn)輸流量問題在一個(gè)網(wǎng)絡(luò)中，截量最小的截集稱為最小截集。由表4-1可知，圖4-6的最小截量為11，最小截集為{（1,3）,（4,t）}。網(wǎng)絡(luò)中從vs到vt的最大流的流量等于分離vs和vt的最小截集的截量。這就是最大流量—最小截量定理。依此原理來求網(wǎng)絡(luò)的最大流。4.3.2求網(wǎng)絡(luò)最大流的標(biāo)號(hào)法這種標(biāo)號(hào)法由福特（Ford）和富爾克遜（Fulkerson）于1956年提出，故稱為福特—富爾克遜標(biāo)號(hào)法。下一頁返回上一頁4.3運(yùn)輸流量問題該法從某一可行流出發(fā)，按照前面介紹的增廣鏈的條件找出一條增廣鏈，并按規(guī)則確定調(diào)整量θ并進(jìn)行調(diào)整，得到一個(gè)流量增大的新的可行流。重復(fù)上述做法，直到找不出增廣鏈為止，這時(shí)就得到一個(gè)最大流，同時(shí)還得到一個(gè)最小截集。1.給始點(diǎn)標(biāo)號(hào)（0,∞），則該點(diǎn)已標(biāo)號(hào)待檢查；2.取一個(gè)已標(biāo)號(hào)待檢查的點(diǎn)vi，對(duì)所有與vi相鄰而未標(biāo)號(hào)的點(diǎn)依次處理如下：（1）前向弧，流量可增時(shí)，標(biāo)號(hào)（vi，b），b取值為通過vi的流量和該弧容量與流量之差的最小值。（2）后向弧，流量大于0時(shí)，標(biāo)號(hào)（-vi，b），b取值為通過vi的流量和該弧流量的最小值。下一頁返回上一頁4.3運(yùn)輸流量問題3.當(dāng)所有與vi相鄰而未標(biāo)號(hào)的點(diǎn)都處理完后，就給vi打√，表示對(duì)它已經(jīng)檢查完畢；4.重復(fù)2，可能出現(xiàn)兩種結(jié)果：（1）終點(diǎn)vt得到標(biāo)號(hào)。則依據(jù)第一個(gè)標(biāo)號(hào)回溯，就能找到一條增廣鏈，轉(zhuǎn)5。（2）所有標(biāo)號(hào)點(diǎn)均已打√，而vt未得到標(biāo)號(hào)，說明不存在增廣鏈，而當(dāng)前的可行流即最大流，算出其流量，終止。5.取終點(diǎn)的第二個(gè)標(biāo)號(hào)為調(diào)整量θ，沿第一個(gè)標(biāo)號(hào)回溯的增廣鏈進(jìn)行調(diào)整：前向弧加上θ；后向弧減去θ。6.刪除所有標(biāo)號(hào)，返回1。下一頁返回上一頁4.3運(yùn)輸流量問題例4-5用標(biāo)號(hào)法求圖4-6所示網(wǎng)絡(luò)的最大流與最小截集。解：（1）先給vs標(biāo)號(hào)（0,∞）。現(xiàn)在已標(biāo)號(hào)待檢查的點(diǎn)只有s點(diǎn)，對(duì)其相鄰點(diǎn)v1和v2分析如下：對(duì)v1，因與vs相關(guān)聯(lián)的?。╲s，v1）上流量為7，容量為9，可增加流量為2，故給v1標(biāo)號(hào)（vs，2）。對(duì)v2，因與vs相關(guān)聯(lián)的?。╲s，v2）上流量為3，容量為5，可增加流量為2，故給v2標(biāo)號(hào)（vs，2）。至此對(duì)vs檢查完畢，給vs打√。下一頁返回上一頁4.3運(yùn)輸流量問題（2）現(xiàn)在已標(biāo)號(hào)待檢查的點(diǎn)有v1、v2。取v1檢查，對(duì)與其相鄰而未標(biāo)號(hào)的點(diǎn)v3、v4分析如下：對(duì)v3，因?。╲1，v3）上容量與流量相等，不能增加流量，故不給v3標(biāo)號(hào)。對(duì)v4，因與v1相關(guān)聯(lián)的?。╲1，v4）上流量為1，容量為3，可增加流量為2，該可增流量與來源點(diǎn)v1的后一標(biāo)號(hào)比較取最小值，已知v1點(diǎn)后標(biāo)號(hào)也為2，故給v4標(biāo)號(hào)（v1,2）。至此對(duì)v1檢查完畢，給v1打√。（3）現(xiàn)在已標(biāo)號(hào)待檢查的點(diǎn)有v2、v4。取v2檢查，因與其相鄰的點(diǎn)都已標(biāo)號(hào)，故給v2打√。下一頁返回上一頁4.3運(yùn)輸流量問題（4）現(xiàn)在已標(biāo)號(hào)待檢查的點(diǎn)僅有v4。對(duì)與其相鄰而未標(biāo)號(hào)的點(diǎn)v3，vt分析如下：對(duì)v3，因弧（v3,v4）流量為1，我們是從v4出發(fā)去v3，（v4,v3）是后向弧，該弧上可減少的流量為1，比較來源點(diǎn)v4的后一標(biāo)號(hào)2，得到最小值1，故給v3標(biāo)號(hào)（-v4,1）。對(duì)vt，因?。╲4，vt）上容量與流量相等，不能增加流量，故不給vt標(biāo)號(hào)。至此對(duì)v4檢查完畢，給v4打√。下一頁返回上一頁4.3運(yùn)輸流量問題（5）現(xiàn)在已標(biāo)號(hào)待檢查的點(diǎn)僅有v3。對(duì)與其相鄰而未標(biāo)號(hào)的點(diǎn)vt分析如下：對(duì)vt，因與v3相關(guān)聯(lián)的?。╲3，vt）上流量為3，容量為6，可增加流量為3，該可增流量與來源點(diǎn)v3的后一標(biāo)號(hào)比較取最小值，已知v3點(diǎn)后標(biāo)號(hào)為1，故給vt標(biāo)號(hào)（v3，1）。至此對(duì)v3檢查完畢，給v4打√。（6）因終點(diǎn)vt已得標(biāo)號(hào)，故從vt依次回溯各點(diǎn)的第一個(gè)標(biāo)號(hào)，就得到一條增廣鏈。如圖4-7粗箭頭線所示。（7）取調(diào)整量θ=1，調(diào)整增廣鏈上各弧的流量，其中，前向弧增加θ，后向弧減少θ，得到一個(gè)新的可行流，如圖4-8所示。下一頁返回上一頁4.3運(yùn)輸流量問題在圖4-8中重復(fù)上述標(biāo)號(hào)步驟,依次給vs，v1，v2，v4標(biāo)號(hào)并檢查后,由于標(biāo)號(hào)過程依法停止，故圖4-8中的可行流就是最大流。最大流的流量可按始點(diǎn)的凈流出量計(jì)算：8+3=11；也可按終點(diǎn)的凈流入量計(jì)算：4+7=11。這時(shí)的標(biāo)號(hào)點(diǎn)集為{vs，v1，v2，v4}，未標(biāo)號(hào)點(diǎn)集為{v3，vt}，故最小截集為{（v1，v3）,（v4，vt）}，最小截量為11，與最大流相等。下面再舉例來說明手工計(jì)算最大流標(biāo)號(hào)法的簡(jiǎn)單表示。下一頁返回上一頁4.3運(yùn)輸流量問題例4-6求圖4-9所示網(wǎng)絡(luò)的最大流與最小截集。圖中每條弧旁邊的數(shù)字為容量，當(dāng)前網(wǎng)絡(luò)流量為零。解：從零流開始，依次選取增廣鏈進(jìn)行調(diào)整，具體調(diào)整步驟如下：下一頁返回上一頁4.3運(yùn)輸流量問題調(diào)整過程如圖4-10所示，弧旁的數(shù)字不斷變化，其中劃去的數(shù)字是各次調(diào)整前的流量。保留的就是最大流在各弧上的最終流量。結(jié)果可知：最大流量20，最小截集為{（vs，v1），（vs，v2）（vs，v3）}。4.3.3最小費(fèi)用最大流在實(shí)際生活中，涉及“流”的問題時(shí)，人們考慮的不只是流量，而且還有“費(fèi)用”的因素，要尋求一個(gè)能使輸送流量的費(fèi)用達(dá)到最小的最大流。這就是最小費(fèi)用最大流問題。下一頁返回上一頁4.3運(yùn)輸流量問題首先來分析一下解決該問題的思路。在求網(wǎng)絡(luò)的最大流時(shí)，從某個(gè)可行流出發(fā)，找到關(guān)于這個(gè)流的一條增廣鏈，如此反復(fù)調(diào)整流量至最大，這個(gè)過程中，增廣鏈的選擇是沒有優(yōu)先順序的。那么在最小費(fèi)用最大流問題中，在尋找增廣鏈以增加流量時(shí)，要找到當(dāng)前網(wǎng)絡(luò)可行流中費(fèi)用最小的增廣鏈，優(yōu)先安排調(diào)運(yùn)，即進(jìn)行流量調(diào)整；調(diào)整后，得到新的可行流，需再尋找費(fèi)用最小的增廣鏈，再次進(jìn)行調(diào)整，如此反復(fù)進(jìn)行，直到找不到費(fèi)用最小的增廣鏈為止。這樣得到的就是費(fèi)用最小的最大流。具體步驟如下：下一頁返回上一頁4.3運(yùn)輸流量問題開始取為初始可行流，一般地，如果在第k-1步得到最小費(fèi)用流，則構(gòu)造賦權(quán)有向圖，在中，尋求從vs到vt的最短路，若不存在最短路，則就是最小費(fèi)用最大流；若存在最短路，則在原網(wǎng)絡(luò)中得到相應(yīng)的增廣鏈，在增廣鏈上對(duì)進(jìn)行調(diào)整，調(diào)整規(guī)則參見最大流標(biāo)號(hào)法。調(diào)整后得到新的可行流，再重復(fù)上述步驟。下面通過例題來具體說明。下一頁返回上一頁4.3運(yùn)輸流量問題例4-7求圖4-11（a）的最小費(fèi)用最大流?；∨詳?shù)字為（bij,cij），其中，bij表示費(fèi)用，cij表示容量，當(dāng)前流量為零。解：（1）取為初始可行流。（2）構(gòu)造賦權(quán)有向圖，并求出從vs到vt的最短路（vs，v2，v1，vt），費(fèi)用為4，如圖4-11（b）所示。（3）在原網(wǎng)絡(luò)中對(duì)與這條最短路相應(yīng)的增廣鏈（vs，v2，

v1，vt）上進(jìn)行調(diào)整，根據(jù)求網(wǎng)絡(luò)最大流的增廣鏈調(diào)整規(guī)則，θ=5，得到新的可行流，如圖4-11（c）所示。下一頁返回上一頁4.3運(yùn)輸流量問題（4）構(gòu)造當(dāng)前可行流的賦權(quán)有向圖。構(gòu)造規(guī)則遵循三個(gè)要點(diǎn)：對(duì)于流量為零的弧，即“空弧”，流向保持不變；對(duì)于流量等于容量的弧，即“滿弧”，流向與初始方向相反；對(duì)于流量非零且不滿的弧，構(gòu)造兩個(gè)方向的弧。在新構(gòu)造的中，求出從vs到vt的最短路（vs，v1，vt），費(fèi)用為5，如圖4-11（d）所示。（5）在原網(wǎng)絡(luò)中對(duì)與這條最短路相應(yīng)的增廣鏈（vs，v1，vt）上進(jìn)行調(diào)整，根據(jù)求網(wǎng)絡(luò)最大流的增廣鏈調(diào)整規(guī)則，θ=2，得到新的可行流，如圖4-11（e）所示。下一頁返回上一頁4.3運(yùn)輸流量問題（6）構(gòu)造當(dāng)前可行流的賦權(quán)有向圖。在新構(gòu)造的中，求出從vs到vt的最短路（vs，v2，v3，vt），費(fèi)用為6，如圖4-11（f）所示。（7）在原網(wǎng)絡(luò)中對(duì)與這條最短路相應(yīng)的增廣鏈（vs，v2，v3，vt）上進(jìn)行調(diào)整，根據(jù)求網(wǎng)絡(luò)最大流的增廣鏈調(diào)整規(guī)則，θ=3，得到新的可行流，如圖4-11（g）所示。（8）構(gòu)造當(dāng)前可行流的賦權(quán)有向圖。在新構(gòu)造的中，求出從vs到vt的最短路（vs，v1，v2，v3，vt），費(fèi)用為7，如圖4-11（h）所示。下一頁返回上一頁4.3運(yùn)輸流量問題（9）在原網(wǎng)絡(luò)中對(duì)與這條最短路相應(yīng)的增廣鏈（vs，v1，v2，v3，vt）上進(jìn)行調(diào)整，根據(jù)求網(wǎng)絡(luò)最大流的增廣鏈調(diào)整規(guī)則，θ=1，得到新的可行流，如圖4-11（i）所示。（10）構(gòu)造當(dāng)前可行流的賦權(quán)有向圖，如圖4-11（j）所示。在新構(gòu)造的中，不存在從vs到vt的最短路，所以為最小費(fèi)用最大流。返回上一頁4.4單回路運(yùn)輸路線問題本節(jié)所要研究的是從某點(diǎn)出發(fā)，經(jīng)過若干個(gè)要到達(dá)的點(diǎn)，或者經(jīng)過若干必須經(jīng)過的路線，最后返回出發(fā)點(diǎn)的一類問題。4.4.1中國(guó)郵遞員問題一個(gè)郵遞員送信，要走完他負(fù)責(zé)投遞的全部街道，完成任務(wù)后回到郵局，應(yīng)該按照怎樣的路線走，所走的路程最短。這個(gè)問題是我國(guó)管梅谷同志在1962年首先提出的，因此在國(guó)際上通稱為中國(guó)郵遞員問題。這個(gè)問題，實(shí)際上就是一類物流配送的最短路問題。下一頁返回4.4單回路運(yùn)輸路線問題若把郵遞員問題抽象為圖的語言，就是給定一個(gè)連通圖，在每條邊上賦予一個(gè)非負(fù)的權(quán)，要求一個(gè)圈（不一定是簡(jiǎn)單的），過每邊至少一次，并使總權(quán)數(shù)最小。1.一筆畫問題在哥尼斯堡城中有一條河叫普雷格爾河，河中有兩個(gè)島，河上有七座橋，如圖4-12（a）所示。當(dāng)?shù)鼐用駸嶂杂谶@樣一個(gè)問題：一個(gè)散布者能否走過七座橋，且每座橋只走過一次，最后回到出發(fā)點(diǎn)。下一頁返回上一頁4.4單回路運(yùn)輸路線問題1736年，歐拉將此問題歸結(jié)為如圖4-12（b）所示圖形的一筆畫問題，即能否從某一點(diǎn)開始一筆畫出這個(gè)圖形，最后回到原點(diǎn)，而不重復(fù)。歐拉證明了這是不可能的，因?yàn)閳D4-12（b）中的每個(gè)點(diǎn)都只與奇數(shù)條線相關(guān)聯(lián)，不可能將這個(gè)圖不重復(fù)地一筆畫成，這是古典圖論中的一個(gè)著名問題。給定一個(gè)連通多重圖G，若存在一條鏈，過每邊一次，且僅一次，則稱這條鏈為歐拉鏈，若存在一個(gè)簡(jiǎn)單圈，過每邊一次，稱這個(gè)圈為歐拉圈。一個(gè)圖若有歐拉圈，則成為歐拉圖。下一頁返回上一頁4.4單回路運(yùn)輸路線問題定理連通多重圖G是歐拉圖，當(dāng)且僅當(dāng)G中無奇點(diǎn)。推論連通多重圖G有歐拉鏈，當(dāng)且僅當(dāng)G恰有兩個(gè)奇點(diǎn)。上述定理和推論為我們提供了一個(gè)識(shí)別一個(gè)圖能否一筆畫出的較為簡(jiǎn)單的辦法。2.奇偶點(diǎn)圖上作業(yè)法如果在某郵遞員所負(fù)責(zé)的范圍內(nèi)，街道圖中沒有奇點(diǎn)，那么他就可以從郵局出發(fā)，走過每條街道一次且僅一次，最后回到郵局，這樣他所走的路程也就是最短的路程。而對(duì)于有奇點(diǎn)的街道，就必須在某些街道上重復(fù)走一次或多次。下一頁返回上一頁4.4單回路運(yùn)輸路線問題如圖4-13所示的街道中，若v1是郵局，郵遞員可以按以下的路線投遞信件：v1→v2→v4→v3→v2→v4→v6→v5→v4→v6→v5→v3→v1總權(quán)為12；也可以按以下的路線投遞信件：v1→v2→v3→v2→v4→v5→v6→v4→v3→v5→v3→v1總權(quán)為11。可見，按第一條路線走，在邊[v2,v4]，[v4,v6]，[v6,v5]上各重復(fù)走了一次，而按第二條路線走，在邊[v3,v2]，[v3,v5]上各重復(fù)走了一次。下一頁返回上一頁4.4單回路運(yùn)輸路線問題如果在某條路線中，邊[vi，vj]上重復(fù)走了幾次，可以在圖中vi，vj之間增加幾條邊，因每邊的權(quán)和原來的權(quán)相等，并把新增加的邊稱為重復(fù)邊。于是這條路線就是相應(yīng)的新圖中的歐拉圈。在圖4-13中，上邊兩條路線分別是圖4-14（a）和（b）中的歐拉圈。顯然，兩條郵遞路線的總路程的差必等于相應(yīng)的重復(fù)邊總權(quán)的差。因而，原來的問題可以敘述為在一個(gè)有奇點(diǎn)的圖中，要求增加一些重復(fù)邊，使新圖不含奇點(diǎn)，并且重復(fù)邊的總權(quán)為最小。把使新圖不含奇點(diǎn)而增加的重復(fù)邊，簡(jiǎn)稱為可行（重復(fù)邊）方案。使總權(quán)最小的可行方案稱為最優(yōu)方案。下一頁返回上一頁4.4單回路運(yùn)輸路線問題現(xiàn)在的問題是第一個(gè)可行方案如何確定，在確定一個(gè)可行方案后，怎么判斷這個(gè)方案是否為最優(yōu)方案？若不是最優(yōu)方案，如何調(diào)整這個(gè)方案?（1）第一個(gè)可行方案的確定方法我們知道，在任何一個(gè)圖中，奇點(diǎn)個(gè)數(shù)必為偶數(shù)。所以如果圖中有奇點(diǎn)，就可以把它們配成對(duì)。又因?yàn)閳D是連通的，故每一對(duì)奇點(diǎn)之間必有一條鏈，我們把這條鏈的所有邊作為重復(fù)邊加到圖中去，則新圖中必?zé)o奇點(diǎn)，這就給出了第一個(gè)可行方案。下一頁返回上一頁4.4單回路運(yùn)輸路線問題例4-8圖4-15中的街道圖，有四個(gè)奇點(diǎn)，v2，v4，v6，v8，把v2與v4分為一對(duì)，v6與v8為一對(duì)。在圖4-15中，連接v2與v4的鏈有好幾條，任取一條（v2，v1，v8，v7，v6，v5，v4），把[v2，v1]，[v1，v8]，[v8，v7]，[v7，v6]，[v6，v5]，[v5，v4]作為重復(fù)邊加到圖中去，同樣地取連接v6與v8的鏈（v6，v5，v4，v3，v2，v1，v8），把[v6，v5]，[v5，v4]，[v4，v3]，[v3，v2]，[v2，v1]，[v1，v8]作為重復(fù)邊加到圖中去，得到圖4-16。這個(gè)圖沒有奇點(diǎn)，是歐拉圖。這是個(gè)可行方案，重復(fù)邊的總權(quán)數(shù)可計(jì)算出為51。下一頁返回上一頁4.4單回路運(yùn)輸路線問題（2）調(diào)整可行方案，使重復(fù)邊總長(zhǎng)度下降從圖4-16中可以看出，有一些邊上有兩條重復(fù)邊，比如[v1，v8]，如果把它們都從圖中去掉，圖仍然無奇點(diǎn)，還是可行方案，但邊的總長(zhǎng)度卻有所下降。一般情況下，如果邊上有兩條或兩條以上的重復(fù)邊時(shí)，我們從中去掉偶數(shù)條，就能得到一個(gè)總長(zhǎng)度較小的可行方案。為了得到總長(zhǎng)度最小的最優(yōu)方案，我們需遵守以下兩條原則：①在最優(yōu)方案中，圖的每一邊上最多有一條重復(fù)邊。②在最優(yōu)方案中，圖中每個(gè)圈上的重復(fù)邊的總權(quán)不大于該圈總權(quán)的一半。下一頁返回上一頁4.4單回路運(yùn)輸路線問題按照上面的原則，圖4-16可以調(diào)整為圖4-17，重復(fù)邊總權(quán)下降到21。進(jìn)一步地，如果把圖中某個(gè)圈上的重復(fù)邊去掉，而給原來沒有重復(fù)邊的邊上加上重復(fù)邊，圖中仍然沒有奇點(diǎn)。如果新的重復(fù)邊總權(quán)數(shù)比原先的重復(fù)邊總權(quán)數(shù)小，將會(huì)得到一個(gè)總權(quán)下降的可行方案。事實(shí)上，較小權(quán)數(shù)的重復(fù)邊，其總權(quán)數(shù)應(yīng)當(dāng)小于其所在圈的總權(quán)的一半。經(jīng)過調(diào)整，得到圖4-18，重復(fù)邊總長(zhǎng)度下降為17。下一頁返回上一頁4.4單回路運(yùn)輸路線問題（3）判斷最優(yōu)方案的標(biāo)準(zhǔn)從上面的分析可知，一個(gè)最優(yōu)方案一定是滿足上述（1）和（2）兩個(gè)條件的可行方案?？梢宰C明，一個(gè)可行方案若滿足（1）和（2），這個(gè)可行方案一定是最優(yōu)方案。根據(jù)這樣一個(gè)判別標(biāo)準(zhǔn)，對(duì)給定的可行方案，檢查它是否滿足上述兩個(gè)條件。若滿足，所得方案即為最優(yōu)方案；若不滿足，則對(duì)方案進(jìn)行調(diào)整，直至滿足上述兩個(gè)條件為止。下一頁返回上一頁4.4單回路運(yùn)輸路線問題檢查圖4-18中的圈（v1，v2，v9，v6，v7，v8，v1）中重復(fù)邊總權(quán)數(shù)為13，而圈的權(quán)為24，不滿足條件（2），經(jīng)調(diào)整得4-19。重復(fù)邊總長(zhǎng)度下降為15。再檢查，條件（1）和（2）都滿足，于是得到了最優(yōu)方案。圖4-20中的任意一個(gè)歐拉圈就是郵遞員的最優(yōu)郵遞路線。以上求最優(yōu)郵遞路線的方法，通常稱為奇偶點(diǎn)圖上作業(yè)法。該方法的主要困難在于檢查條件（2），當(dāng)圖中點(diǎn)、邊數(shù)較多時(shí)，圈的個(gè)數(shù)將會(huì)很多，比如“日”字形的圖有3個(gè)圈，而“田”字形的圖就有13個(gè)圈。下一頁返回上一頁4.4單回路運(yùn)輸路線問題4.4.2旅行商問題旅行商問題大意是說：一個(gè)旅行商從某一個(gè)村莊出發(fā)，到周圍若干個(gè)村莊進(jìn)行銷售，每個(gè)村莊都要走到，而且只去一次，最后返回出發(fā)點(diǎn)，試問應(yīng)按什么順序走遍所有村莊，同時(shí)使所走路程最短。這個(gè)問題屬于組合最優(yōu)化問題，當(dāng)村莊數(shù)量不太大時(shí)，利用動(dòng)態(tài)規(guī)劃方法求解是很方便的。下面通過一個(gè)具體的例子來說明如何應(yīng)用動(dòng)態(tài)規(guī)劃方法求解簡(jiǎn)單的旅行商問題。下一頁返回上一頁4.4單回路運(yùn)輸路線問題例4-9求解四個(gè)城市旅行推銷員問題，其距離矩陣如表4-2所示，當(dāng)推銷員從1城市出發(fā)，經(jīng)過每個(gè)城市一次且僅一次，最后回到1城市，問按怎樣的路線走，能使總的行程距離最短。解：按順序解法的思路：第一階段：從1城市開始，中間經(jīng)過一個(gè)城市到達(dá)某城市i的最短距離分別是：當(dāng)i=2時(shí)，經(jīng)過3城的最短距離是d132=d13+d32=5+9=14當(dāng)i=2時(shí)，經(jīng)過4城的最短距離是d142=d14+d42=6+7=13下一頁返回上一頁4.4單回路運(yùn)輸路線問題當(dāng)i=3時(shí)，經(jīng)過2城的最短距離是d123=d12+d23=8+8=16當(dāng)i=3時(shí)，經(jīng)過4城的最短距離是d143=d14+d43=6+8=14當(dāng)i=4時(shí)，經(jīng)過2城的最短距離是d124=d12+d24=8+5=13當(dāng)i=4時(shí)，經(jīng)過3城的最短距離是d134=d13+d34=5+5=10第二階段：從1城市開始，中間經(jīng)過兩個(gè)城市（順序隨便）到達(dá)某城市i的最短距離分別是：下一頁返回上一頁4.4單回路運(yùn)輸路線問題當(dāng)i=2時(shí)，經(jīng)過3、4城的最短距離是d1[34]2=min[d134+d42

，d143+d32]=[10+7，14+9]=17路線為1-3-4-2。當(dāng)i=3時(shí)，經(jīng)過2、4城的最短距離是d1[24]3=min[d124+d43，d142+d23]=[13+8，13+8]=21路線為1-2-4-3。下一頁返回上一頁4.4單回路運(yùn)輸路線問題當(dāng)i=4時(shí)，經(jīng)過2、3城的最短距離是d1[23]4=min[d123+d34，d132+d24]=[16+10，14+5]=19路線為1-3-2-4。第三階段：從1城市開始，中間經(jīng)過三個(gè)城市（順序隨便）回到1城市的最短距離為：d1[234]1=min[d1342+d21，d1243+d31，d1324+d41]=[17+6，21+7，19+9]=23由此可知，推銷員的最短旅行路線是1-3-4-2-1，最短總距離為23。返回上一頁4.5多回路運(yùn)輸路線隨著社會(huì)經(jīng)濟(jì)的不斷發(fā)展，作為“第三利潤(rùn)源”的物流越來越引起人們的關(guān)注，其中物流配送車輛優(yōu)化調(diào)度問題是物流中關(guān)鍵的一環(huán)，對(duì)其進(jìn)行優(yōu)化調(diào)度，可以提高物流經(jīng)濟(jì)效益、實(shí)現(xiàn)物流科學(xué)化。物流配送車輛優(yōu)化調(diào)度問題最早是由Dantzig和Ramser于1959年首次提出的，稱之為VehicleRoutingProblem（簡(jiǎn)稱VRP）。該問題一般定義為：對(duì)一系列給定的顧客（取貨點(diǎn)或送貨點(diǎn)），確定適當(dāng)?shù)呐渌蛙囕v行駛路線，使其從配送中心出發(fā)，有序地通過它們，最后返回配送中心，并在滿足一定的約束條件下（如車輛容量限制、顧客需求量、交發(fā)貨時(shí)間等），達(dá)到一定的目標(biāo)（如路程最短、費(fèi)用最少等）。下一頁返回4.5多回路運(yùn)輸路線車輛路徑問題（VRP問題）是組合優(yōu)化領(lǐng)域中著名的NP難題。近二十年來，無論在國(guó)內(nèi)外，VRP問題都是一個(gè)非?；钴S的研究領(lǐng)域。目前解決該問題的現(xiàn)代數(shù)學(xué)方法主要分為以下幾類：1.精確優(yōu)化方法包括分枝定界算法、Ｋ度中心樹及相關(guān)算法、動(dòng)態(tài)規(guī)劃、集合劃分和列產(chǎn)生、三索引車輛流方式、二索引車輛流方式等。但精確算法的計(jì)算復(fù)雜度很高，隨著運(yùn)輸系統(tǒng)的復(fù)雜化和對(duì)調(diào)度的多目標(biāo)要求，獲得整個(gè)系統(tǒng)的精確優(yōu)化解越來越困難，花費(fèi)的時(shí)間和費(fèi)用太大，因此精確解法不能應(yīng)用于規(guī)模較大的物流配送車路由問題的求解，僅用于運(yùn)輸調(diào)度的局部?jī)?yōu)化問題。下一頁返回上一頁4.5多回路運(yùn)輸路線2.啟發(fā)式方法（Heuristics）指通過經(jīng)驗(yàn)法則來求取運(yùn)輸過程滿意解的數(shù)學(xué)方法。啟發(fā)式方法能同時(shí)滿足詳細(xì)描繪問題和求解的需要，較精確優(yōu)化方法更為簡(jiǎn)單實(shí)用，缺點(diǎn)是難于知道什么時(shí)候好的啟發(fā)式解己經(jīng)被求得。啟發(fā)式方法中最具代表性的就是由Clarck和Wright提出的節(jié)約法（SavingMethod）。許多成功的車輛調(diào)度軟件就是根據(jù)該方法或其改進(jìn)方法開發(fā)的。下一頁返回上一頁4.5多回路運(yùn)輸路線典型啟發(fā)式算法中還包括由Lin和Kemighan提出的，并由Chtistofidests和GilbertlaPorte等人所推廣的分支交換探索法，該算法始終保持解的可行性而又力圖向最優(yōu)目標(biāo)前進(jìn)。在每一步，都改變一個(gè)可行解而減少總費(fèi)用，直到這個(gè)過程繼續(xù)到不再可能使費(fèi)用減少為止。Gillet和Milled提出的掃描法（SweepMethod）先把節(jié)點(diǎn)或弧的需求進(jìn)行分組或劃群，然后對(duì)每一組按旅行商問題（TSP）求解，設(shè)計(jì)出一條經(jīng)濟(jì)的路線。此外，常用的啟發(fā)式方法還有2-階段法、不完全樹搜索算法等。各種啟發(fā)式方法的主要區(qū)別在于收斂的速度和程度不同。下一頁返回上一頁4.5多回路運(yùn)輸路線精確優(yōu)化方法是以往廣泛采用的方法，另外三種方法則代表了最近研究的方向。尤其是啟發(fā)式方法，作為一種逐次逼近的算法，雖然不一定得到最優(yōu)解，但是可以高效率地得到具有較高精度的解，而且也易于考慮各種實(shí)際問題，因此，現(xiàn)己成為解決配送問題的重要方法。啟發(fā)式算法中最具有代表性的就是由克拉克（Clarke）和懷特（Wright）提出的節(jié)約法（SavingMethod）。下面說明節(jié)約法思考的基本方法。下一頁返回上一頁4.5多回路運(yùn)輸路線設(shè)有一個(gè)配送中心,兩個(gè)配送點(diǎn)和,若配送中心向配送點(diǎn)分別單獨(dú)送貨，則運(yùn)輸路線為,

運(yùn)輸距離為，若采取回路送貨，運(yùn)輸路線為，運(yùn)輸距離為。如圖4-19所示。路線改動(dòng)后運(yùn)輸路線的節(jié)約量是：這就是有名的節(jié)約量公式。

下一頁返回上一頁4.5多回路運(yùn)輸路線4.5.1單配送中心配送規(guī)劃1.配送路線與車輛調(diào)度前提條件實(shí)際的配送路線優(yōu)化問題，存在各種約束條件，非常復(fù)雜。為了簡(jiǎn)化問題，我們首先提出一些假設(shè)條件。（1）被配送的是已知的一種或者幾種物資；（2）各個(gè)用戶的所在地和需求量已知；（3）從配送中心到各個(gè)用戶之間的運(yùn)輸距離已知；（4）各種類型的車輛數(shù)目一定，能滿足運(yùn)輸要求；（5）每一輛發(fā)送車輛的裝載量有一定的限制，不能超載運(yùn)行。下一頁返回上一頁4.5多回路運(yùn)輸路線2.配送路線優(yōu)化節(jié)約法一般地，配送中心向用戶配送物資，使用的車輛的裝載量不可能完全相同（主要是由于車型不同），假設(shè)向每個(gè)用戶都派一輛車，各個(gè)用戶的需要量都小于最大發(fā)送車的裝載量，同時(shí)裝載量最小的車子臺(tái)數(shù)足以安排貨運(yùn)。下面通過一個(gè)實(shí)際例子來說明節(jié)約法的求解思路。下一頁返回上一頁4.5多回路運(yùn)輸路線例4-10已知配送中心P0向7個(gè)用戶Pj配送貨物，其配送路線網(wǎng)絡(luò)、配送中心與用戶的距離、用戶之間的距離如圖4-20所示，圖中括號(hào)內(nèi)的數(shù)字表示客戶的需求量Qi（單位：t），線路上的數(shù)字表示兩結(jié)點(diǎn)之間的距離（單位：km），現(xiàn)配送中心有8臺(tái)4t卡車和3臺(tái)6t兩種車輛可供使用。試?yán)霉?jié)約里程法制定最優(yōu)的配送方案？解：首先做出配送中心與各用戶間的運(yùn)輸里程表4-3。根據(jù)節(jié)約量公式，求出用戶連接的費(fèi)用節(jié)約值，見表4-4。初始方案為：配送中心向每個(gè)用戶單獨(dú)送貨，需要7臺(tái)4t的車，總里程為：下一頁返回上一頁4.5多回路運(yùn)輸路線車輛分配方案為：4t車輛使用7臺(tái)，6t車輛使用0臺(tái)。在初始解的基礎(chǔ)上，選出具有最大節(jié)約值的格子，該格子應(yīng)滿足下列條件：（1）用戶Pi和用戶Pj不在同一條線路上；（2）原計(jì)劃分別運(yùn)送用戶Pi和用戶Pj的貨物可用裝載量大于的車進(jìn)行運(yùn)送。表4-4中最大節(jié)約量為，把用戶P6和用戶P7進(jìn)行連接，進(jìn)行第一次路線修改。第一次修改后得到表4-5的配送方案。其中，將用戶P6和用戶P7的需要量分別改為的總載運(yùn)量。下一頁返回上一頁4.5多回路運(yùn)輸路線注：表4-5中，1表示連接這兩個(gè)用戶，0表示不連接，2表示由配送中心單獨(dú)送貨。車輛分配方案為：4t車輛使用6臺(tái)，6t車輛使用0臺(tái)。由節(jié)約量公式可知，總里程減少了23，此時(shí)總里程為

,進(jìn)一步優(yōu)化,選取次大節(jié)約值，把用戶P3和用戶P4進(jìn)行連接，進(jìn)行第二次路線修改。修改后得到表4-6的配送方案。其中，將用戶P3和用戶P4的需要量分別改為的總載運(yùn)量。下一頁返回上一頁4.5多回路運(yùn)輸路線車輛分配方案為：4t車輛使用5臺(tái)，6t車輛使用0臺(tái)。由節(jié)約量公式可知，總里程又減少了16，此時(shí)總里程為，再進(jìn)一步優(yōu)化，比16小的節(jié)約值和，任選一個(gè)進(jìn)行優(yōu)化，把用戶P2和用戶P3進(jìn)行連接，進(jìn)行第三次路線修改。我們將用戶P2、用戶P3和用戶P4的需要量分別改為的總載運(yùn)量。因?yàn)橛脩鬚3兩端分別和用戶P4、用戶P2相連，不可能再與其它點(diǎn)相連，故表4-4中P3行整行節(jié)約值刪除，不再考慮。修改后得到表4-7的配送方案。下一頁返回上一頁4.5多回路運(yùn)輸路線車輛分配方案為：4t車輛使用4臺(tái)，6t車輛使用0臺(tái)。由節(jié)約量公式可知，總里程又減少了11，此時(shí)總里程為，下一步選進(jìn)行優(yōu)化，把用戶P5和用戶P6進(jìn)行連接，進(jìn)行第四次路線修改。將用戶P5、用戶P6和用戶P7的需要量分別改為的總載運(yùn)量。因?yàn)橛脩鬚6兩端分別和用戶P7、用戶P5相連，不可能再與其它點(diǎn)相連，故表4-4中P6行整行節(jié)約值刪除，不再考慮。修改后得到表4-8的配送方案。下一頁返回上一頁4.5多回路運(yùn)輸路線車輛分配方案為：4t車輛使用2臺(tái)，6t車輛使用1臺(tái)。由節(jié)約量公式可知，總里程又減少了11，此時(shí)總里程為，下面看到比11小的節(jié)約值10和8因?yàn)樘幱赑3和P6行，因此不予考慮和，若選進(jìn)行優(yōu)化，則現(xiàn)有車輛噸位不夠。因此用戶P4和用戶P5所在線路不能相連。選進(jìn)行優(yōu)化，把用戶P1和用戶P2、P3、P4進(jìn)行連接，進(jìn)行第五次路線修改。我們將用戶P1、P2、P3、P4的需要量分別改為的總載運(yùn)量。因?yàn)橛脩鬚2兩端分別和用戶P1、用戶P3相連，不可能再與其它點(diǎn)相連，故表4-4中P2行整行節(jié)約值刪除，不再考慮。修改后得到表4-9的配送方案。下一頁返回上一頁4.5多回路運(yùn)輸路線車輛分配方案為：4t車輛使用0臺(tái)，6t車輛使用2臺(tái)。由節(jié)約量公式可知，總里程又減少了7，此時(shí)總里程為。現(xiàn)在，有兩條線路進(jìn)行配送，就現(xiàn)有的車輛噸位狀況，每條線路上載運(yùn)量都不可能再增加，因此，第五次修改后的方案就是最優(yōu)調(diào)運(yùn)方案。3.節(jié)約法的改進(jìn)前面已經(jīng)講到，啟發(fā)式算法并不能保證得到問題的最優(yōu)解。節(jié)約法求解配送路線優(yōu)化問題，有時(shí)就會(huì)出現(xiàn)僅得滿意解的情況，這時(shí)就需要結(jié)合其他的方法來求最優(yōu)解。下一頁返回上一頁4.5多回路運(yùn)輸路線例4-11同樣是一個(gè)配送中心，7個(gè)用戶的問題，改變一下上例的部分參數(shù)。表4-10給出了配送中心與用戶的距離、用戶之間的距離以及客戶的需求量Qi（單位：t）解：根據(jù)節(jié)約量公式，求出用戶連接的費(fèi)用節(jié)約值，見表4-11。配送路線優(yōu)化的過程簡(jiǎn)寫如下：初始方案：對(duì)每個(gè)用戶單獨(dú)送貨，需7臺(tái)4t的車，總里程為：下一頁返回上一頁4.5多回路運(yùn)輸路線改進(jìn)1：最大節(jié)約量Smax=S34=16,Q34=Q3+Q4=2.9t，需要6臺(tái)4t的車，總里程S1=124-16=108km。改進(jìn)2：Smax=S67=11，Q67=Q6+Q7=3.9t，需要5臺(tái)4t的車，總里程S2=108-11=97km。改進(jìn)3：Smax=S17=11,Q167=Q1+Q67=7.1t，不可行。Smax=S45=9，Q345=Q5+Q34=5.3t，需要3臺(tái)4t的車，1臺(tái)6t車，總里程S3=97-9=88km。下一頁返回上一頁4.5多回路運(yùn)輸路線改進(jìn)4：Smax=S23=9，Q2345=Q2+Q345=6.9t，不可行。同理，Smax=S56=8，Smax=S13=8均不可行。Smax=S12=7，Q12=Q1+Q2=4.8t，需要1臺(tái)4t的車，2臺(tái)6t車，總里程S3=88-7=81km。最優(yōu)方案為：1、2商店共同送貨，貨物量4.8t，6t車；3、4、5商店共同送貨，貨物量5.3t，6t車；6、7商店共同送貨，貨物量3.9t，4t車?？偫锍?1km。如果在遇到相同節(jié)約值的時(shí)候做出不同的選擇，會(huì)有如下另一種方案。下一頁返回上一頁4.5多回路運(yùn)輸路線初始方案：對(duì)每個(gè)用戶單獨(dú)送貨,需7臺(tái)4t的車,總里程為：改進(jìn)1：最大節(jié)約量Smax=S34=16,Q34=Q3+Q4=2.9t。需要6臺(tái)4t的車，總里程S1=124-16=108km。改進(jìn)2：Smax=S17=11，Q17=Q1+Q7=4.9t。需要4臺(tái)4t的車，1臺(tái)6t的車，總里程S2=108-11=97km。改進(jìn)3：Smax=S67=11，Q176=Q17+Q6=7.1t，不可行。Smax=S23=9，Q234=Q2+Q34=4.5t。需要2臺(tái)4t的車，2臺(tái)6t車，總里程S3=97-9=88km。下一頁返回上一頁4.5多回路運(yùn)輸路線改進(jìn)4：Smax=S45=9，Q2345=Q234+Q5=6.9t，不可行。Smax=S56=8，Q56=Q5+Q6=4.6t。Smax=S12=7，Q12=Q1+Q2=4.8t，需要3臺(tái)6t車，總里程S4=88-8=80km。最優(yōu)方案為：1、7商店共同送貨，貨物量4.9t，6t車；2、3、4商店共同送貨，貨物量4.5t，6t車；5、6商店共同送貨，貨物量4.8t。總里程80km。進(jìn)一步地，如果用分支的形式將各種路線組合優(yōu)化的方案對(duì)比，可以得到如下分支圖，如圖4-21所示。通過分支法，對(duì)此類問題的求解過程進(jìn)行改進(jìn)，可以更精確地得到最優(yōu)解、次優(yōu)解，以便做出更好的選擇。下一頁返回上一頁4.5多回路運(yùn)輸路線4.5.2多配送中心配送規(guī)劃現(xiàn)實(shí)生活中，為提高經(jīng)濟(jì)效益，有時(shí)候需要使用多個(gè)配送中心來進(jìn)行配送，即利用多個(gè)配送中心為用戶服務(wù)。此類問題可以看作是由幾個(gè)封閉循環(huán)線路的旅行商問題，是組合優(yōu)化問題的一種，調(diào)度的目標(biāo)是尋求在完成用戶的貨運(yùn)任務(wù)前提下，使用最少的車輛數(shù)并且安排各車的行駛路線。對(duì)此類問題有兩類基本的算法。下一頁返回上一頁4.5多回路運(yùn)輸路線一類先對(duì)用戶分組后安排路線，即把用戶按一定調(diào)度規(guī)則劃分為不同的組，每一組對(duì)應(yīng)一個(gè)配送中心，然后對(duì)每一個(gè)配送中心求解。如果任何一個(gè)配送中心的車輛不足以安排任務(wù)，就修正原來的分組，并對(duì)新的單配送中心問題進(jìn)行求解。這一過程按照分組規(guī)則一直進(jìn)行下去，直到得到滿意的解為止。對(duì)用戶進(jìn)行劃分的規(guī)則可以是“就地就近發(fā)送”等實(shí)際經(jīng)驗(yàn)調(diào)度（目前一般采用這種方式），也可以是一些對(duì)局優(yōu)化有貢獻(xiàn)的啟發(fā)式規(guī)則。下一頁返回上一頁4.5多回路運(yùn)輸路線另一類則先安排線路后分組，即先對(duì)所有用戶求解線路安排，而不管配送中心在哪，這樣就構(gòu)建了一條大的路線（通常不可行），它包含了所有的用戶。然后，對(duì)每一輛車的路線，指定一個(gè)配送中心。其目的是在滿足配貨中心的車輛限制下使得總的運(yùn)輸距離最小。當(dāng)車輛進(jìn)出配送中心的距離遠(yuǎn)小于它消耗在運(yùn)輸貨物的行駛距離時(shí)，這種方法就比較合理，求解的滿意度也很高。下一頁返回上一頁4.5多回路運(yùn)輸路線現(xiàn)在采用先分組后安排路線的方法，對(duì)此類問題的求解進(jìn)行討論。設(shè)di（t）表示用戶i和配送中心t之間的距離，記為集合Di={di（t），t=1，…，p}，p是配送中心的個(gè)數(shù)。計(jì)算r（i）=minDi/subminDi，minDi和subminDi分別表示集合Di中的最小值和次小值，取適當(dāng)?shù)摩模容^r（i）和δ的大小，當(dāng)r（i）＜δ，把用戶i分配給minDi對(duì)應(yīng)的配送中心，如果r（i）≥δ，這時(shí)用戶i為邊界點(diǎn)，對(duì)邊界點(diǎn)的分配如下：下一頁返回上一頁4.5多回路運(yùn)輸路線當(dāng)r（i）≠1時(shí)，利用節(jié)約法進(jìn)行分派。首先考慮由最近的配送中心發(fā)出配送車服務(wù)每一個(gè)點(diǎn)，構(gòu)成初始解。各點(diǎn)對(duì)最近配送中心的分派都是暫時(shí)的，一旦兩個(gè)或者多個(gè)點(diǎn)已被分派給一個(gè)配送中心發(fā)出的線路，這些點(diǎn)就不再分派給其他的配送中心。當(dāng)點(diǎn)i和j都不與配送中心相連時(shí)，進(jìn)行連接，連接的節(jié)約量按上述節(jié)約量公式計(jì)算。根據(jù)節(jié)約值，連接用戶i和j。在這種情況下，點(diǎn)i被分配離它最近的配送中心。下一頁返回上一頁4.5多回路運(yùn)輸路線第二種情況，當(dāng)r（i）=1時(shí)，如果點(diǎn)j和點(diǎn)k已分派給某配送中心t，插入點(diǎn)i，對(duì)配送中心t而言產(chǎn)生的附加費(fèi)用是dijk（t）=dik+dji-djk，并且將用戶i分派給使得dijk（t）最小的配送中心。通過改變?chǔ)牡拇笮。梢钥刂七吔琰c(diǎn)的個(gè)數(shù)。當(dāng)δ=0時(shí)，所有的用戶都是邊界點(diǎn)，當(dāng)δ=1時(shí)，所有的用戶均分派給最近的配送中心。對(duì)用戶的分組完畢后，就可以分別對(duì)每組的用戶進(jìn)行單配送中心的車輛調(diào)度安排，得到各組的路線安排。下一頁返回上一頁4.5多回路運(yùn)輸路線例4-11現(xiàn)有三個(gè)配送中心（標(biāo)號(hào)1，2，3）給10個(gè)用戶（標(biāo)號(hào)4，5，…，13）進(jìn)行配送。配送中心與用戶之間，以及用戶之間的距離如表4-12所示。對(duì)各用戶進(jìn)行分組，以便求單配送中心的車輛路線安排。解：計(jì)算r（i），得表4-13。取δ=0.7，所有r（i）＜δ的用戶被分配給最近的中心，如表4-14所示。對(duì)r（i）≥δ且r（i）≠1的點(diǎn)8，10和12，兩兩相連，計(jì)算節(jié)約量sij（t）（i，j=8，10，12；t=1，2，3），并且按照從大到小的順序排列，得表4-15。下一頁返回上一頁4.5多回路運(yùn)輸路線根據(jù)表4-15，把用戶8和用戶10分配給配送中心1，得到永久分配。把用戶12分配給最近的配送中心3。對(duì)于r（i）=1的用戶13，分配給不同的配送中心時(shí)，需插入到已分配給該配送中心的各用戶點(diǎn)之間，根據(jù)插入點(diǎn)產(chǎn)生附加費(fèi)用的公式dijk（t）=dik+dji-djk，計(jì)算節(jié)約值：對(duì)配送中心1，其現(xiàn)已安排的用戶為4，5，8，10。d13,4,5=101+43-44=100d13,4,8=101+121-63=159d13,4,10=101+55-65=91下一頁返回上一頁4.5多回路運(yùn)輸路線d13,5,8=101+43-44=100d13,5,10=43+55-69=29d13,8,10=121+55-35=141對(duì)配送中心2，其現(xiàn)已安排的用戶為11。d13,11=37+48-32=53對(duì)配送中心3，其現(xiàn)已安排的用戶為6，7，9，12。d13,6,7=89+98-75=112d13,6,9=89+73-40=122d13,6,12=89+64-67=86下一頁返回上一頁4.5多回路運(yùn)輸路線d13,7,9=98+73-53=118d13,7,12=98+64-46=116d13,9,12=73+64-28=109從上述節(jié)約值中取最小值29，故把