線路規(guī)劃及成本控制

1、唐龍政 主要內(nèi)容預(yù)備知識(shí) 運(yùn)輸優(yōu)化與成本控制基本理論第一節(jié) 物流運(yùn)輸服務(wù)選擇決策第二節(jié) 貨物運(yùn)輸調(diào)配決策第三節(jié) 物流運(yùn)輸線路的優(yōu)化第四節(jié) 行車路線及時(shí)刻表的制訂第五節(jié) 運(yùn)輸工具與貨載的最優(yōu)分配2預(yù)備知識(shí)一、物流運(yùn)輸組織、規(guī)劃的基本原理 二、物流運(yùn)輸?shù)馁|(zhì)量 三、物流運(yùn)輸?shù)暮侠砘?（一）規(guī)模經(jīng)濟(jì)（economy of scale） 思考：規(guī)模經(jīng)濟(jì)存在的原因？有關(guān)的固定費(fèi)用可以按整批貨物的質(zhì)量分?jǐn)偂?（二）距離經(jīng)濟(jì)（economy of distance） 指每單位距離的運(yùn)輸成本隨距離的增加而減少。距離越長(zhǎng)，固定費(fèi)用分?jǐn)偤蟮闹翟叫。沟妹繂挝痪嚯x支付的費(fèi)用越小。距離經(jīng)濟(jì)的合理性類似于規(guī)模經(jīng)濟(jì)，尤其體

2、現(xiàn)在運(yùn)輸裝卸費(fèi)用上的分?jǐn)偂?5（一）貨運(yùn)質(zhì)量事故分類1、重大事故：貨損金額在3000元以上的運(yùn)輸質(zhì)量事故，以及經(jīng)省級(jí)有關(guān)部門鑒定為珍貴、尖端、保密物品在運(yùn)輸過程中發(fā)生滅失、損壞的事故。2、大事故：貨損金額在500-3000元的貨運(yùn)質(zhì)量事故。3、一般事故：貨損金額在50-500元的貨運(yùn)質(zhì)量事故。4、小事故：貨損金額在20-50元的貨運(yùn)質(zhì)量事故。 貨損金額在20元以下的貨運(yùn)質(zhì)量事故，不作為事故統(tǒng)計(jì)上報(bào)，但企業(yè)要作為內(nèi)部記錄和處理。6物流運(yùn)輸?shù)馁|(zhì)量（二）貨運(yùn)質(zhì)量事故考核指標(biāo) 6 61 10 0完完成成貨貨運(yùn)運(yùn)周周轉(zhuǎn)轉(zhuǎn)量量貨貨運(yùn)運(yùn)質(zhì)質(zhì)量量事事故故次次數(shù)數(shù)貨貨運(yùn)運(yùn)質(zhì)質(zhì)量量事事故故頻頻率率7物流運(yùn)輸?shù)馁|(zhì)量

3、（二）貨運(yùn)質(zhì)量事故考核指標(biāo)100%貨運(yùn)總噸數(shù)貨損噸數(shù)貨損率100%貨運(yùn)總噸數(shù)貨差噸數(shù)貨差率8物流運(yùn)輸?shù)馁|(zhì)量（二）貨運(yùn)質(zhì)量事故考核指標(biāo)100%100%貨運(yùn)總收入金額貨運(yùn)總收入金額質(zhì)量事故賠償金額質(zhì)量事故賠償金額貨運(yùn)質(zhì)量事故賠償率貨運(yùn)質(zhì)量事故賠償率100%100%完成總貨運(yùn)量噸數(shù)完成總貨運(yùn)量噸數(shù)的貨運(yùn)量噸數(shù)的貨運(yùn)量噸數(shù)按托運(yùn)要求的時(shí)間完成按托運(yùn)要求的時(shí)間完成完成運(yùn)量及時(shí)率完成運(yùn)量及時(shí)率9物流運(yùn)輸?shù)暮侠砘?0（一）合理運(yùn)輸?shù)母拍睿ǘ┎缓侠磉\(yùn)輸?shù)谋憩F(xiàn)形式（三）運(yùn)輸合理化的措施物流運(yùn)輸?shù)暮侠砘ㄒ唬┖侠磉\(yùn)輸?shù)母拍?合理運(yùn)輸（Reasonable Transportation）： 11物流運(yùn)輸?shù)暮侠砘?/p>

