運(yùn)輸系統(tǒng)及運(yùn)輸優(yōu)化-課件

第6章運(yùn)輸系統(tǒng)及運(yùn)輸優(yōu)化2PPT課件物流網(wǎng)絡(luò)的“運(yùn)輸連接點(diǎn)”“運(yùn)輸路徑”“運(yùn)輸手段”車站物流中心港口機(jī)場(chǎng)貨場(chǎng)運(yùn)輸連接點(diǎn)車站物流中心港口機(jī)場(chǎng)貨場(chǎng)運(yùn)輸連接點(diǎn)運(yùn)輸手段運(yùn)輸路徑汽車飛機(jī)船舶列車管道公路水路管網(wǎng)航空線路鐵路運(yùn)輸圖6.1運(yùn)輸網(wǎng)絡(luò)示意圖3PPT課件6.1運(yùn)輸系統(tǒng)的重要性與功能6.1.1運(yùn)輸系統(tǒng)的重要性地域分工專業(yè)化規(guī)模經(jīng)濟(jì)競(jìng)爭(zhēng)加劇土地價(jià)值的提高4PPT課件6.1.2運(yùn)輸?shù)墓δ苓\(yùn)輸?shù)囊粋€(gè)特性是移動(dòng)，包括速度（不管是門到門，還是站到站）、可靠性和服務(wù)頻率。另一個(gè)特性是要使用運(yùn)輸設(shè)備，設(shè)備影響運(yùn)輸?shù)臏?zhǔn)備、運(yùn)輸貨物的大小和裝卸成本。第三個(gè)方面是運(yùn)輸服務(wù)具有成本，包括主要服務(wù)的費(fèi)用以及由使用者承擔(dān)的附加費(fèi)用。后者包括取貨和送貨成本、包裝成本、損壞和滯留成本以及其他特殊服務(wù)。運(yùn)輸?shù)墓δ苤饕w現(xiàn)在時(shí)間和空間效用上：產(chǎn)品轉(zhuǎn)移產(chǎn)品儲(chǔ)存5PPT課件6.1.3運(yùn)輸服務(wù)的特征運(yùn)輸成本運(yùn)輸時(shí)間（速度）運(yùn)輸時(shí)間變化率（一致性）安全性可達(dá)性受理能力6PPT課件6.1.4影響運(yùn)輸決策的因素影響承運(yùn)人決策的因素與運(yùn)輸工具相關(guān)的成本固定運(yùn)營(yíng)成本與運(yùn)距有關(guān)的成本與運(yùn)量有關(guān)的成本運(yùn)營(yíng)成本托運(yùn)人決策的影響因素運(yùn)輸成本庫存成本作業(yè)成本服務(wù)水平成本7PPT課件6.2承運(yùn)人運(yùn)營(yíng)6.2.1基本運(yùn)輸方式及其運(yùn)營(yíng)特點(diǎn)1．鐵路運(yùn)輸優(yōu)點(diǎn)（1）承運(yùn)能力大，適合大批量低值物品及長(zhǎng)距離運(yùn)輸；（2）鐵路運(yùn)輸不大受氣候和自然條件影響，在運(yùn)輸?shù)臏?zhǔn)時(shí)性方面有優(yōu)勢(shì)；（3）鐵路運(yùn)輸可以方便地實(shí)現(xiàn)馱背運(yùn)輸、集裝箱運(yùn)輸及多式聯(lián)運(yùn)。缺點(diǎn)（1）固定成本高，項(xiàng)目投資大，建設(shè)周期較長(zhǎng)；（2）運(yùn)輸時(shí)間較長(zhǎng)，在運(yùn)輸過程中需要有列車編組、解體和中轉(zhuǎn)改編等作業(yè)環(huán)節(jié)，占用時(shí)間較長(zhǎng)，因而增加了貨物的運(yùn)輸時(shí)間。（3）鐵路運(yùn)輸中的貨損率比較高。由于裝卸次數(shù)較多，貨物毀損或滅失事故通常比其它運(yùn)輸方式多。（4）不能實(shí)現(xiàn)“門到門”運(yùn)輸。如果托運(yùn)人和收貨人都有專用線，可以提供工“門到門”服務(wù)。如果沒有專用線，則貨物運(yùn)送必須用其他方式來協(xié)助完成。8PPT課件2．公路運(yùn)輸由于汽車已經(jīng)成為公路運(yùn)輸?shù)闹饕\(yùn)載工具，因此，現(xiàn)代公路運(yùn)輸主要指汽車運(yùn)輸。優(yōu)點(diǎn)速度可達(dá)性運(yùn)輸?shù)钠椒€(wěn)性靈活性由于汽車運(yùn)輸具有上述優(yōu)點(diǎn)，更由于高速公路網(wǎng)的不斷延伸，在世界范圍內(nèi)汽車運(yùn)輸迅速發(fā)展，并超過鐵路和其他運(yùn)輸方式。但是汽車運(yùn)輸也存在一些問題，主要是裝載量少，運(yùn)輸成本高，燃料消耗大，環(huán)境污染比其它運(yùn)輸方式嚴(yán)重得多。9PPT課件3．航空運(yùn)輸航空運(yùn)輸與其他運(yùn)輸方式相比較，有以下幾個(gè)特征：速度快安全性高包裝要求低受氣候條件限制可達(dá)性差10PPT課件4．水路運(yùn)輸

