運輸系統(tǒng)及運輸優(yōu)化

1、物流與供應鏈管理物流與供應鏈管理高等教育出版社高等教育出版社現(xiàn)代物流叢書現(xiàn)代物流叢書第第6章章 運輸系統(tǒng)及運輸優(yōu)化運輸系統(tǒng)及運輸優(yōu)化現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理2現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理3物流網(wǎng)絡的物流網(wǎng)絡的“運輸連接點運輸連接點”“”“運輸路徑運輸路徑”“”“運輸手段運輸手段”車站物流中心港口機場貨場運輸連接點車站物流中心港口機場貨場運輸連接點運輸手段運輸路徑汽車 飛機船舶 列車 管道公路 水路 管網(wǎng)航空線路 鐵路運 輸圖圖6.1 6.1 運輸網(wǎng)絡示意圖運輸網(wǎng)絡示意圖現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理46.1 運輸系統(tǒng)的重要性與功能6.1.

2、1運輸系統(tǒng)的重要性p地域分工專業(yè)化p規(guī)模經(jīng)濟p競爭加劇p土地價值的提高現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理56.1.2 運輸?shù)墓δ苓\輸?shù)囊粋€特性是移動，包括速度（不管是門到門，還是站到站）、可靠性和服務頻率。另一個特性是要使用運輸設(shè)備，設(shè)備影響運輸?shù)臏蕚洹⑦\輸貨物的大小和裝卸成本。第三個方面是運輸服務具有成本，包括主要服務的費用以及由使用者承擔的附加費用。后者包括取貨和送貨成本、包裝成本、損壞和滯留成本以及其他特殊服務。運輸?shù)墓δ苤饕w現(xiàn)在時間和空間效用上：p產(chǎn)品轉(zhuǎn)移p產(chǎn)品儲存現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理66.1.3 運輸服務的特征p運輸成本p運輸時間（速度）p運輸

3、時間變化率（一致性）p安全性p可達性p受理能力現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理76.1.4 影響運輸決策的因素p影響承運人決策的因素 與運輸工具相關(guān)的成本 固定運營成本 與運距有關(guān)的成本 與運量有關(guān)的成本 運營成本p托運人決策的影響因素 運輸成本 庫存成本 作業(yè)成本 服務水平成本現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理86.2 承運人運營l6.2.1 基本運輸方式及其運營特點p1鐵路運輸 優(yōu)點 （1）承運能力大，適合大批量低值物品及長距離運輸； （2）鐵路運輸不大受氣候和自然條件影響，在運輸?shù)臏蕰r性方面有優(yōu)勢； （3）鐵路運輸可以方便地實現(xiàn)馱背運輸、集裝箱運輸及多式聯(lián)運。

4、缺點 （1）固定成本高，項目投資大，建設(shè)周期較長； （2）運輸時間較長，在運輸過程中需要有列車編組、解體和中轉(zhuǎn)改編等作業(yè)環(huán)節(jié)，占用時間較長，因而增加了貨物的運輸時間。 （3）鐵路運輸中的貨損率比較高。由于裝卸次數(shù)較多，貨物毀損或滅失事故通常比其它運輸方式多。 （4）不能實現(xiàn)“門到門”運輸。如果托運人和收貨人都有專用線，可以提供工“門到門”服務。如果沒有專用線，則貨物運送必須用其他方式來協(xié)助完成?，F(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理9p2公路運輸 由于汽車已經(jīng)成為公路運輸?shù)闹饕\載工具，因此，現(xiàn)代公路運輸主要指汽車運輸。 優(yōu)點 速度 可達性 運輸?shù)钠椒€(wěn)性 靈活性由于汽車運輸具有上述優(yōu)點

5、，更由于高速公路網(wǎng)的不斷延伸，在世界范圍內(nèi)汽車運輸迅速發(fā)展，并超過鐵路和其他運輸方式。但是汽車運輸也存在一些問題，主要是裝載量少，運輸成本高，燃料消耗大，環(huán)境污染比其它運輸方式嚴重得多。現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理10p3航空運輸航空運輸與其他運輸方式相比較，有以下幾個特征： 速度快 安全性高 包裝要求低 受氣候條件限制 可達性差現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理11p4水路運輸 水路運輸按航行區(qū)域，大體上可以劃分為海洋運輸和內(nèi)河運輸兩種類型。水上服務僅限于一定范圍。國內(nèi)水運服務受限于內(nèi)陸水運系統(tǒng)，要求托運人靠近水路或使用其他運輸方式接應水運。 與其他運輸方式相比