4、二）不合理運(yùn)輸?shù)谋憩F(xiàn)形式12對(duì)流運(yùn)輸迂回運(yùn)輸重復(fù)運(yùn)輸?shù)沽鬟\(yùn)輸過遠(yuǎn)運(yùn)輸運(yùn)力選擇不當(dāng)無效運(yùn)輸表現(xiàn)形式13甲乙丙丁對(duì)流運(yùn)輸1、對(duì)流運(yùn)輸是指同類的或可以互相代替的貨物的相向運(yùn)輸，它是不合理運(yùn)輸最突出、最普遍的一種。主要有兩種表現(xiàn)形式：（1）明顯對(duì)流（2）是隱蔽對(duì)流派生形式：倒流運(yùn)輸，即同一批貨物或同批中的一部分貨物，由發(fā)運(yùn)站至目的站后，又從目的站往發(fā)運(yùn)站方向運(yùn)輸表現(xiàn)形式14迂回運(yùn)輸迂回運(yùn)輸不經(jīng)過最短路徑的繞道運(yùn)輸，“近路不走走遠(yuǎn)路”。表現(xiàn)形式15甲乙丙3、重復(fù)運(yùn)輸-出現(xiàn)不必要的中轉(zhuǎn) 指同一批貨物由產(chǎn)地運(yùn)抵目的地，沒經(jīng)任何加工和必要的作業(yè)，也不是為聯(lián)運(yùn)及中轉(zhuǎn)需要，又重新裝運(yùn)到別處的現(xiàn)象。 重復(fù)運(yùn)輸是因物

5、流倉庫設(shè)置不當(dāng)或計(jì)劃不周使其在中途卸下，導(dǎo)致增加運(yùn)輸環(huán)節(jié)、浪費(fèi)運(yùn)輸設(shè)備和裝卸搬運(yùn)能力，延長(zhǎng)運(yùn)輸時(shí)間的不合理運(yùn)輸方式。表現(xiàn)形式16甲乙丙4、倒流運(yùn)輸 指同一批貨物或同一批中的部分貨物，由始發(fā)站運(yùn)往目的站，又從目的站往始發(fā)站方向運(yùn)輸。表現(xiàn)形式17過遠(yuǎn)運(yùn)輸5、過遠(yuǎn)運(yùn)輸 指凡是可以從附近取得所需物資的供應(yīng)而不去就近組織，相反卻從相反的地方運(yùn)來，從而造成不必要的浪費(fèi)，即在相同條件下舍近求遠(yuǎn)的物品運(yùn)輸方式。未考慮各種運(yùn)輸工具的經(jīng)濟(jì)技術(shù)特點(diǎn)而進(jìn)行不適當(dāng)?shù)倪x擇造成的不合理。常見的有以下幾種形式：（1）違反水陸分工使用，棄水走陸的運(yùn)輸。（2）鐵路短途運(yùn)輸。（3）水運(yùn)的過近運(yùn)輸。187、運(yùn)力選擇不當(dāng)三、物流運(yùn)輸?shù)?/p>

6、合理化（三）運(yùn)輸合理化的措施19第一節(jié):物流運(yùn)輸服務(wù)選擇決策20一、物流運(yùn)輸方式選擇的原則（一）安全性原則（二）及時(shí)性原則（三）準(zhǔn)確性原則（四）經(jīng)濟(jì)性原則21二、基于物流總成本比較的運(yùn)輸方式選擇22【例7-1】某公司欲將產(chǎn)品從位置A的工廠運(yùn)往位置B的公司自有倉庫，年運(yùn)量D=700000件，年存貨成本為產(chǎn)品價(jià)格的30%。公司希望選擇使總成本最小的運(yùn)輸方式。據(jù)估計(jì)，運(yùn)輸時(shí)間每減少一天，平均庫存成本可以減少1%。各種運(yùn)輸服務(wù)方式的有關(guān)參數(shù)見表7-1。 二、基于物流總成本比較的運(yùn)輸方式選擇【例7-1】基于運(yùn)輸成本與庫存成本的總成本分析方法：23成本類型成本類型計(jì)算公式計(jì)算公式鐵路運(yùn)輸鐵路運(yùn)輸馱背運(yùn)輸馱

7、背運(yùn)輸公路運(yùn)輸公路運(yùn)輸航空運(yùn)輸航空運(yùn)輸運(yùn)輸成本運(yùn)輸成本R D70 000105 000140 000980 000在途庫存在途庫存ICDT/365362 466241 64486 30134 521工廠存貨工廠存貨ICQ/2900 000418 500378 000182 250倉庫存貨倉庫存貨I(C+R)Q/2903 000420 593380 520190 755總成本總成本 2 235 4661 185 737984 8211387526三、承運(yùn)人的選擇與評(píng)價(jià)24三、承運(yùn)人的選擇與評(píng)價(jià)假設(shè)一共有N個(gè)評(píng)價(jià)指標(biāo)。對(duì)于某備選承運(yùn)商來說，客戶可通過統(tǒng)計(jì)分析、專家打分或其他信息獲取途徑，得出該承運(yùn)

