《物流運籌學(xué)》第4章-物流運輸路徑規(guī)劃

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

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

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

v2→v5

v3→v5

v4→v5

v5→v6

v6→v7

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

v1，vt）上進行調(diào)整，根據(jù)求網(wǎng)絡(luò)最大流的增廣鏈調(diào)整規(guī)則，θ=5，得到新的可行流，如圖4-11（c）所示。下一頁返回上一頁4.3運輸流量問題（4）構(gòu)造當(dāng)前可行流的賦權(quán)有向圖。構(gòu)造規(guī)則遵循三個要點：對于流量為零的弧，即“空弧”，流向保持不變；對于流量等于容量的弧，即“滿弧”，流向與初始方向相反；對于流量非零且不滿的弧，構(gòu)造兩個方向的弧。在新構(gòu)造的中，求出從vs到vt的最短路（vs，v1，vt），費用為5，如圖4-11（d）所示。（5）在原網(wǎng)絡(luò)中對與這條最短路相應(yīng)的增廣鏈（vs，v1，vt）上進行調(diào)整，根據(jù)求網(wǎng)絡(luò)最大流的增廣鏈調(diào)整規(guī)則，θ=2，得到新的可行流，如圖4-11（e）所示。下一頁返回上一頁4.3運輸流量問題（6）構(gòu)造當(dāng)前可行流的賦權(quán)有向圖。在新構(gòu)造的中，求出從vs到vt的最短路（vs，v2，v3，vt），費用為6，如圖4-11（f）所示。（7）在原網(wǎng)絡(luò)中對與這條最短路相應(yīng)的增廣鏈（vs，v2，v3，vt）上進行調(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），費用為7，如圖4-11（h）所示。下一頁返回上一頁4.3運輸流量問題（9）在原網(wǎng)絡(luò)中對與這條最短路相應(yīng)的增廣鏈（vs，v1，v2，v3，vt）上進行調(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的最短路，所以為最小費用最大流。返回上一頁4.4單回路運輸路線問題本節(jié)所要研究的是從某點出發(fā)，經(jīng)過若干個要到達的點，或者經(jīng)過若干必須經(jīng)過的路線，最后返回出發(fā)點的一類問題。4.4.1中國郵遞員問題一個郵遞員送信，要走完他負(fù)責(zé)投遞的全部街道，完成任務(wù)后回到郵局，應(yīng)該按照怎樣的路線走，所走的路程最短。這個問題是我國管梅谷同志在1962年首先提出的，因此在國際上通稱為中國郵遞員問題。這個問題，實際上就是一類物流配送的最短路問題。下一頁返回4.4單回路運輸路線問題若把郵遞員問題抽象為圖的語言，就是給定一個連通圖，在每條邊上賦予一個非負(fù)的權(quán)，要求一個圈（不一定是簡單的），過每邊至少一次，并使總權(quán)數(shù)最小。1.一筆畫問題在哥尼斯堡城中有一條河叫普雷格爾河，河中有兩個島，河上有七座橋，如圖4-12（a）所示。當(dāng)?shù)鼐用駸嶂杂谶@樣一個問題：一個散布者能否走過七座橋，且每座橋只走過一次，最后回到出發(fā)點。下一頁返回上一頁4.4單回路運輸路線問題1736年，歐拉將此問題歸結(jié)為如圖4-12（b）所示圖形的一筆畫問題，即能否從某一點開始一筆畫出這個圖形，最后回到原點，而不重復(fù)。歐拉證明了這是不可能的，因為圖4-12（b）中的每個點都只與奇數(shù)條線相關(guān)聯(lián)，不可能將這個圖不重復(fù)地一筆畫成，這是古典圖論中的一個著名問題。給定一個連通多重圖G，若存在一條鏈，過每邊一次，且僅一次，則稱這條鏈為歐拉鏈，若存在一個簡單圈，過每邊一次，稱這個圈為歐拉圈。一個圖若有歐拉圈，則成為歐拉圖。下一頁返回上一頁4.4單回路運輸路線問題定理連通多重圖G是歐拉圖，當(dāng)且僅當(dāng)G中無奇點。推論連通多重圖G有歐拉鏈，當(dāng)且僅當(dāng)G恰有兩個奇點。上述定理和推論為我們提供了一個識別一個圖能否一筆畫出的較為簡單的辦法。2.奇偶點圖上作業(yè)法如果在某郵遞員所負(fù)責(zé)的范圍內(nèi)，街道圖中沒有奇點，那么他就可以從郵局出發(fā)，走過每條街道一次且僅一次，最后回到郵局，這樣他所走的路程也就是最短的路程。而對于有奇點的街道，就必須在某些街道上重復(fù)走一次或多次。下一頁返回上一頁4.4單回路運輸路線問題如圖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單回路運輸路線問題如果在某條路線中，邊[vi，vj]上重復(fù)走了幾次，可以在圖中vi，vj之間增加幾條邊，因每邊的權(quán)和原來的權(quán)相等，并把新增加的邊稱為重復(fù)邊。于是這條路線就是相應(yīng)的新圖中的歐拉圈。在圖4-13中，上邊兩條路線分別是圖4-14（a）和（b）中的歐拉圈。顯然，兩條郵遞路線的總路程的差必等于相應(yīng)的重復(fù)邊總權(quán)的差。因而，原來的問題可以敘述為在一個有奇點的圖中，要求增加一些重復(fù)邊，使新圖不含奇點，并且重復(fù)邊的總權(quán)為最小。把使新圖不含奇點而增加的重復(fù)邊，簡稱為可行（重復(fù)邊）方案。使總權(quán)最小的可行方案稱為最優(yōu)方案。下一頁返回上一頁4.4單回路運輸路線問題現(xiàn)在的問題是第一個可行方案如何確定，在確定一個可行方案后，怎么判斷這個方案是否為最優(yōu)方案？若不是最優(yōu)方案，如何調(diào)整這個方案?（1）第一個可行方案的確定方法我們知道，在任何一個圖中，奇點個數(shù)必為偶數(shù)。所以如果圖中有奇點，就可以把它們配成對。又因為圖是連通的，故每一對奇點之間必有一條鏈，我們把這條鏈的所有邊作為重復(fù)邊加到圖中去，則新圖中必?zé)o奇點，這就給出了第一個可行方案。下一頁返回上一頁4.4單回路運輸路線問題例4-8圖4-15中的街道圖，有四個奇點，v2，v4，v6，v8，把v2與v4分為一對，v6與v8為一對。在圖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。這個圖沒有奇點，是歐拉圖。這是個可行方案，重復(fù)邊的總權(quán)數(shù)可計算出為51。下一頁返回上一頁4.4單回路運輸路線問題（2）調(diào)整可行方案，使重復(fù)邊總長度下降從圖4-16中可以看出，有一些邊上有兩條重復(fù)邊，比如[v1，v8]，如果把它們都從圖中去掉，圖仍然無奇點，還是可行方案，但邊的總長度卻有所下降。一般情況下，如果邊上有兩條或兩條以上的重復(fù)邊時，我們從中去掉偶數(shù)條，就能得到一個總長度較小的可行方案。為了得到總長度最小的最優(yōu)方案，我們需遵守以下兩條原則：①在最優(yōu)方案中，圖的每一邊上最多有一條重復(fù)邊。②在最優(yōu)方案中，圖中每個圈上的重復(fù)邊的總權(quán)不大于該圈總權(quán)的一半。下一頁返回上一頁4.4單回路運輸路線問題按照上面的原則，圖4-16可以調(diào)整為圖4-17，重復(fù)邊總權(quán)下降到21。進一步地，如果把圖中某個圈上的重復(fù)邊去掉，而給原來沒有重復(fù)邊的邊上加上重復(fù)邊，圖中仍然沒有奇點。如果新的重復(fù)邊總權(quán)數(shù)比原先的重復(fù)邊總權(quán)數(shù)小，將會得到一個總權(quán)下降的可行方案。事實上，較小權(quán)數(shù)的重復(fù)邊，其總權(quán)數(shù)應(yīng)當(dāng)小于其所在圈的總權(quán)的一半。經(jīng)過調(diào)整，得到圖4-18，重復(fù)邊總長度下降為17。下一頁返回上一頁4.4單回路運輸路線問題（3）判斷最優(yōu)方案的標(biāo)準(zhǔn)從上面的分析可知，一個最優(yōu)方案一定是滿足上述（1）和（2）兩個條件的可行方案?？梢宰C明，一個可行方案若滿足（1）和（2），這個可行方案一定是最優(yōu)方案。根據(jù)這樣一個判別標(biāo)準(zhǔn)，對給定的可行方案，檢查它是否滿足上述兩個條件。若滿足，所得方案即為最優(yōu)方案；若不滿足，則對方案進行調(diào)整，直至滿足上述兩個條件為止。下一頁返回上一頁4.4單回路運輸路線問題檢查圖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ù)邊總長度下降為15。再檢查，條件（1）和（2）都滿足，于是得到了最優(yōu)方案。圖4-20中的任意一個歐拉圈就是郵遞員的最優(yōu)郵遞路線。以上求最優(yōu)郵遞路線的方法，通常稱為奇偶點圖上作業(yè)法。該方法的主要困難在于檢查條件（2），當(dāng)圖中點、邊數(shù)較多時，圈的個數(shù)將會很多，比如“日”字形的圖有3個圈，而“田”字形的圖就有13個圈。下一頁返回上一頁4.4單回路運輸路線問題4.4.2旅行商問題旅行商問題大意是說：一個旅行商從某一個村莊出發(fā)，到周圍若干個村莊進行銷售，每個村莊都要走到，而且只去一次，最后返回出發(fā)點，試問應(yīng)按什么順序走遍所有村莊，同時使所走路程最短。這個問題屬于組合最優(yōu)化問題，當(dāng)村莊數(shù)量不太大時，利用動態(tài)規(guī)劃方法求解是很方便的。下面通過一個具體的例子來說明如何應(yīng)用動態(tài)規(guī)劃方法求解簡單的旅行商問題。下一頁返回上一頁4.4單回路運輸路線問題例4-9求解四個城市旅行推銷員問題，其距離矩陣如表4-2所示，當(dāng)推銷員從1城市出發(fā)，經(jīng)過每個城市一次且僅一次，最后回到1城市，問按怎樣的路線走，能使總的行程距離最短。解：按順序解法的思路：第一階段：從1城市開始，中間經(jīng)過一個城市到達某城市i的最短距離分別是：當(dāng)i=2時，經(jīng)過3城的最短距離是d132=d13+d32=5+9=14當(dāng)i=2時，經(jīng)過4城的最短距離是d142=d14+d42=6+7=13下一頁返回上一頁4.4單回路運輸路線問題當(dāng)i=3時，經(jīng)過2城的最短距離是d123=d12+d23=8+8=16當(dāng)i=3時，經(jīng)過4城的最短距離是d143=d14+d43=6+8=14當(dāng)i=4時，經(jīng)過2城的最短距離是d124=d12+d24=8+5=13當(dāng)i=4時，經(jīng)過3城的最短距離是d134=d13+d34=5+5=10第二階段：從1城市開始，中間經(jīng)過兩個城市（順序隨便）到達某城市i的最短距離分別是：下一頁返回上一頁4.4單回路運輸路線問題當(dāng)i=2時，經(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時，經(jīng)過2、4城的最短距離是d1[24]3=min[d124+d43，d142+d23]=[13+8，13+8]=21路線為1-2-4-3。下一頁返回上一頁4.4單回路運輸路線問題當(dāng)i=4時，經(jīng)過2、3城的最短距離是d1[23]4=min[d123+d34，d132+d24]=[16+10，14+5]=19路線為1-3-2-4。第三階段：從1城市開始，中間經(jīng)過三個城市（順序隨便）回到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多回路運輸路線隨著社會經(jīng)濟的不斷發(fā)展，作為“第三利潤源”的物流越來越引起人們的關(guān)注，其中物流配送車輛優(yōu)化調(diào)度問題是物流中關(guān)鍵的一環(huán)，對其進行優(yōu)化調(diào)度，可以提高物流經(jīng)濟效益、實現(xiàn)物流科學(xué)化。物流配送車輛優(yōu)化調(diào)度問題最早是由Dantzig和Ramser于1959年首次提出的，稱之為VehicleRoutingProblem（簡稱VRP）。該問題一般定義為：對一系列給定的顧客（取貨點或送貨點），確定適當(dāng)?shù)呐渌蛙囕v行駛路線，使其從配送中心出發(fā)，有序地通過它們，最后返回配送中心，并在滿足一定的約束條件下（如車輛容量限制、顧客需求量、交發(fā)貨時間等），達到一定的目標(biāo)（如路程最短、費用最少等）。下一頁返回4.5多回路運輸路線車輛路徑問題（VRP問題）是組合優(yōu)化領(lǐng)域中著名的NP難題。近二十年來，無論在國內(nèi)外，VRP問題都是一個非?；钴S的研究領(lǐng)域。目前解決該問題的現(xiàn)代數(shù)學(xué)方法主要分為以下幾類：1.精確優(yōu)化方法包括分枝定界算法、Ｋ度中心樹及相關(guān)算法、動態(tài)規(guī)劃、集合劃分和列產(chǎn)生、三索引車輛流方式、二索引車輛流方式等。但精確算法的計算復(fù)雜度很高，隨著運輸系統(tǒng)的復(fù)雜化和對調(diào)度的多目標(biāo)要求，獲得整個系統(tǒng)的精確優(yōu)化解越來越困難，花費的時間和費用太大，因此精確解法不能應(yīng)用于規(guī)模較大的物流配送車路由問題的求解，僅用于運輸調(diào)度的局部優(yōu)化問題。下一頁返回上一頁4.5多回路運輸路線2.啟發(fā)式方法（Heuristics）指通過經(jīng)驗法則來求取運輸過程滿意解的數(shù)學(xué)方法。啟發(fā)式方法能同時滿足詳細(xì)描繪問題和求解的需要，較精確優(yōu)化方法更為簡單實用，缺點是難于知道什么時候好的啟發(fā)式解己經(jīng)被求得。啟發(fā)式方法中最具代表性的就是由Clarck和Wright提出的節(jié)約法（SavingMethod）。許多成功的車輛調(diào)度軟件就是根據(jù)該方法或其改進方法開發(fā)的。下一頁返回上一頁4.5多回路運輸路線典型啟發(fā)式算法中還包括由Lin和Kemighan提出的，并由Chtistofidests和GilbertlaPorte等人所推廣的分支交換探索法，該算法始終保持解的可行性而又力圖向最優(yōu)目標(biāo)前進。在每一步，都改變一個可行解而減少總費用，直到這個過程繼續(xù)到不再可能使費用減少為止。Gillet和Milled提出的掃描法（SweepMethod）先把節(jié)點或弧的需求進行分組或劃群，然后對每一組按旅行商問題（TSP）求解，設(shè)計出一條經(jīng)濟的路線。此外，常用的啟發(fā)式方法還有2-階段法、不完全樹搜索算法等。各種啟發(fā)式方法的主要區(qū)別在于收斂的速度和程度不同。下一頁返回上一頁4.5多回路運輸路線精確優(yōu)化方法是以往廣泛采用的方法，另外三種方法則代表了最近研究的方向。尤其是啟發(fā)式方法，作為一種逐次逼近的算法，雖然不一定得到最優(yōu)解，但是可以高效率地得到具有較高精度的解，而且也易于考慮各種實際問題，因此，現(xiàn)己成為解決配送問題的重要方法。啟發(fā)式算法中最具有代表性的就是由克拉克（Clarke）和懷特（Wright）提出的節(jié)約法（SavingMethod）。下面說明節(jié)約法思考的基本方法。下一頁返回上一頁4.5多回路運輸路線設(shè)有一個配送中心,兩個配送點和,若配送中心向配送點分別單獨送貨，則運輸路線為,

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

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

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