6、，水運造成的貨物滅失和損壞成本較低，因為貨主對低價值散裝貨的破損不太關(guān)心，延遲帶來的損失也不嚴重（買方經(jīng)常囤積大量庫存） 水路運輸?shù)闹匾攸c是利用天然水道，進行大噸位、長距離的運輸，由于運量大、成本低，非常適合于運輸大宗貨。與其他運輸方式相比，水運對貨物的載運和裝卸要求不高，因而占地較少。 水路運輸?shù)娜秉c也顯而易見。一是速度慢，船舶平均航速較低，不能快速將貨物運達目的地；二是水路運輸受自然條件影響大，特別是受氣候條件影響較大，比如斷流、臺風影響等，因而呈現(xiàn)較大的波動性。 現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理12p5管道運輸 管道是很獨特的運輸方式，它所能運送的貨物種類很有限，4種主要

7、通過管道運輸?shù)呢浳锸牵菏图俺善酚汀⑻烊粴?、煤、化學制品。 管道運輸?shù)囊粋€主要優(yōu)勢是費用低。大直徑、全負荷管道運輸效率很高。管道提供的是地下的、全封閉的服務，因此，貨損、貨差率低。另外，因為管道運輸速度很慢，還可以將管道作為倉庫。也就是說，如果產(chǎn)品不是急用，緩慢的管理運輸可以看作是免費倉庫存儲。 管道的另一個服務優(yōu)勢是它的可靠性。管道運輸基本上不受天氣影響，很少有機械故障。雖然運輸時間長，但能準確估計交貨時間，減少了安全庫存的需要。 管道運輸也有相對劣勢。首先，管道線路是相對固定的，因此有地域靈活性或可達性的限制。其次，管道運輸?shù)漠a(chǎn)品有局限性，并且只能提供單向服務?，F(xiàn)代物流叢書-物流與供應鏈管

8、理物流與供應鏈管理13表6.2 各種運輸方式的成本和運作績效的相對排名運輸方式運作特點成本1=最高平均運送時間1=最快運作時間的變化率安全性1=最高絕對值1=最低百分比1=最低鐵路運輸33435公路運輸22324航空運輸11153水上運輸55542管道運輸44211每噸-公里成本 門到門的速度 絕對變化除以平均運送時間的比率現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理146.2.2 綜合運輸與特殊運輸1綜合運輸綜合運輸 綜合運輸是指在把貨物從出發(fā)地運往目的地的過程中使用兩種或多種運輸方式，又稱作多式聯(lián)運。 （1）鐵路運輸和卡車運輸;（2）鐵路運輸和水上運輸;（3）鐵路運輸和航空運輸;（4）鐵

9、路運輸和管道運輸;（5）卡車運輸和航空運輸;（6）卡車運輸和水上運輸;（7）卡車運輸和管道運輸;（8）水上運輸和管道運輸;（9）水上運輸和航空運輸;（10）航空運輸和管道運輸?，F(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理15（1）駝背運輸（2）集裝箱運輸2特殊的承運人形式特殊的承運人形式（1）運輸代理）運輸代理（2）快運業(yè)務和快遞業(yè)務）快運業(yè)務和快遞業(yè)務現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理166.2.3 自有運輸l優(yōu)點p提升服務p降低成本l缺點p空車回程（empty backhaul）p缺乏專業(yè)貨運管理技術(shù)p資金可用性p貨物丟失和損壞現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理1

10、76.2.4 國際運輸p國際貨物運輸方式主要有海洋運輸、國際鐵路運輸、航空運輸、汽車運輸和其他一些特殊的運輸方式，如國際郵政運輸、管道運輸和集裝箱運輸?shù)?。買賣雙方協(xié)定國際貿(mào)易術(shù)語解釋通則運輸運輸主要承運人國內(nèi)承運人貨物運輸保險中介人港口海關(guān)國外承運人準備訂貨準備訂貨生產(chǎn)挑選物品包裝辦理單證辦理單證出口許可證銷售單據(jù)財務結(jié)算單據(jù)海關(guān)單證運輸單據(jù)顧客顧客圖6-2 國際運輸程序現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理186.2.5 運輸定價1. 運輸管理中的定價運輸管理中的定價（1 1）影響定價決策的因素）影響定價決策的因素 許多人承運人的定價決策受到商業(yè)環(huán)境的影響，包括客戶（市場）、政府、其