8、商的N個(gè)指標(biāo)（取值）得分情況，分別用X1、X2，.Xn表示。 則，該承運(yùn)商的綜合得分為： 25專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善26表7-3 承運(yùn)商評(píng)估報(bào)告示例最高分評(píng)價(jià)標(biāo)準(zhǔn)承運(yùn)人分?jǐn)?shù)備注13滿足接貨時(shí)間表1313滿足搬運(yùn)109運(yùn)輸時(shí)間910運(yùn)輸時(shí)間一致性77費(fèi)率53附加費(fèi)1高的住宅搬運(yùn)5運(yùn)營(yíng)比率396.5增長(zhǎng)4收益性33索賠頻率33索賠解決310賬單錯(cuò)誤79跟蹤能力711設(shè)備可用性l無平臺(tái)裝貨卡車100總分72第二節(jié) 貨物運(yùn)輸調(diào)配決策一、多起訖點(diǎn)間的直達(dá)運(yùn)輸二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配三、圖上作業(yè)法27表上作業(yè)法一、多起訖點(diǎn)間的直達(dá)運(yùn)輸對(duì)于多點(diǎn)間直達(dá)運(yùn)輸問題，描述如下：28 a1 a2 am

9、 b1 b2 bn Cij Xij 供供 應(yīng)應(yīng) 地地 需需 求求 地地 圖7-1 多點(diǎn)之間的物資運(yùn)輸調(diào)撥問題示意圖一、多起訖點(diǎn)間的直達(dá)運(yùn)輸 銷地銷地產(chǎn)地產(chǎn)地B1B2Bn產(chǎn)量A A1 1x x1111x x1212x x1n1na a1 1A A2 2x x2121x x2222x x2n2na a2 2A Am mx xm1m1x xm2m2x xmnmna am m銷量銷量b b1 1b b2 2b bn n29一、多起訖點(diǎn)間的直達(dá)運(yùn)輸（一）產(chǎn)銷平衡的運(yùn)輸問題（ai= bj）1產(chǎn)銷平衡運(yùn)輸問題數(shù)學(xué)模型30 一、多起訖點(diǎn)間的直達(dá)運(yùn)輸（二）運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)31專注專業(yè)、持續(xù)改善專注專業(yè)、持

10、續(xù)改善32 一、多起訖點(diǎn)間的直達(dá)運(yùn)輸專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善33 min f = 6x11+4x12+6x13+6x21+5x22+5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij0 (i=1,2；j=1,2,3）一、多起訖點(diǎn)間的直達(dá)運(yùn)輸（二）運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善34 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 一

11、、多起訖點(diǎn)間的直達(dá)運(yùn)輸（二）運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善35模型系數(shù)矩陣特征一、多起訖點(diǎn)間的直達(dá)運(yùn)輸（二）運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)、 西北角法 最小元素法 沃格爾法（vogel）2、解的最優(yōu)性檢驗(yàn)（判斷是否為最優(yōu)調(diào)運(yùn)方案） 閉回路法 位勢(shì)法（對(duì)偶變量法）3、解的改進(jìn)4、重復(fù)2、3兩步，經(jīng)有限次調(diào)整，得到最優(yōu)解。 36一、多起訖點(diǎn)間的直達(dá)運(yùn)輸（三）用表上作業(yè)發(fā)求解運(yùn)輸問題的基本步驟 銷地銷地產(chǎn)地產(chǎn)地B B1 1B B2 2B B3 3B B4 4產(chǎn)量A A1 11616A A2 21010A A3 32222銷量銷量8 814141212141448374124311

12、1028511961、確定初始基本可行解西北角法8864814（三）用表上作業(yè)發(fā)求解運(yùn)輸問題的基本步驟一、多起訖點(diǎn)間的直達(dá)運(yùn)輸 銷地銷地產(chǎn)地產(chǎn)地B B1 1B B2 2B B3 3B B4 4產(chǎn)量A A1 11616A A2 21010A A3 32222銷量銷量8 8141412121414483841243111028511961、西北角法得到的初始調(diào)運(yùn)方案為：8864814總運(yùn)輸費(fèi)用為：372（怎么計(jì)算？）（三）用表上作業(yè)發(fā)求解運(yùn)輸問題的基本步驟一、多起訖點(diǎn)間的直達(dá)運(yùn)輸 銷地銷地產(chǎn)地產(chǎn)地B B1 1B B2 2B B3 3B B4 4產(chǎn)量A A1 11616A A2 21010A A3