水路運(yùn)輸按航行區(qū)域，大體上可以劃分為海洋運(yùn)輸和內(nèi)河運(yùn)輸兩種類型。水上服務(wù)僅限于一定范圍。國(guó)內(nèi)水運(yùn)服務(wù)受限于內(nèi)陸水運(yùn)系統(tǒng)，要求托運(yùn)人靠近水路或使用其他運(yùn)輸方式接應(yīng)水運(yùn)。與其他運(yùn)輸方式相比，水運(yùn)造成的貨物滅失和損壞成本較低，因?yàn)樨浿鲗?duì)低價(jià)值散裝貨的破損不太關(guān)心，延遲帶來的損失也不嚴(yán)重（買方經(jīng)常囤積大量庫存）水路運(yùn)輸?shù)闹匾攸c(diǎn)是利用天然水道，進(jìn)行大噸位、長(zhǎng)距離的運(yùn)輸，由于運(yùn)量大、成本低，非常適合于運(yùn)輸大宗貨。與其他運(yùn)輸方式相比，水運(yùn)對(duì)貨物的載運(yùn)和裝卸要求不高，因而占地較少。水路運(yùn)輸?shù)娜秉c(diǎn)也顯而易見。一是速度慢，船舶平均航速較低，不能快速將貨物運(yùn)達(dá)目的地；二是水路運(yùn)輸受自然條件影響大，特別是受氣候條件影響較大，比如斷流、臺(tái)風(fēng)影響等，因而呈現(xiàn)較大的波動(dòng)性。11PPT課件5．管道運(yùn)輸

管道是很獨(dú)特的運(yùn)輸方式，它所能運(yùn)送的貨物種類很有限，4種主要通過管道運(yùn)輸?shù)呢浳锸牵菏图俺善酚?、天然氣、煤、化學(xué)制品。管道運(yùn)輸?shù)囊粋€(gè)主要優(yōu)勢(shì)是費(fèi)用低。大直徑、全負(fù)荷管道運(yùn)輸效率很高。管道提供的是地下的、全封閉的服務(wù)，因此，貨損、貨差率低。另外，因?yàn)楣艿肋\(yùn)輸速度很慢，還可以將管道作為倉(cāng)庫。也就是說，如果產(chǎn)品不是急用，緩慢的管理運(yùn)輸可以看作是免費(fèi)倉(cāng)庫存儲(chǔ)。管道的另一個(gè)服務(wù)優(yōu)勢(shì)是它的可靠性。管道運(yùn)輸基本上不受天氣影響，很少有機(jī)械故障。雖然運(yùn)輸時(shí)間長(zhǎng)，但能準(zhǔn)確估計(jì)交貨時(shí)間，減少了安全庫存的需要。管道運(yùn)輸也有相對(duì)劣勢(shì)。首先，管道線路是相對(duì)固定的，因此有地域靈活性或可達(dá)性的限制。其次，管道運(yùn)輸?shù)漠a(chǎn)品有局限性，并且只能提供單向服務(wù)。12PPT課件表6.2各種運(yùn)輸方式的成本和運(yùn)作績(jī)效的相對(duì)排名運(yùn)輸方式運(yùn)作特點(diǎn)成本①1=最高平均運(yùn)送時(shí)間②1=最快運(yùn)作時(shí)間的變化率安全性1=最高絕對(duì)值1=最低百分比③1=最低鐵路運(yùn)輸33435公路運(yùn)輸22324航空運(yùn)輸11153水上運(yùn)輸55542管道運(yùn)輸44211①每噸-公里成本②門到門的速度③絕對(duì)變化除以平均運(yùn)送時(shí)間的比率13PPT課件6.2.2綜合運(yùn)輸與特殊運(yùn)輸1．綜合運(yùn)輸

綜合運(yùn)輸是指在把貨物從出發(fā)地運(yùn)往目的地的過程中使用兩種或多種運(yùn)輸方式，又稱作多式聯(lián)運(yùn)。