11、他渠道成本和競爭。（2 2）主要定價決策）主要定價決策對全新運輸服務的定價。 運輸服務價格變更。應對市場價格變化的定價。 （3 3）運輸定價方法）運輸定價方法按服務成本定價。 按服務價值定價。 綜合定價。 現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理192. 運價結(jié)構(gòu)運價結(jié)構(gòu)（1 1）線路定價）線路定價 按產(chǎn)品分類。 協(xié)議運價。 按運輸批量劃分（2 2）貨物運輸其他收費）貨物運輸其他收費 調(diào)車費。延滯費。貨（箱）落空損失費。 道路阻塞停車費。 車輛處置費。 車輛通行費。 運輸變更手續(xù)費。 現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理206.3 運輸最優(yōu)化6.3.1 運輸合理化 影響物流運輸

12、合理化的因素很多，起決定作用的有五個方面，稱作合理運輸?shù)摹拔逡亍薄?p1運輸距離p2運輸環(huán)節(jié)p3運輸工具p4運輸時間p5運輸費用現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理21不合理的運輸主要有以下幾種表現(xiàn)形式：p1對流運輸；p2迂回運輸；p3過遠運輸；p4重復運輸；p5無效運輸；p6運力選擇不當現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理22l6.3.2 運輸服務的選擇 運輸成本、速度和一致性是決策者心目中最重要的運輸服務要素，因此，這三項是運輸服務選擇的基礎(chǔ)。 運輸方式的選擇即是戰(zhàn)術(shù)性決策又是操作性決策。與某個承運商簽訂合同的決策屬于戰(zhàn)術(shù)性決策，而具體運輸方式的選擇則是操作性決策。對

13、于兩種決策來說，托運人都必須權(quán)衡運輸成本和庫存成本。一種運費最低的運輸方式，并不一定使總運輸成本最低。運輸?shù)乃俣群涂煽啃詴绊懲羞\人和買方的庫存水平（訂貨庫存和安全庫存）以及他們之間的在途庫存水平。運輸對庫存的影響有以下幾點： （1）較慢的運輸模式會引起較大的中轉(zhuǎn)或運輸庫存； （2）較大運量的運輸方式會出現(xiàn)訂單批量超過需求量的情況，從而增加庫存； （3）不可靠的運輸模式會引起安全庫存的提高。 在選擇運輸方式時，就需要考慮庫存持有成本可能升高，而抵消運輸服務成本降低的情況。因此，選擇運輸方式時的最合理方案應該是，既能滿足顧客需求，又使總成本最低的服務。現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管

14、理23例例6.16.1 某箱包公司生產(chǎn)系列箱包產(chǎn)品，其分撥計劃是將生產(chǎn)的成品先存放在工廠，然后由工廠運往公司自有的基層倉庫。目前，公司使用鐵路運輸將工廠的成品運往倉庫。鐵路運輸?shù)钠骄鶗r間為T=21天，每個存儲點平均儲存100000件箱包，箱包的平均價值C=30元，庫存成本I=30%每年。 公司希望選擇使總成本最小的運輸方式。據(jù)估計，運輸時間從目前的21天每減少一天，平均庫存水平可以減少1%。每年倉庫賣出D=700000件箱包。公司可以利用以下運輸服務： 其中采購成本和運輸時間的變化忽略不計。運輸服務方式運輸費率(元/單位)門到門運送時間T（天）每年運輸批次鐵路運輸0.12110卡車運輸0.25

15、20航空運輸1.4240現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理24解答：解答：在選擇運輸方式時要考慮總成本，包括運輸成本，不同運輸方式的運輸成本不同，各種運輸方式下的運輸成本為年運輸量與運輸費率的乘積。在途貨物的庫存成本，不同運輸方式將影響貨物的在途時間，在途庫存的持有成本不同。在途庫存成本為ICDT/365分撥渠道兩端的庫存成本。分撥渠道兩端的平均庫存大約是Q/2，其中Q是運輸批量。每單位貨物的庫存成本為IC，但產(chǎn)品價值C在分撥渠道的不同地點是不同的。在工廠，C是產(chǎn)品的出廠價值，在倉庫，C是產(chǎn)品的出廠價值加上運輸費率。計算各種運輸方式下的總成本:現(xiàn)代物流叢書-物流與供應鏈管理物流與供