13、32222銷量銷量8 81414121214144839 銷地銷地產(chǎn)地產(chǎn)地B B1 1B B2 2B B3 3B B4 4產(chǎn)量A A1 11616A A2 21010A A3 32222銷量銷量8 814141212141448401、確定初始基本可行解沃格爾（Vogel）法（三）用表上作業(yè)發(fā)求解運(yùn)輸問題的基本步驟一、多起訖點(diǎn)間的直達(dá)運(yùn)輸 銷地銷地產(chǎn)地產(chǎn)地B B1 1B B2 2B B3 3B B4 4產(chǎn)量行罰數(shù)A A1 11616A A2 21010A A3 32222銷量銷量8 814141212141448列罰數(shù) 銷地銷地產(chǎn)地產(chǎn)地B B1 1B B2 2B B3 3B B4 4產(chǎn)量A A

14、1 11616A A2 21010A A3 32222銷量銷量8 8141412121414484243 銷地銷地產(chǎn)地產(chǎn)地B B1 1B B2 2B B3 3B B4 4產(chǎn)量A A1 11616A A2 21010A A3 32222銷量銷量8 814141212141448 2、解的最優(yōu)性檢驗(yàn)閉回路法44 銷地銷地產(chǎn)地產(chǎn)地B B1 1B B2 2B B3 3B B4 4產(chǎn)量A A1 11 12 21616A A2 21 1- 1- 11010A A3 3101012122222銷量銷量8 814141212141448檢驗(yàn)數(shù)計(jì)算結(jié)果（三）用表上作業(yè)發(fā)求解運(yùn)輸問題的基本步驟一、多起訖點(diǎn)間的直達(dá)

15、運(yùn)輸 2、解的最優(yōu)性檢驗(yàn)位勢(shì)(對(duì)偶變量)法45 銷地銷地產(chǎn)地產(chǎn)地B B1 1B B2 2B B3 3B B4 4產(chǎn)量uiA A1 11616 u1A A2 21010 u2A A3 32222 u3銷量銷量8 814141212141448vjv1v2v3v4（三）用表上作業(yè)發(fā)求解運(yùn)輸問題的基本步驟一、多起訖點(diǎn)間的直達(dá)運(yùn)輸 2、解的最優(yōu)性檢驗(yàn)位勢(shì)(對(duì)偶變量)法46 銷地銷地產(chǎn)地產(chǎn)地B B1 1B B2 2B B3 3B B4 4產(chǎn)量uiA A1 11616 u1( )A A2 21010 u2( )A A3 32222 u3 銷量銷量8 81414121214144848vjv1 ( )v2

16、( )v3 ( )v4 ()（三）用表上作業(yè)發(fā)求解運(yùn)輸問題的基本步驟一、多起訖點(diǎn)間的直達(dá)運(yùn)輸47 銷地銷地產(chǎn)地產(chǎn)地B B1 1B B2 2B B3 3B B4 4產(chǎn)量A A1 11616A A2 21010A A3 32222銷量銷量8 814141212141448練習(xí)：求解如下運(yùn)輸問題48 銷地銷地產(chǎn)地產(chǎn)地B B1 1B B2 2B B3 3B B4 4產(chǎn)量A A1 18 8A A2 25 5A A3 35 5銷量銷量4 43 35 56 6要求：用三種方法求出初始方案，用兩種方法對(duì)最小元素法得到的初始方案進(jìn)行檢驗(yàn)，如果初始方案不是最優(yōu)，請(qǐng)調(diào)整到最優(yōu)。1總產(chǎn)量大于總銷量：則增加一個(gè)假想的銷

17、地Bn+1，其銷量為：2總銷量大于總產(chǎn)量：則增加一個(gè)假想的產(chǎn)地Am+1，其產(chǎn)量為：49njjmiinbab111miinjjmaba111njjmiiba11miinjjab11（四）產(chǎn)銷不平衡問題一、多起迄點(diǎn)間的直達(dá)運(yùn)輸50 銷地銷地產(chǎn)地產(chǎn)地B1B2BnBn+1(貯存)產(chǎn)量A A1 1x x1111x x1212x x1n1nx x1.n+11.n+1a a1 1A A2 2x x2121x x2222x x2n2nx x2.n+12.n+1a a2 2A Am mx xm1m1x xm2m2x xmnmnx xm.n+1m.n+1a am m銷量銷量b b1 1b b2 2b b3 3b