（1）鐵路運(yùn)輸和卡車運(yùn)輸;（2）鐵路運(yùn)輸和水上運(yùn)輸;（3）鐵路運(yùn)輸和航空運(yùn)輸;（4）鐵路運(yùn)輸和管道運(yùn)輸;（5）卡車運(yùn)輸和航空運(yùn)輸;（6）卡車運(yùn)輸和水上運(yùn)輸;（7）卡車運(yùn)輸和管道運(yùn)輸;（8）水上運(yùn)輸和管道運(yùn)輸;（9）水上運(yùn)輸和航空運(yùn)輸;（10）航空運(yùn)輸和管道運(yùn)輸。14PPT課件（1）駝背運(yùn)輸（2）集裝箱運(yùn)輸2．特殊的承運(yùn)人形式（1）運(yùn)輸代理（2）快運(yùn)業(yè)務(wù)和快遞業(yè)務(wù)15PPT課件6.2.3自有運(yùn)輸優(yōu)點(diǎn)提升服務(wù)降低成本缺點(diǎn)空車回程（emptybackhaul）缺乏專業(yè)貨運(yùn)管理技術(shù)資金可用性貨物丟失和損壞16PPT課件6.2.4國(guó)際運(yùn)輸國(guó)際貨物運(yùn)輸方式主要有海洋運(yùn)輸、國(guó)際鐵路運(yùn)輸、航空運(yùn)輸、汽車運(yùn)輸和其他一些特殊的運(yùn)輸方式，如國(guó)際郵政運(yùn)輸、管道運(yùn)輸和集裝箱運(yùn)輸?shù)取ＹI賣雙方協(xié)定國(guó)際貿(mào)易術(shù)語解釋通則運(yùn)輸主要承運(yùn)人國(guó)內(nèi)承運(yùn)人貨物運(yùn)輸保險(xiǎn)中介人港口海關(guān)國(guó)外承運(yùn)人準(zhǔn)備訂貨生產(chǎn)挑選物品包裝辦理單證出口許可證銷售單據(jù)財(cái)務(wù)結(jié)算單據(jù)海關(guān)單證運(yùn)輸單據(jù)顧客圖6-2國(guó)際運(yùn)輸程序17PPT課件6.2.5運(yùn)輸定價(jià)1.運(yùn)輸管理中的定價(jià)（1）影響定價(jià)決策的因素許多人承運(yùn)人的定價(jià)決策受到商業(yè)環(huán)境的影響，包括客戶（市場(chǎng)）、政府、其他渠道成本和競(jìng)爭(zhēng)。（2）主要定價(jià)決策①對(duì)全新運(yùn)輸服務(wù)的定價(jià)。②運(yùn)輸服務(wù)價(jià)格變更。③應(yīng)對(duì)市場(chǎng)價(jià)格變化的定價(jià)。

（3）運(yùn)輸定價(jià)方法①按服務(wù)成本定價(jià)。②按服務(wù)價(jià)值定價(jià)。③綜合定價(jià)。

18PPT課件2.運(yùn)價(jià)結(jié)構(gòu)（1）線路定價(jià)

①按產(chǎn)品分類。②協(xié)議運(yùn)價(jià)。③按運(yùn)輸批量劃分（2）貨物運(yùn)輸其他收費(fèi)

①調(diào)車費(fèi)。②延滯費(fèi)。③貨（箱）落空損失費(fèi)。④道路阻塞停車費(fèi)。⑤車輛處置費(fèi)。⑥車輛通行費(fèi)。⑦運(yùn)輸變更手續(xù)費(fèi)。

19PPT課件6.3運(yùn)輸最優(yōu)化6.3.1運(yùn)輸合理化

影響物流運(yùn)輸合理化的因素很多，起決定作用的有五個(gè)方面，稱作合理運(yùn)輸?shù)摹拔逡亍薄?/p>

1．運(yùn)輸距離2．運(yùn)輸環(huán)節(jié)3．運(yùn)輸工具4．運(yùn)輸時(shí)間5．運(yùn)輸費(fèi)用20PPT課件不合理的運(yùn)輸主要有以下幾種表現(xiàn)形式：1．對(duì)流運(yùn)輸；2．迂回運(yùn)輸；3．過遠(yuǎn)運(yùn)輸；4．重復(fù)運(yùn)輸；5．無效運(yùn)輸；6．運(yùn)力選擇不當(dāng)21PPT課件6.3.2運(yùn)輸服務(wù)的選擇