16、應鏈管理25成本類型鐵路運輸卡車運輸航空運輸運輸成本0.1700000=700000.2700000=1400001.4700000=980000在途庫存0.33070000021/365=3624660.3307000005/365=863010.3307000002/365=34521工廠庫存0.33070000/2=6300000.33035000/20.84=2646000.33017500/20.81=127575倉庫庫存0.330.170000/2=3160500.330.235000/20.84=1331820.330.417500/20.81=64638合計1378516624

17、0831206734 由上表可以看出，雖然采用鐵路運輸時的運輸費率最低，采用航空運輸時的庫存成本最低，但卡車運輸?shù)目偝杀咀畹汀Ｈ绻褂每ㄜ囘\輸，運輸時間減少到5天，兩個端點的庫存水平比使用鐵路運輸減少50%?，F(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理26l6.3.3 運輸路線的選擇1起、止點不同的單一路徑規(guī)劃起、止點不同的單一路徑規(guī)劃 這類路徑規(guī)劃問題稱為最短路問題。最短路徑問題是線路優(yōu)化模型理論中最為基礎(chǔ)的問題之一。 問題描述：假設(shè)有一n個節(jié)點和m條弧的連通圖G（Vn,Em),并且圖中的每條弧（i,j)都有一個長度cij(或者費用cij)，則最短路徑問題為：在連通圖中找到一條從節(jié)點1到節(jié)