18、bn n a ai i- - b bj j（四）產(chǎn)銷不平衡問題一、多起迄點(diǎn)間的直達(dá)運(yùn)輸二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配51 t1 t2 tm b1 b2 bn Ckij Xkij 供應(yīng)地供應(yīng)地 需求地需求地 a1 af 中轉(zhuǎn)站中轉(zhuǎn)站 二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配目標(biāo)函數(shù)為：約束條件為：（1）配送量生產(chǎn)能力的限制： k=1，2，f； （2）流通中心發(fā)送能力的限制： i1，2，m；（3）滿足零售店需求量： j=1，2，n；（4）變量非負(fù)：52minjkijkijfkXCZ111minnjkkijmiaX11njikijfktX11fkjkijmibX110kijX（二）數(shù)學(xué)模型二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配例

19、7-2某公司生產(chǎn)變壓器，一個(gè)工廠在A市，每天生產(chǎn)能力為150 ，另一個(gè)工廠在B市，每天生產(chǎn)能力為200 。需求點(diǎn)C市和D市的需求量均為130。公司還需要兩中間轉(zhuǎn)運(yùn)站E市和F市進(jìn)行整合運(yùn)輸。各點(diǎn)間運(yùn)輸單位費(fèi)用見表7-4。試確定從工廠到需求點(diǎn)的最優(yōu)路線。 53二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配（三）求解方法 1、將運(yùn)輸模型轉(zhuǎn)為簡(jiǎn)單的運(yùn)輸問題 （1）增加一虛擬的行或列來平衡需求 （2）構(gòu)造一個(gè)包括所有城市（起點(diǎn)、終點(diǎn)和中間點(diǎn)）作為供需點(diǎn)的運(yùn)輸表（包括虛擬列）。 （3）根據(jù)表7-5的規(guī)則，得到最終運(yùn)輸表轉(zhuǎn)運(yùn)問題中轉(zhuǎn)運(yùn)問題中點(diǎn)的性質(zhì)點(diǎn)的性質(zhì)在運(yùn)輸表中的在運(yùn)輸表中的供應(yīng)值供應(yīng)值在運(yùn)輸表中的在運(yùn)輸表中的需求值需求值

20、供應(yīng)點(diǎn)供應(yīng)點(diǎn)起始供應(yīng)起始供應(yīng)+總供應(yīng)總供應(yīng)總供應(yīng)總供應(yīng)轉(zhuǎn)運(yùn)點(diǎn)轉(zhuǎn)運(yùn)點(diǎn)總供應(yīng)總供應(yīng)總供應(yīng)總供應(yīng)需求點(diǎn)需求點(diǎn)總供應(yīng)總供應(yīng)起始需求起始需求+總供應(yīng)總供應(yīng)空空 點(diǎn)點(diǎn)0起始供應(yīng)起始需求起始供應(yīng)起始需求54需求和供應(yīng)量確定準(zhǔn)則需求和供應(yīng)量確定準(zhǔn)則專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善55表7-6 最終運(yùn)輸表二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配（三）求解方法專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善56表7-7 初始調(diào)運(yùn)方案二、存在中間轉(zhuǎn)運(yùn)的物資調(diào)配（三）求解方法三、圖上作業(yè)法 57（一）圖上作業(yè)法要解決的問題回顧一下什么是對(duì)流運(yùn)輸？5820303020243(20)(20)(30)(30)這是對(duì)流這是對(duì)流2030302024

21、3(20)(20)(30)(30)(10)什么又是迂回運(yùn)輸呢？59206040402463(20)(20)(40)圈長(zhǎng)：圈上每一條邊的長(zhǎng)度之和（記為 l）l =15 先用“丟邊破圈”方法，得到無圈圖，再產(chǎn)生一個(gè)沒有對(duì)流的方案。內(nèi)圈長(zhǎng) l內(nèi)=8外圈長(zhǎng) l外=4是最優(yōu)解碼？8,2ll 內(nèi)不是最優(yōu)的.稱為迂回運(yùn)輸調(diào)整方案：對(duì)內(nèi)圈各流量中最小調(diào)運(yùn)量，進(jìn)行反向調(diào)運(yùn)(40)(20)(20)準(zhǔn)則：內(nèi)外圈長(zhǎng)都小于圈長(zhǎng)的一半的無對(duì)流的調(diào)運(yùn)方案 為最優(yōu)方案67.22llll外內(nèi)此時(shí)為最優(yōu)調(diào)運(yùn)方案三、圖上作業(yè)法1、交通圖的符號(hào) 發(fā)點(diǎn)用“ ”表示，并將發(fā)貨量記在里面，收點(diǎn)用“ ”表示，并將收貨量記在里面。兩點(diǎn)間交通線