運(yùn)輸成本、速度和一致性是決策者心目中最重要的運(yùn)輸服務(wù)要素，因此，這三項(xiàng)是運(yùn)輸服務(wù)選擇的基礎(chǔ)。運(yùn)輸方式的選擇即是戰(zhàn)術(shù)性決策又是操作性決策。與某個(gè)承運(yùn)商簽訂合同的決策屬于戰(zhàn)術(shù)性決策，而具體運(yùn)輸方式的選擇則是操作性決策。對(duì)于兩種決策來說，托運(yùn)人都必須權(quán)衡運(yùn)輸成本和庫存成本。一種運(yùn)費(fèi)最低的運(yùn)輸方式，并不一定使總運(yùn)輸成本最低。運(yùn)輸?shù)乃俣群涂煽啃詴?huì)影響托運(yùn)人和買方的庫存水平（訂貨庫存和安全庫存）以及他們之間的在途庫存水平。運(yùn)輸對(duì)庫存的影響有以下幾點(diǎn)：（1）較慢的運(yùn)輸模式會(huì)引起較大的中轉(zhuǎn)或運(yùn)輸庫存；（2）較大運(yùn)量的運(yùn)輸方式會(huì)出現(xiàn)訂單批量超過需求量的情況，從而增加庫存；（3）不可靠的運(yùn)輸模式會(huì)引起安全庫存的提高。在選擇運(yùn)輸方式時(shí)，就需要考慮庫存持有成本可能升高，而抵消運(yùn)輸服務(wù)成本降低的情況。因此，選擇運(yùn)輸方式時(shí)的最合理方案應(yīng)該是，既能滿足顧客需求，又使總成本最低的服務(wù)。22PPT課件例6.1

某箱包公司生產(chǎn)系列箱包產(chǎn)品，其分撥計(jì)劃是將生產(chǎn)的成品先存放在工廠，然后由工廠運(yùn)往公司自有的基層倉(cāng)庫。目前，公司使用鐵路運(yùn)輸將工廠的成品運(yùn)往倉(cāng)庫。鐵路運(yùn)輸?shù)钠骄鶗r(shí)間為T=21天，每個(gè)存儲(chǔ)點(diǎn)平均儲(chǔ)存100000件箱包，箱包的平均價(jià)值C=30元，庫存成本I=30%每年。公司希望選擇使總成本最小的運(yùn)輸方式。據(jù)估計(jì)，運(yùn)輸時(shí)間從目前的21天每減少一天，平均庫存水平可以減少1%。每年倉(cāng)庫賣出D=700000件箱包。公司可以利用以下運(yùn)輸服務(wù)：

其中采購(gòu)成本和運(yùn)輸時(shí)間的變化忽略不計(jì)。運(yùn)輸服務(wù)方式運(yùn)輸費(fèi)率(元/單位)門到門運(yùn)送時(shí)間T（天）每年運(yùn)輸批次鐵路運(yùn)輸0.12110卡車運(yùn)輸0.2520航空運(yùn)輸1.424023PPT課件解答：在選擇運(yùn)輸方式時(shí)要考慮總成本，包括運(yùn)輸成本，不同運(yùn)輸方式的運(yùn)輸成本不同，各種運(yùn)輸方式下的運(yùn)輸成本為年運(yùn)輸量與運(yùn)輸費(fèi)率的乘積。在途貨物的庫存成本，不同運(yùn)輸方式將影響貨物的在途時(shí)間，在途庫存的持有成本不同。在途庫存成本為I×C×D×T/365分撥渠道兩端的庫存成本。分撥渠道兩端的平均庫存大約是Q/2，其中Q是運(yùn)輸批量。每單位貨物的庫存成本為I×C，但產(chǎn)品價(jià)值C在分撥渠道的不同地點(diǎn)是不同的。在工廠，C是產(chǎn)品的出廠價(jià)值，在倉(cāng)庫，C是產(chǎn)品的出廠價(jià)值加上運(yùn)輸費(fèi)率。計(jì)算各種運(yùn)輸方式下的總成本:24PPT課件成本類型鐵路運(yùn)輸卡車運(yùn)輸航空運(yùn)輸運(yùn)輸成本0.1×700000=700000.2×700000=1400001.4×700000=980000在途庫存0.3×30×700000×21/365=3624660.3×30×700000×5/365=863010.3×30×700000×2/365=34521工廠庫存0.3×30×70000/2=6300000.3×30×35000/2×0.84=2646000.3×30×17500/2×0.81=127575倉(cāng)庫庫存0.3×30.1×70000/2=3160500.3×30.2×35000/2×0.84=1331820.3×30.4×17500/2×0.81=64638合計(jì)13785166240831206734