18、點n距離最短（或費用最低）的路徑。 求解此類最短路徑問題，主要有以下幾種算法：（1）Dijkstra算法；（2）逐次逼近法；（3）Floyd算法。下面通過一個實例對該類問題進行說明?，F(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理27例例6.26.2 某運輸公司簽訂了一項運輸合同，要把A市的一批貨物運送到B市，該公司根據(jù)這兩個城市之間可選擇的行車路線的地圖繪制了如圖所示的公路網(wǎng)絡。圖中，圓圈也稱節(jié)點，代表起點、目的地和與行車路線相交的其他城市。鏈代表兩個結(jié)點之間的公路，每一條公路都標明運輸里程。2165434283274111A市市B市市圖6-3 A、B兩地之間運輸路線示意圖 可以看出，從A市出

19、發(fā)到達B市，可以有很多條路線可以選擇。但是如何選擇運輸路線，才能使總路程的長度最短？這就是運輸規(guī)劃中的最短路問題?，F(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理28解答：最短路的計算方法（1）找出第n個距起點最近的節(jié)點。對n=1,2,，重復此過程，直到所找出的最近節(jié)點是終點。（2）在前面的迭代過程中找出（n-1）個距起點最近的節(jié)點，及其距起點最短的中徑和距離，這些節(jié)點和起點統(tǒng)稱為已解的節(jié)點，其余的稱為未解節(jié)點。（3）每個已解的節(jié)點和一個或多外未解的節(jié)點相連接，就可以得出一個候選點連接距離最短的未解點。如果有多個距離相等的最短連接，則有多個候選點。（4）將每個已解節(jié)點與其候選點之間的距離累加到該

20、已解節(jié)點與起點之間最短路徑的距離上，所得出的總距離最短的候選點就是第n個最近的節(jié)點，其最短路徑就是得出該距離的路徑（若多個候選點都得出相等的最短距離，則都是已解節(jié)點）。現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理29步驟直接連接到未解節(jié)點的已解節(jié)點與其直接連接的未解結(jié)點相關(guān)總成本第n個最近解點最小成本最新連接11123411241-22122345114+7=114+2=6562-5312553446114+7=116+3=96+8=14495-4414453366119+1=109+4=136+8=143104-3534566610+2=129+4=136+8=146123-6表6.3 最

21、短路徑法的計算步驟表通過上表的計算可知，最短路徑為1-2-5-4-3-6，最短距離為12。最短路徑法適合利用計算機進行求解，把運輸網(wǎng)絡中的鏈和節(jié)點的資料都存入數(shù)據(jù)庫中，選好起點和終點后，計算機可以很快就算出最短路徑?，F(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理302多個起、止點的路徑規(guī)劃多個起、止點的路徑規(guī)劃 當有多個貨源和多個目的地時，就需要指定目的地的供貨地，同時要找到供貨地、目的地之間的最佳路徑。例例6.3 某公司下屬三個倉庫，供應四個客戶的需要，三個倉庫的供應量和四個客戶的需求量，以及由各倉庫到各客戶的運輸單價如下表所示。求運輸費用最少的運輸方案。 銷地客戶1客戶2客戶3客戶4供應量

22、運價產(chǎn)地倉庫A311310700倉庫B1928400倉庫C74105900需求量3006005006002000現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理31表上做業(yè)法，該方法適合于對相對簡單的問題進行求解，求解過程方便直觀，而且由于計算量不大，可以用手工直接完成。利用表上作業(yè)法有兩個基本步驟：（1）確定初始調(diào)運方案 最小元素法是按運價表依次挑選運費小的供-需點組合，盡量優(yōu)先安排運費最低組合的方法。 3113101928734105 銷地客戶1客戶2客戶3客戶4供應量運價產(chǎn)地倉庫A400300700倉庫B300100400倉庫C600300900需求量300600500600表6.4 初始

23、調(diào)運方案現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理32（2）初始方案的檢驗最優(yōu)方案的數(shù)字特征檢驗數(shù)：閉回路：閉回路： 從理論上講，對于表上作業(yè)法的初始方案來說，從調(diào)運方案表上的一個空格出發(fā)，存在一條且僅存在一條以該空格（用xij表示）為起點，以其他填有數(shù)字的點為其他頂點的閉合回路，簡稱閉回路。這個閉回路有以下性質(zhì)：每個頂點都是轉(zhuǎn)角點；閉合回路是一條封閉折線，每一條邊都是水平或垂直的；每一行（列）若有閉合回路的頂點，則必有兩個。 只有從空格出發(fā)，其余各轉(zhuǎn)角點所對應的方格內(nèi)均填寫數(shù)字時，所構(gòu)成的閉合回路才是我們所說的閉回路；另外，過任一空格的閉合回路不僅是存在的，而且是唯一的。現(xiàn)代物流叢書-物

24、流與供應鏈管理物流與供應鏈管理33 銷地客戶1客戶2客戶3客戶4供應量產(chǎn)地倉庫A400300700倉庫B300100400倉庫C600300900需求量300600500600 表6.5給出了單元格（1，1）和（3，1）所形成的閉回路：（1，1）（1,3）(2，3)（2，1）（1，1）（3，1）（2，1）（2，3）（1，3）（1，4）（3，4）（3，1）。其他空格的閉回路與此同理。 在調(diào)運方案內(nèi)的每個空格所形成的閉回路上，作單位物資的運量調(diào)整，總可以計算出相應的運費是增加還是減少。我們把所計算出來的每條閉回路上調(diào)整單位運量而使運輸費用發(fā)生變化的增減值，稱其為檢驗數(shù)。如果檢驗數(shù)小于0，表示在該空

25、格的閉回路上調(diào)整運量會使運費減少；相反，如果檢驗數(shù)大于0，則會使運費增加。表6.5 初始調(diào)運方案現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理34用閉回路法求檢驗數(shù)時，需給每一空格找一條閉回路。當產(chǎn)銷點很多時，這種計算很繁，可以用較為簡便的方法“位勢法”求解。設(shè)u1,u2,um；v1,v2,vn，是對應運輸問題的m+n個約束條件的對偶變量。在初始調(diào)運方案中x13,x14,x21,x23,x32,x34是基變量，這時對應的檢驗數(shù)是：基變量 檢驗數(shù)x21 c21-( u2+v1)=0 設(shè)v1=0，并且c21=1 所以 u2=1x23 c23-(u2+v3)=0 2-( u2+v3)=0 x13 c

26、13-(u1+v3)=0 3-( u1+v3)=0 x14 c14-(u1+v4)=0 10-( u1+v4)=0 x34 c34-(u3+v4)=0 5-( u3+v4)=0 x22 c22-(u2+v2)=0 4-( u2+v2)=0現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理35通過這些方程可以求得u1=2 u2=1 u3= -3 v1=0 v2=7 v3=1 v4=8在初始解調(diào)運方案中增加一行一列，在列中填入ui,在行中填入vi。接下來，按ij=cij-(ui+vj)計算所有空格的檢驗數(shù)。完成后的表格見表6.6。3113101928734105 銷地客戶1客戶2客戶3客戶4ui運價產(chǎn)

27、地倉庫A12002倉庫B010-11倉庫C100120-3vi0718表6.6 檢驗數(shù)表格現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理36（3）方案調(diào)整 判定一個初始調(diào)運方案不是最優(yōu)調(diào)運方案的標準，是在檢驗數(shù)表格中出現(xiàn)負值的檢驗數(shù)。如果檢驗數(shù)的負值不止個時，一般選擇負檢驗數(shù)絕對值最大的空格作為具體調(diào)整對象。 從表6.6可以發(fā)現(xiàn)，單元格x24的檢驗數(shù)是負數(shù)，因此對其進行調(diào)整，具體過程如表6.7所示。x13x14x13400+100=500 x14300-100=200 x23100-100=0 x240+100=100表表6.7 調(diào)動方案調(diào)整表調(diào)動方案調(diào)整表 從單元格x24開始，沿閉回路在各奇

28、數(shù)次轉(zhuǎn)角點中挑選運量的最小數(shù)值作為調(diào)整量。在此將x23單元格的100作為調(diào)整量，將亮個數(shù)填入單元格x24內(nèi)，同時調(diào)整該閉回路中其他轉(zhuǎn)角點上的運量，使各行、列保持原來的供需平衡，這樣注得到一個新的調(diào)運方案，如表6.7所示。現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理373113101928734105 銷地客戶1客戶2客戶3客戶4供應量 運價產(chǎn)地倉庫A500200700倉庫B300100400倉庫C600300900需求量300600500600表6.7 調(diào)整后的方案按新方案計算調(diào)運物資的運輸費用為：3500+10200+8100+4600+5300=8500元新方案是否最優(yōu)方案，還需再進行檢

29、驗。經(jīng)計算，該新方案的所有檢驗數(shù)都是非負數(shù)，說明該方案已經(jīng)是最優(yōu)方案了?，F(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理383起點和終點相同的路徑規(guī)劃起點和終點相同的路徑規(guī)劃 物流管理人員經(jīng)常會遇到起點和終點相同的路徑規(guī)劃問題。例如，從某倉庫送貨到零售店然后返回的路線；從零售店到客戶地點配送的路線規(guī)劃。起點和終點重合的路徑問題一般被稱為“流動推銷員”問題（TSP, Traveling Salesman Problem），是運籌學、圖論和組合優(yōu)化中的典型問題。 TSP問題一般描述如下：一個旅行者從出發(fā)地出發(fā)，經(jīng)過所有要到達的城市后，返回到出發(fā)地，要求合理安排其旅行路線，使得總旅行距離（或旅行費用、

30、旅行時間等）最短。人們已經(jīng)提出不少方法來解決這類問題。如果某個問題中包含很多個點，要找到最優(yōu)路徑是不切實際的，因為許多現(xiàn)實問題的規(guī)模太大。啟發(fā)式算法是求解這類問題的好辦法?，F(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理39 車輛路線安排問題（車輛路線安排問題（VRP, Vehicle Routing Problem）是指對物流配送的車輛進行優(yōu)化調(diào)度。該問題一般可以描述如下：對一系列裝貨點或（和）卸貨點，組織適當合理的行車路線，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量、數(shù)目限制、車輛行駛里程、時間限制等）下，達到一定的目標（如最短路程、最小費用、最

31、短時間、最少車輛等）。該問題涉及了多輛交通工具的服務對象的選擇和路徑（服務順序）確定兩方面的問題。 VRP問題是組合優(yōu)化領(lǐng)域著名的NP難題之一，求解方法一般相當復雜，通常的做法是應用相關(guān)技術(shù)問題分解或者轉(zhuǎn)化為一個或多個已經(jīng)研究過的基本問題（如旅行商問題、指派問題、最短路問題等），再使用相對比較成熟的基本理論和方法進行求解。6.3.4 車輛路線安排現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理40運用VRP模型對實際問題進行研究時，一般需要考慮以下幾個方面的問題：u（1）倉庫。倉庫的級數(shù)，每級倉庫的數(shù)量、地點和規(guī)模。u（2）車輛。車輛的型號和數(shù)量，每種車輛的容積和運作費用，出發(fā)時間和返回時間，司

32、機休息時間，最大的里程和時間限制。u（3）時間窗口。由于各處的工作時間不同，每個站點每天只允許在特定的時間內(nèi)取貨和/或送貨。u（4）顧客。顧客需求，裝載、卸載，所處的地理位置，分離需求，優(yōu)先等級。u（5）道路信息。車流密度，道路交通費用，距離或時間屬性。u（6）貨物信息。貨物的種類多少，兼容性，貨物的保鮮。u（7）運輸規(guī)章。工人每天的工作時間，車輛的周期維護?，F(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理41u（1）安排車輛負責相互距離最接近的站點的貨物運輸。u（2）安排車輛各日途經(jīng)站點時，應注意使站點群更加緊湊。如果一周內(nèi)各日服務的站點不同，就應該對一周內(nèi)每天的路線和時刻表問題分別進行站點群

33、劃分。各日站點群的劃分應避免重疊。u（3）從距倉庫最遠的站點開始設(shè)計路線u（4）卡車的行車路線應呈水滴狀。u（5）盡可能使用最大的車輛進行運送，這樣設(shè)計出的路線是最有效的。u（6）取貨、送貨應該混合安排，不應該在完成全部送貨任務之后再取貨。u（7）對過于遙遠而無法歸入群落的站點，可以采用其它配送方式。u（8）避免時間窗口過短。簡化的原則：簡化的原則：現(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理421掃描法掃描法路線設(shè)計中的掃描法很簡單，即使問題規(guī)模很大，也可以通過手工計算得出結(jié)果。掃描法可闡述如下：（1 1）在地圖或方格圖中確定所有站點（含倉庫）的位置。）在地圖或方格圖中確定所有站點（含倉庫

34、）的位置。（2 2）自倉庫始沿任一方向向外劃一條直線。沿順時針或逆時針方向旋轉(zhuǎn)該直線直）自倉庫始沿任一方向向外劃一條直線。沿順時針或逆時針方向旋轉(zhuǎn)該直線直到與某站點相交?？紤]：如果在某線路上增加該站點，是否會超過車輛的載貨能到與某站點相交。考慮：如果在某線路上增加該站點，是否會超過車輛的載貨能力？如果沒有，繼續(xù)旋轉(zhuǎn)直線，直到與下一個站點相交。再次計算累計貨運量是力？如果沒有，繼續(xù)旋轉(zhuǎn)直線，直到與下一個站點相交。再次計算累計貨運量是否超過車輛的運載能力（先使用最大的車輛）。如果超過，就剔除最后的那個站否超過車輛的運載能力（先使用最大的車輛）。如果超過，就剔除最后的那個站點，并確定路線。隨后，從不

35、包含在上一條路線中的站點開始，繼續(xù)旋轉(zhuǎn)直線以點，并確定路線。隨后，從不包含在上一條路線中的站點開始，繼續(xù)旋轉(zhuǎn)直線以尋找新路線。繼續(xù)該過程直到所有的站點都被安排到路線中。尋找新路線。繼續(xù)該過程直到所有的站點都被安排到路線中。（3 3）排定各路線上每個站點的順序使行車距離最短。排序時可以使用）排定各路線上每個站點的順序使行車距離最短。排序時可以使用“水滴水滴”法法或求解或求解“流動推銷員流動推銷員”問題的任何算法。問題的任何算法?，F(xiàn)代物流叢書-物流與供應鏈管理物流與供應鏈管理43例6.4 某公司用廂式貨車從貨主處取貨，圖6-4 (a)是一天的取貨量，單位是件。廂式貨車的載貨量是10000件。完成所

36、有取貨任務需一天時間。公司需要多少條運輸路線（即多少部車），每條路線上應該經(jīng)過哪些站點，每條路線上的站點怎樣排序。 首先，向北畫一條直線，進行逆時針方向“掃描”。這些都是隨機決定的。逆時針旋轉(zhuǎn)該直線，直到裝載的貨物能裝上一輛載重10000件的卡車，同時又不超載。一旦所有的站點都分派有車輛，就可以利用“水滴”法安排經(jīng)過各站點的順序，圖6-4(b)是所列出的最終的路線設(shè)計。200020002000200020002000200020001000100020002000300030001000100040004000200020003000300030003000200020002000200020002000200020001000100020002000300030001000100040004