22、的長(zhǎng)度記在交通線旁邊。2、調(diào)運(yùn)物資的流向圖 物資調(diào)運(yùn)的方向（流向）用“ ”表示，并把 “ ” 按調(diào)運(yùn)方向畫在交通線的右邊，把調(diào)運(yùn)物資的數(shù)量記在“ ”的右邊并加上括號(hào)。在交通圖成圈時(shí)，若運(yùn)輸方向沿逆時(shí)針方向，則需將流向“ ”畫在圈外，稱為外圈流向，反之，若運(yùn)輸方向沿順時(shí)針方向，則需將流向“ ”畫在圈內(nèi)，稱為內(nèi)圈流向，60（二）交通圖三、圖上作業(yè)法 1、交通圖不含圈 沒有對(duì)流運(yùn)輸即是最優(yōu)方案。61（三）基本步驟三、圖上作業(yè)法6252378135A1A2B1A3B2B3A4B4(5)(7)(1)(2)(1)(5)(2)（三）基本步驟三、圖上作業(yè)法63（三）基本步驟三、圖上作業(yè)法64 銷地銷地產(chǎn)地產(chǎn)地

23、B B1 1B B2 2B B3 3B B4 4產(chǎn)量A A1 15 57 73 3A A2 23 32 23 3A A3 34 44 43 31 1銷量銷量2 23 31 11 17（三）基本步驟三、圖上作業(yè)法653131132A1A2B1A3B2B3B475344432(3)(1)(2)(1)(1)（三）基本步驟（三）基本步驟三、圖上作業(yè)法663131132A1A2B1A3B2B3B475344432(3)(1)(1)(1)(1)(2)(2)(1)（三）基本步驟三、圖上作業(yè)法 銷地銷地產(chǎn)地產(chǎn)地B B1 1B B2 2B B3 3B B4 4產(chǎn)量A A1 12 21 13 3A A2 22 2

24、1 13 3A A3 31 11 1銷量銷量2 23 31 11 1767最優(yōu)調(diào)運(yùn)方案（三）基本步驟三、圖上作業(yè)法練習(xí)：682030A30502070100206030BCDEFGHI234523251813(20)(10)(50)(20)(80)(60)(20)(30)（三）基本步驟三、圖上作業(yè)法練習(xí)：692030A30502070100206030BCDEFGHI234523251813(20)(10)(50)(20)(80)(60)(20)(30)(30)(40)(20)（三）基本步驟 2、交通圖含圈第三節(jié) 物流運(yùn)輸線路的優(yōu)化一、起迄點(diǎn)不同的單一路線優(yōu)化二、起迄點(diǎn)重合的單一路線優(yōu)化70一

25、、起迄點(diǎn)不同的單一路線優(yōu)化 71AB1B2B3C1C2C3D1D2E3541584642469751242（一）動(dòng)態(tài)規(guī)劃法（逆序遞推）72一、起迄點(diǎn)不同的單一路線優(yōu)化n=4n=3n=2n=1AB1B2B3C1C2C3D1D2E3541584642469751242（二）標(biāo)號(hào)法（Dijkstra方法）例7-373OABCDET225417443175起點(diǎn)終點(diǎn)OABCDET225417443175起點(diǎn)終點(diǎn)圖7-5 運(yùn)輸網(wǎng)絡(luò)圖一、起迄點(diǎn)不同的單一路線優(yōu)化表7-8 Dijkstra算法步驟表74二、起迄點(diǎn)重合的單一路線優(yōu)化（一）旅行商問題（TSP）模型1、問題描述75 C A B D 38 18 31

26、 22 27 45 444241242221141211.xxxxxxxxxXs0382745380183127180224531220ijCninjijijXCZ11min專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善76二、起迄點(diǎn)重合的單一路線優(yōu)化（一）旅行商問題（TSP）模型 2、解決辦法 枚舉、分支定界、現(xiàn)代優(yōu)化方法（遺傳算法等）啟發(fā)式算法。 貪婪算法： 選擇距離出發(fā)點(diǎn)最近的顧客位置； 再?gòu)氖Ｏ碌奈恢弥羞x距離已選擇的位置最近的顧客位置。 如果所有位置都被選擇了，則停止，否則返回。 C A B D 38 18 31 22 27 45 專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善77（二）中國(guó)郵遞員問題預(yù)備

27、知識(shí)：圖論的相關(guān)概念“頂點(diǎn)”表示某對(duì)象節(jié)點(diǎn)（設(shè)施地點(diǎn)或企業(yè)單位）?！斑叀北硎緦?duì)象之間的某種特性（如距離）。邊上的非負(fù)數(shù)字稱為“權(quán)”。以V為頂點(diǎn)的邊的數(shù)目稱為頂點(diǎn)V的“次”。次為奇數(shù)的點(diǎn)，稱為奇點(diǎn)；次為偶數(shù)的點(diǎn)，稱為偶點(diǎn)。由點(diǎn)、邊交替構(gòu)成的序列稱為“鏈”；起點(diǎn)與終點(diǎn)相同的鏈就稱為“圈”。二、起迄點(diǎn)重合的單一路線優(yōu)化專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善78（二）中國(guó)郵遞員問題預(yù)備知識(shí)：圖論的相關(guān)概念二、起迄點(diǎn)重合的單一路線優(yōu)化（二）中國(guó)郵遞員問題1確定可行方案（如果有奇點(diǎn)存在 ）79 V2 V9 5 9 4 3 4 2 4 5 6 4 3 V4 V8 V6 4 V5 V3 V1 V7 V3 V1