由上表可以看出，雖然采用鐵路運(yùn)輸時(shí)的運(yùn)輸費(fèi)率最低，采用航空運(yùn)輸時(shí)的庫存成本最低，但卡車運(yùn)輸?shù)目偝杀咀畹汀Ｈ绻褂每ㄜ囘\(yùn)輸，運(yùn)輸時(shí)間減少到5天，兩個(gè)端點(diǎn)的庫存水平比使用鐵路運(yùn)輸減少50%。25PPT課件6.3.3運(yùn)輸路線的選擇1．起、止點(diǎn)不同的單一路徑規(guī)劃

這類路徑規(guī)劃問題稱為最短路問題。最短路徑問題是線路優(yōu)化模型理論中最為基礎(chǔ)的問題之一。問題描述：假設(shè)有一n個(gè)節(jié)點(diǎn)和m條弧的連通圖G（Vn,Em),并且圖中的每條?。╥,j)都有一個(gè)長(zhǎng)度cij(或者費(fèi)用cij)，則最短路徑問題為：在連通圖中找到一條從節(jié)點(diǎn)1到節(jié)點(diǎn)n距離最短（或費(fèi)用最低）的路徑。求解此類最短路徑問題，主要有以下幾種算法：（1）Dijkstra算法；（2）逐次逼近法；（3）Floyd算法。下面通過一個(gè)實(shí)例對(duì)該類問題進(jìn)行說明。26PPT課件例6.2

某運(yùn)輸公司簽訂了一項(xiàng)運(yùn)輸合同，要把A市的一批貨物運(yùn)送到B市，該公司根據(jù)這兩個(gè)城市之間可選擇的行車路線的地圖繪制了如圖所示的公路網(wǎng)絡(luò)。圖中，圓圈也稱節(jié)點(diǎn)，代表起點(diǎn)、目的地和與行車路線相交的其他城市。鏈代表兩個(gè)結(jié)點(diǎn)之間的公路，每一條公路都標(biāo)明運(yùn)輸里程。A市B市圖6-3A、B兩地之間運(yùn)輸路線示意圖

可以看出，從A市出發(fā)到達(dá)B市，可以有很多條路線可以選擇。但是如何選擇運(yùn)輸路線，才能使總路程的長(zhǎng)度最短？這就是運(yùn)輸規(guī)劃中的最短路問題。27PPT課件解答：最短路的計(jì)算方法（1）找出第n個(gè)距起點(diǎn)最近的節(jié)點(diǎn)。對(duì)n=1,2,…，重復(fù)此過程，直到所找出的最近節(jié)點(diǎn)是終點(diǎn)。（2）在前面的迭代過程中找出（n-1）個(gè)距起點(diǎn)最近的節(jié)點(diǎn)，及其距起點(diǎn)最短的中徑和距離，這些節(jié)點(diǎn)和起點(diǎn)統(tǒng)稱為已解的節(jié)點(diǎn)，其余的稱為未解節(jié)點(diǎn)。（3）每個(gè)已解的節(jié)點(diǎn)和一個(gè)或多外未解的節(jié)點(diǎn)相連接，就可以得出一個(gè)候選點(diǎn)—連接距離最短的未解點(diǎn)。如果有多個(gè)距離相等的最短連接，則有多個(gè)候選點(diǎn)。（4）將每個(gè)已解節(jié)點(diǎn)與其候選點(diǎn)之間的距離累加到該已解節(jié)點(diǎn)與起點(diǎn)之間最短路徑的距離上，所得出的總距離最短的候選點(diǎn)就是第n個(gè)最近的節(jié)點(diǎn)，其最短路徑就是得出該距離的路徑（若多個(gè)候選點(diǎn)都得出相等的最短距離，則都是已解節(jié)點(diǎn)）。28PPT課件步驟直接連接到未解節(jié)點(diǎn)的已解節(jié)點(diǎn)與其直接連接的未解結(jié)點(diǎn)相關(guān)總成本第n個(gè)最近解點(diǎ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最短路徑法的計(jì)算步驟表通過上表的計(jì)算可知，最短路徑為1-2-5-4-3-6，最短距離為12。最短路徑法適合利用計(jì)算機(jī)進(jìn)行求解，把運(yùn)輸網(wǎng)絡(luò)中的鏈和節(jié)點(diǎn)的資料都存入數(shù)據(jù)庫中，選好起點(diǎn)和終點(diǎn)后，計(jì)算機(jī)可以很快就算出最短路徑。29PPT課件2．多個(gè)起、止點(diǎn)的路徑規(guī)劃當(dāng)有多個(gè)貨源和多個(gè)目的地時(shí)，就需要指定目的地的供貨地，同時(shí)要找到供貨地、目的地之間的最佳路徑。例6.3

某公司下屬三個(gè)倉(cāng)庫，供應(yīng)四個(gè)客戶的需要，三個(gè)倉(cāng)庫的供應(yīng)量和四個(gè)客戶的需求量，以及由各倉(cāng)庫到各客戶的運(yùn)輸單價(jià)如下表所示。求運(yùn)輸費(fèi)用最少的運(yùn)輸方案。

銷地客戶1客戶2客戶3客戶4供應(yīng)量運(yùn)價(jià)產(chǎn)地倉(cāng)庫A311310700倉(cāng)庫B1928400倉(cāng)庫C74105900需求量300600500600200030PPT課件表上做業(yè)法，該方法適合于對(duì)相對(duì)簡(jiǎn)單的問題進(jìn)行求解，求解過程方便直觀，而且由于計(jì)算量不大，可以用手工直接完成。利用表上作業(yè)法有兩個(gè)基本步驟：（1）確定初始調(diào)運(yùn)方案最小元素法是按運(yùn)價(jià)表依次挑選運(yùn)費(fèi)小的供-需點(diǎn)組合，盡量?jī)?yōu)先安排運(yùn)費(fèi)最低組合的方法。3113101928734105