28、V2 V44 V5 V6 V7 V8 V9 二、起迄點(diǎn)重合的單一路線優(yōu)化圖圖7-8 街道圖街道圖 圖圖7-9 加重復(fù)邊后的街道圖（可行方案）加重復(fù)邊后的街道圖（可行方案） 專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善80（二）中國(guó)郵遞員問題2判斷最優(yōu)方案（兩條標(biāo)準(zhǔn)） V2 V3 V44 V9 3 5 5 4 6 9 2 3 3 4 4 4 4 V7 V6 V5 V8 V1 V2 V3 V44 V9 3 5 5 4 6 9 2 3 3 4 4 4 4 V7 V6 V5 V8 V1 V2 V3 V4 V9 3 5 5 4 6 9 2 3 4 4 4 4 V7 V6 V5 V8 V1 （a）調(diào)整方案一）調(diào)整

29、方案一 （b）調(diào)整方案二）調(diào)整方案二 （c）調(diào)整方案三（最佳方案）調(diào)整方案三（最佳方案） 第四節(jié) 行車路線及時(shí)刻表的制定81一、運(yùn)輸路線及時(shí)刻表制訂的原則1同一車輛服務(wù)的客戶按距離聚類82 倉 庫 倉 庫 2避免行車路線交叉3盡可能使用大載重量車輛，減少出車數(shù)量4取貨/送貨混合安排5從距倉庫最遠(yuǎn)的站點(diǎn)開始設(shè)計(jì)線路83圖7-13 合理與不合理的行車線路一、運(yùn)輸路線及時(shí)刻表制訂的原則二、行車路線制訂的掃描法1、基本原理 先以倉庫(物流中心)為原點(diǎn)，將所有需求點(diǎn)的極坐標(biāo)算出，然后依角度大小以逆時(shí)針或順時(shí)針方向掃描，若滿足車輛裝載量即劃分為一群，將所有點(diǎn)掃描完畢后在每個(gè)群內(nèi)用最短路徑法求出車輛最佳行駛

30、路徑。2、基本步驟 第一步：求出各客戶點(diǎn)的極坐標(biāo)。 第二步：掃描劃分客戶群。 第三步：確定每輛車的最佳路徑（TSP算法 ）。84專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善85二、行車路線制訂的掃描法【例7-4】某運(yùn)輸公司為其客戶企業(yè)提供取貨服務(wù)，貨物運(yùn)回倉庫集中后，將以更大的批量進(jìn)行長(zhǎng)途運(yùn)輸。所有取貨任務(wù)均由載重量為10噸的貨車完成?，F(xiàn)在有13家客戶有取貨要求，各客戶的去貨量、客戶的地理位置坐標(biāo)見表7-10。運(yùn)輸公司倉庫的坐標(biāo)為（19.50，5.56）。要求合理安排車輛，并確定各車輛行駛路線，使總運(yùn)輸里程最短。 86 3 2 2.4 2.8 3.11.8 2.5 2.25 2.6 2.11.5 1.

31、9 1.6 1#線路 2#線路 3#線路 11 12 9 10 7 8 2 1 5 4 3 13 6 0 二、行車路線制訂的掃描法三、行車路線制訂的節(jié)約法基本思想：如果將運(yùn)輸問題中的兩個(gè)回路合并成一個(gè)回路，就可縮短線路總里程（即節(jié)約了距離），并減少了一輛卡車。87 COA CBO A B O 倉庫 A B O 倉庫 （a）初始路線 總里程= COA + CAO + COB + CBO CAO COB （b）將兩個(gè)站點(diǎn)合并成同一線路 總里程= COA + CAB + CBO CAB COA CBO 圖7-15 節(jié)約法的圖形描述專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善88【例7-5】某配送中心要為13

32、個(gè)客戶提供配送服務(wù)，配送中心的位置、客戶的坐標(biāo)及客戶的訂單規(guī)模見表7-11。配送中心共有4輛卡車，每輛車的載重量是200件。 由于送貨成本與車輛行駛總里程之間密切相關(guān)，公司經(jīng)理希望獲得總行駛距離最短的方案。如何分配客戶？如何確定車輛行駛路徑？ 三、行車路線制訂的節(jié)約法89三、行車路線制訂的節(jié)約法1確定距離方陣9022)()(BABAAByyxxC三、行車路線制訂的節(jié)約法2計(jì)算節(jié)約矩陣91三、行車路線制訂的節(jié)約法3將客戶劃歸到不同的運(yùn)輸路線92三、行車路線制訂的節(jié)約法93三、行車路線制訂的節(jié)約法94三、行車路線制訂的節(jié)約法95 11 7 8 9 10 12 13 5 2 3 4 6 1 0 X

33、Y 三、行車路線制訂的節(jié)約法第五節(jié) 運(yùn)輸工具與貨載的最優(yōu)分配一、航線配船優(yōu)化問題二、多車多品種貨載配車優(yōu)化96一、航線配船優(yōu)化問題（一）問題概述 設(shè)船公司經(jīng)營(yíng)n條航線。第j條航線上規(guī)劃期正向貨運(yùn)量預(yù)測(cè)為Qj，公司擁有裝載能力分別為Ni的m種船型；i型船的船舶艘數(shù)為mi，一艘i型船在j航線上規(guī)劃期可以完成的最大往返航次數(shù)為nij；一艘i型船在j航線上完成一個(gè)往返航次所花費(fèi)的全部成本為kij。要求將這些船合理地安排在這幾條航線上，使公司的經(jīng)濟(jì)效益最好。 97專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善98一、航線配船優(yōu)化問題（二）數(shù)學(xué)模型的建立1參數(shù)說明I 船型編號(hào)，i=1,2，m；J 航線編號(hào)，j=1,

34、2，n；Xij i型船在j航線上每季度完成的往返航次數(shù)，是決策變量；Yj j航線上未被船舶承運(yùn)的貨物量，也是決策變量；Kij 每艘i型船在j航線上完成一個(gè)往返航次所花費(fèi)的運(yùn)營(yíng)成本； j航線上單位貨物未被承運(yùn)產(chǎn)生的費(fèi)用損失； 每艘i型船在j航線上每季度可以完成的最大往返航次數(shù)； i型船的集裝箱裝載能力； i型船的船舶數(shù)量； j航線的正向運(yùn)量。 jijniNimjQ專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善99一、航線配船優(yōu)化問題（二）數(shù)學(xué)模型的建立2目標(biāo)函數(shù)3約束條件jnjjijminjijyxKk 111min0, 0111jijjjijmiiiijnjijyxQyxNmxn專注專業(yè)、持續(xù)改善專注專

35、業(yè)、持續(xù)改善100一、航線配船優(yōu)化問題（三）航線配船優(yōu)化舉例【例7-6】假設(shè)某船公司擁有3種噸位的集裝箱船舶共30搜，分別是1500TEU的8艘、850TEU的12艘、500TEU的10艘?，F(xiàn)開辟班輪航線6條，各航線季度集裝箱運(yùn)輸量、船舶在每條航線每季度最多能完成的航次數(shù)、每艘船在各航線每往返航次的成本（萬元）以及每條航線發(fā)現(xiàn)的機(jī)會(huì)成本（萬元/TEU）如表7-17至表7-19所示。求不同航線的船舶最佳配置方案。 一、航線配船優(yōu)化問題（三）航線配船優(yōu)化舉例101102一、航線配船優(yōu)化問題（三）航線配船優(yōu)化舉例專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善103解：（1）目標(biāo)函數(shù)： 一、航線配船優(yōu)化問題33

36、2313232221213121115 .202528125. 020242515. 0182430minxxxyxxxyxxxK2414324251 . 0 xxy26165352515434283215. 02030351 . 05 .18xxyxxxyx636125. 032yx專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善104解：（2）約束條件： 一、航線配船優(yōu)化問題且均為整數(shù), 0, 0,7000500850150030005008501500450050085015005000500850150080005008501500600050085015001021514141411231214131413182131213121613611636261653525154342414333231323222121312111363534333231262524232221161514131211yyxxyxxxyxxxyxxxyxxxyxxxyxxxxxxxxxxxxxxxxxxxxx專注專業(yè)、持續(xù)改善專注專業(yè)、持續(xù)改善105解：（3）求解結(jié)果一、航線配船優(yōu)化問題二、多車多品種貨載配車優(yōu)化（一）問題描述 已知有m輛零擔(dān)作業(yè)車，其載重量和容積分別為G1，G2，Gm和V1，V2，Vm?，F(xiàn)有n批貨物H1，H2，Hn，其重量和體積分別為g1，g2，gn和v1，v2，vn。 試確定一個(gè)