銷地客戶1客戶2客戶3客戶4供應(yīng)量運(yùn)價(jià)產(chǎn)地倉(cāng)庫A400300700倉(cāng)庫B300100400倉(cāng)庫C600300900需求量300600500600表6.4初始調(diào)運(yùn)方案31PPT課件（2）初始方案的檢驗(yàn)最優(yōu)方案的數(shù)字特征—檢驗(yàn)數(shù)：閉回路：從理論上講，對(duì)于表上作業(yè)法的初始方案來說，從調(diào)運(yùn)方案表上的一個(gè)空格出發(fā)，存在一條且僅存在一條以該空格（用xij表示）為起點(diǎn)，以其他填有數(shù)字的點(diǎn)為其他頂點(diǎn)的閉合回路，簡(jiǎn)稱閉回路。這個(gè)閉回路有以下性質(zhì)：每個(gè)頂點(diǎn)都是轉(zhuǎn)角點(diǎn)；閉合回路是一條封閉折線，每一條邊都是水平或垂直的；每一行（列）若有閉合回路的頂點(diǎn)，則必有兩個(gè)。只有從空格出發(fā)，其余各轉(zhuǎn)角點(diǎn)所對(duì)應(yīng)的方格內(nèi)均填寫數(shù)字時(shí)，所構(gòu)成的閉合回路才是我們所說的閉回路；另外，過任一空格的閉合回路不僅是存在的，而且是唯一的。32PPT課件

銷地客戶1客戶2客戶3客戶4供應(yīng)量產(chǎn)地倉(cāng)庫A400300700倉(cāng)庫B300100400倉(cāng)庫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)運(yùn)方案內(nèi)的每個(gè)空格所形成的閉回路上，作單位物資的運(yùn)量調(diào)整，總可以計(jì)算出相應(yīng)的運(yùn)費(fèi)是增加還是減少。我們把所計(jì)算出來的每條閉回路上調(diào)整單位運(yùn)量而使運(yùn)輸費(fèi)用發(fā)生變化的增減值，稱其為檢驗(yàn)數(shù)。如果檢驗(yàn)數(shù)小于0，表示在該空格的閉回路上調(diào)整運(yùn)量會(huì)使運(yùn)費(fèi)減少；相反，如果檢驗(yàn)數(shù)大于0，則會(huì)使運(yùn)費(fèi)增加。表6.5初始調(diào)運(yùn)方案33PPT課件用閉回路法求檢驗(yàn)數(shù)時(shí)，需給每一空格找一條閉回路。當(dāng)產(chǎn)銷點(diǎn)很多時(shí)，這種計(jì)算很繁，可以用較為簡(jiǎn)便的方法“位勢(shì)法”求解。設(shè)u1,u2,…,um；v1,v2,…,vn，是對(duì)應(yīng)運(yùn)輸問題的m+n個(gè)約束條件的對(duì)偶變量。在初始調(diào)運(yùn)方案中x13,x14,x21,x23,x32,x34是基變量，這時(shí)對(duì)應(yīng)的檢驗(yàn)數(shù)是：基變量檢驗(yàn)數(shù)x21c21-(u2+v1)=0設(shè)v1=0，并且c21=1所以u(píng)2=1x23c23-(u2+v3)=02-(u2+v3)=0x13c13-(u1+v3)=03-(u1+v3)=0x14c14-(u1+v4)=010-(u1+v4)=0x34c34-(u3+v4)=05-(u3+v4)=0x22c22-(u2+v2)=04-(u2+v2)=034PPT課件通過這些方程可以求得u1=2u2=1u3=-3v1=0v2=7v3=1v4=8在初始解調(diào)運(yùn)方案中增加一行一列，在列中填入ui,在行中填入vi。接下來，按σij=cij-(ui+vj)計(jì)算所有空格的檢驗(yàn)數(shù)。完成后的表格見表6.6。3113101928734105

銷地客戶1客戶2客戶3客戶4ui運(yùn)價(jià)產(chǎn)地倉(cāng)庫A12002倉(cāng)庫B010-11倉(cāng)庫C100120-3vi0718表6.6檢驗(yàn)數(shù)表格35PPT課件（3）方案調(diào)整判定一個(gè)初始調(diào)運(yùn)方案不是最優(yōu)調(diào)運(yùn)方案的標(biāo)準(zhǔn)，是在檢驗(yàn)數(shù)表格中出現(xiàn)負(fù)值的檢驗(yàn)數(shù)。如果檢驗(yàn)數(shù)的負(fù)值不止個(gè)時(shí)，一般選擇負(fù)檢驗(yàn)數(shù)絕對(duì)值最大的空格作為具體調(diào)整對(duì)象。從表6.6可以發(fā)現(xiàn)，單元格x24的檢驗(yàn)數(shù)是負(fù)數(shù)，因此對(duì)其進(jìn)行調(diào)整，具體過程如表6.7所示。x13x14x13400+100=500x14300-100=200x23100-100=0x240+100=100表6.7調(diào)動(dòng)方案調(diào)整表

從單元格x24開始，沿閉回路在各奇數(shù)次轉(zhuǎn)角點(diǎn)中挑選運(yùn)量的最小數(shù)值作為調(diào)整量。在此將x23單元格的100作為調(diào)整量，將亮個(gè)數(shù)填入單元格x24內(nèi)，同時(shí)調(diào)整該閉回路中其他轉(zhuǎn)角點(diǎn)上的運(yùn)量，使各行、列保持原來的供需平衡，這樣注得到一個(gè)新的調(diào)運(yùn)方案，如表6.7所示。36PPT課件3113101928734105

銷地客戶1客戶2客戶3客戶4供應(yīng)量

運(yùn)價(jià)產(chǎn)地倉(cāng)庫A500200700倉(cāng)庫B300100400倉(cāng)庫C600300900需求量300600500600表6.7調(diào)整后的方案按新方案計(jì)算調(diào)運(yùn)物資的運(yùn)輸費(fèi)用為：3×500+10×200+8×100+4×600+5×300=8500元新方案是否最優(yōu)方案，還需再進(jìn)行檢驗(yàn)。經(jīng)計(jì)算，該新方案的所有檢驗(yàn)數(shù)都是非負(fù)數(shù)，說明該方案已經(jīng)是最優(yōu)方案了。37PPT課件3．起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃物流管理人員經(jīng)常會(huì)遇到起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃問題。例如，從某倉(cāng)庫送貨到零售店然后返回的路線；從零售店到客戶地點(diǎn)配送的路線規(guī)劃。起點(diǎn)和終點(diǎn)重合的路徑問題一般被稱為“流動(dòng)推銷員”問題（TSP,TravelingSalesmanProblem），是運(yùn)籌學(xué)、圖論和組合優(yōu)化中的典型問題。

TSP問題一般描述如下：一個(gè)旅行者從出發(fā)地出發(fā)，經(jīng)過所有要到達(dá)的城市后，返回到出發(fā)地，要求合理安排其旅行路線，使得總旅行距離（或旅行費(fèi)用、旅行時(shí)間等）最短。人們已經(jīng)提出不少方法來解決這類問題。如果某個(gè)問題中包含很多個(gè)點(diǎn)，要找到最優(yōu)路徑是不切實(shí)際的，因?yàn)樵S多現(xiàn)實(shí)問題的規(guī)模太大。啟發(fā)式算法是求解這類問題的好辦法。38PPT課件

車輛路線安排問題（VRP,VehicleRoutingProblem）是指對(duì)物流配送的車輛進(jìn)行優(yōu)化調(diào)度。該問題一般可以描述如下：對(duì)一系列裝貨點(diǎn)或（和）卸貨點(diǎn)，組織適當(dāng)合理的行車路線，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量、數(shù)目限制、車輛行駛里程、時(shí)間限制等）下，達(dá)到一定的目標(biāo)（如最短路程、最小費(fèi)用、最短時(shí)間、最少車輛等）。該問題涉及了多輛交通工具的服務(wù)對(duì)象的選擇和路徑（服務(wù)順序）確定兩方面的問題。

VRP問題是組合優(yōu)化領(lǐng)域著名的NP難題之一，求解方法一般相當(dāng)復(fù)雜，通常的做法是應(yīng)用相關(guān)技術(shù)問題分解或者轉(zhuǎn)化為一個(gè)或多個(gè)已經(jīng)研究過的基本問題（如旅行商問題、指派問題、最短路問題等），再使用相對(duì)比較成熟的基本理論和方法進(jìn)行求解。6.3.4車輛路線安排39PPT課件運(yùn)用VRP模型對(duì)實(shí)際問題進(jìn)行研究時(shí)，一般需要考慮以下幾個(gè)方面的問題：（1）倉(cāng)庫。倉(cāng)庫的級(jí)數(shù)，每級(jí)倉(cāng)庫的數(shù)量、地點(diǎn)和規(guī)模。（2）車輛。車輛的型號(hào)和數(shù)量，每種車輛的容積和運(yùn)作費(fèi)用，出發(fā)時(shí)間和返回時(shí)間，司機(jī)休息時(shí)間，最大的里程和時(shí)間限制。（3）時(shí)間窗口。由于各處的工作時(shí)間不同，每個(gè)站點(diǎn)每天只允許在特定的時(shí)間內(nèi)取貨和/或送貨。（4）顧客。顧客需求，裝載、卸載，所處的地理位置，分離需求，優(yōu)先等級(jí)。（5）道路信息。車流密度，道路交通費(fèi)用，距離或時(shí)間屬性。（6）貨物信息。貨物的種類多少，兼容性，貨物的保鮮。（7）運(yùn)輸規(guī)章。工人每天的工作時(shí)間，車輛的周期維護(hù)。40PPT課件（1）安排車輛負(fù)責(zé)相互距離最接近的站點(diǎn)的貨物運(yùn)輸。（2）安排車輛各日途經(jīng)站點(diǎn)時(shí)，應(yīng)注意使站點(diǎn)群更加緊湊。如果一周內(nèi)各日服務(wù)的站點(diǎn)不同，就應(yīng)該對(duì)一周內(nèi)每天的路線和時(shí)刻表問題分別進(jìn)行站點(diǎn)群劃分。各日站點(diǎn)群的劃分應(yīng)避免重疊。（3）從距倉(cāng)庫最遠(yuǎn)的站點(diǎn)開始設(shè)計(jì)路線（4）卡車的行車路線應(yīng)呈水滴狀。（5）盡可能使用最大的車輛進(jìn)行運(yùn)送，這樣設(shè)計(jì)出的路線是最有效的。（6）取貨、送貨應(yīng)該混合安排，不應(yīng)該在完成全部送貨任務(wù)之后再取貨。（7）對(duì)過于遙遠(yuǎn)而無法歸入群落的站點(diǎn)，可以采用其它配送方式。（8）避免時(shí)間窗口過短。簡(jiǎn)化的原則：41PPT課件1．掃描法路線設(shè)計(jì)中的掃描法很簡(jiǎn)單，即使問題規(guī)模很大，也可以通過手工計(jì)算得出結(jié)果。掃描法可闡述如下：（1）在地圖或方格圖中確定所有站點(diǎn)（含倉(cāng)庫）的位置。（2）自倉(cāng)庫始沿任一方向向外劃一條直線。沿順時(shí)針或逆時(shí)針方向旋轉(zhuǎn)該直線直到與某站點(diǎn)相交?？紤]：如果在某線路上增加該站點(diǎn)，是否會(huì)超過車輛的載貨能力？如果沒有，繼續(xù)旋轉(zhuǎn)直線，直到與下一個(gè)站點(diǎn)相交。再次計(jì)算累計(jì)貨運(yùn)量是否超過車輛的運(yùn)載能力（先使用最大的車輛）。如果超過，就剔除最后的那個(gè)站點(diǎn)，并確定路線。隨后，從不包含在上一條路線中的站點(diǎn)開始，繼續(xù)旋轉(zhuǎn)直線以尋找新路線。繼續(xù)該過程直到所有的站點(diǎn)都被安排到路線中。（3）排定各路線上每個(gè)站點(diǎn)的順序使行車距離最短。排序時(shí)可以使用“水滴”法或求解“流動(dòng)推銷員”問題的任何算法。42PPT課件例6.4某公司用廂式貨車從貨主處取貨，圖6-4(a)是一天的取貨量，單位是件。廂式貨車的載貨量是10000件。完成所有取貨任務(wù)需一天時(shí)間。公司需要多少條運(yùn)輸路線（即多少部車），每條路線上應(yīng)該經(jīng)過哪些站點(diǎn)，每條路線上的站點(diǎn)怎樣排序。