《物流運籌方法與工具》第3版 課件 模塊六單元六 應(yīng)用舉例

物流運籌方法與工具（第3版）目錄

CONTENTS物流運籌方法與工具概述物流決策分析物流資源配置規(guī)劃物流任務(wù)指派運輸方案優(yōu)化運輸路徑規(guī)劃物流項目計劃物流需求預(yù)測庫存水平控制模塊六模塊二模塊三模塊四模塊五模塊七模塊八模塊九模塊一模塊六運輸路徑規(guī)劃運輸路徑規(guī)劃概述應(yīng)用舉例線路選擇的最短路法運輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹法車輛配送路線的安排單元四單元三單元二單元六單元一單元五知識點1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義；掌握求解最短路問題的Dijkstra算法步驟。3．理解可行流、最大流、增廣鏈的概念；掌握求解最大流問題的標(biāo)號算法步驟。4．理解最小樹、圖的中心和重心的含義；掌握最小樹問題的逐步生長法步驟。5．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。6．掌握單回路路線優(yōu)化的最近鄰點法和最近插入法的求解步驟。7．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。能力點、素質(zhì)點能力點：1．能夠把相應(yīng)的實際問題歸結(jié)為最短路問題，并能夠熟練運用Dijkstra算法求解。2．能夠把相應(yīng)的實際問題歸結(jié)為最大流問題，并能熟練運用標(biāo)號算法求解。3．能夠把相應(yīng)的實際問題歸結(jié)為最小樹問題，并能熟練運用逐步生長法求解。4．能夠把相應(yīng)的實際問題歸結(jié)為回路運輸路線優(yōu)化問題，并能熟練運用最近鄰點法和最近插入法、掃描法、節(jié)約法求解。素質(zhì)點：1．提高對大數(shù)據(jù)及云計算、物聯(lián)網(wǎng)、人工智能等新科技的應(yīng)用興趣，勇于實踐創(chuàng)新。2．加強“互聯(lián)網(wǎng)+高效物流”和“降本增效”理念。單元六應(yīng)用舉例一、車輛運輸路線選擇二、運輸網(wǎng)送貨能力分析三、運輸網(wǎng)絡(luò)中心和重心確定四、配送路線安排及效益評估一、車輛運輸路線選擇王健是一家運輸公司的車輛調(diào)度員。他的公司已經(jīng)簽訂了一項運輸合同，要把沈陽的一批貨物運送到北京附近地區(qū)。王健查看了這兩個城市之間可選擇的行車路線的地圖，然后繪制了公路網(wǎng)絡(luò)圖，并在每一條公路上標(biāo)出了里程數(shù)（公里），如圖6-33所示。王健的任務(wù)是找出沈陽到北京的最短路線。一、車輛運輸路線選擇11023456789650沈陽北京01006003001502756005004001001504001252001502001753503001752752752002501009-108-106-9-102-6-9-105-8-104-6-9-107-8-103-5-8-101-4-6-9-106-34兩城市間的交通網(wǎng)線王健運用Dijkstra算法尋找最短路線的過程如下：1．從終點開始逐步逆向推算：與終點10連接的有兩個點，即9和8，先從9開始計算。9到10只有一條路線，因此沒有選擇余地，9-10就是最短的路線，它的里程為100，寫在節(jié)點9上方的框中，并注上9-10。同樣8至10也只有一條路線，最短路線為8-10，里程為150，也按相同方式記上。2．再看節(jié)點6：與6連接的只有一個節(jié)點9，因此最短路線為6-9，6至9的里程為200，而9至終點10的最短里程為100，因此6至終點的最短里程為200+100=300。記入方式同上，方框上注上6-9-10。一、車輛運輸路線選擇王健運用Dijkstra算法尋找最短路線的過程如下：3．再看節(jié)點5：與5連接的節(jié)點有9、8兩個，5至9再至終點的最短里程為400+100=500，5至8再至終點的最短里程為250+150=400。400<500，所以5至終點的最短里程為400，寫在節(jié)點5上方的方框中，方框上再注上5-8-10。點7至終點的最短里程為125+150=275。記入格式同上。4．再看節(jié)點4：與4連接的節(jié)點有5、6、7三個。4至6再到終點的最短里程為200+300=500，4至5再到終點的最短里程為175+400=575，4至7再到終點的最短里程為275+275=550。三個里程中以500為最小，所以把500寫在節(jié)點4上方的方框中，方框上注上4-6-9-10。一、車輛運輸路線選擇王健運用Dijkstra算法尋找最短路線的過程如下：用同樣的方法，算出了節(jié)點2到終點的最短里程為600，節(jié)點3到終點的最短里程也為600。記入的格式同上。5．最后看節(jié)點1，與節(jié)點1連接的路線有3條：1至2再到終點的最短里程100+600=700；1至4再到終點的最短里程150+500=650；1至3再到終點的最短里程175+600=775。；三個里程中以650為最小，這就是從沈陽到北京的最短里程，而對應(yīng)的最短路線為1-4-6-9-10。如圖6-34中加粗線所示。一、車輛運輸路線選擇二、運輸網(wǎng)送貨能力分析

甲市有一生產(chǎn)廠家生產(chǎn)A原料供應(yīng)給乙市市場需求，該原料的分撥任務(wù)外包給了順通運輸公司?，F(xiàn)在生產(chǎn)廠家為了應(yīng)對市場需求高鋒的到來，確保需求高鋒期間有足夠數(shù)量的原料銷售，要求運輸公司在需求高鋒到來之前，一周內(nèi)將22噸原料貨物準(zhǔn)時運送到乙市市場。

如果運輸公司不能按時將22噸原料送到乙市市場，將影響來年生產(chǎn)廠家與運輸公司的合同是否續(xù)約問題。為了保證廠家運輸任務(wù)的及時、可靠，運輸公司經(jīng)理要求調(diào)度人員對本公司的運輸網(wǎng)絡(luò)送貨能力進行評估，以便做好相應(yīng)的準(zhǔn)備安排工作。二、運輸網(wǎng)送貨能力分析運輸網(wǎng)送貨能力分析過程如下：調(diào)度人員首先繪制了本公司運輸網(wǎng)絡(luò)圖。101041151124甲市廠家610718乙市市場3圖6-34運輸專線網(wǎng)絡(luò)圖二、運輸網(wǎng)送貨能力分析運輸網(wǎng)送貨能力分析過程如下：運輸網(wǎng)絡(luò)送貨能力評估問題轉(zhuǎn)化為求解最大流問題。1．任意先選一條從甲市到乙市的送貨線路，如：甲→1→4→乙，最多可安排送貨6噸，在圖上作標(biāo)記，圖中線路旁的數(shù)字為

，見圖6-35。2．再選第二條從甲市到乙市的送貨線路，可選：甲→2→4→乙，最多可安排送貨10噸，在圖上作標(biāo)記，見圖6-35。二、運輸網(wǎng)送貨能力分析10（5）10411（10）5（5）1124甲市廠家6（6）10（10）7（6）18(6)(10)乙市市場3圖6-36線路流量調(diào)整1二、運輸網(wǎng)送貨能力分析3．再選第三條從甲市到乙市的送貨線路，可選：甲→3→乙，最多可安排送貨5噸，在圖上作標(biāo)記。目前流量安排情況見圖6-35所示，此時，支線甲→1，甲→2，3→乙已無剩余送貨能力，這三條支線不再考慮安排送貨，可從圖中去掉，見圖6-36所示。圖6-37線路流量調(diào)整27(6)(1)18(6)(10)(1)(1)10(5)(1)(1)10(0)4（1）11(10)(1)1（1）124甲市廠家乙市市場3二、運輸網(wǎng)送貨能力分析4．再選第四條線路：甲→3→2→4→乙，最多可安排送貨1噸，在圖上標(biāo)記，見圖6-36。5．再選第五條線路：甲→3→1→4→乙，最多可安排送貨1噸，在圖上標(biāo)記，見圖6-36。現(xiàn)在通往乙市市場的最后一條支線4→乙已無多余的送貨能力，因此該網(wǎng)絡(luò)最大流量值已經(jīng)求得，各支線流量分配如圖6-37所示。二、運輸網(wǎng)送貨能力分析10（10）10（7）10（0）4（1）11（11）5（5）1（1）124甲市廠家6（6）7（7）18（18）乙市市場3圖6-38

運輸網(wǎng)絡(luò)最大送貨量分布方案最大送貨量=6噸（1線）+10噸（2線）+5噸（3線）+1噸（4線）+1噸（5線）=23噸。23噸>22噸，測算結(jié)果表明，順通運輸公司現(xiàn)有的運輸網(wǎng)絡(luò)能夠完成一周內(nèi)22噸的送貨任務(wù)，不必另想計劃措施。三、運輸網(wǎng)絡(luò)中心和重心確定（一）網(wǎng)絡(luò)中心圖6-39所示為華陽物流公司在某一市區(qū)的零擔(dān)運輸網(wǎng)點布局圖。其中點表示該公司的營運站點，邊表示各站點間已有的交通路線，邊旁的數(shù)字表示兩點間的距離長度（公里）。（1）現(xiàn)在公司要確定能保證各站點互通且使運輸專線總長度最小的運營線路網(wǎng)。（2）在公司運營線路網(wǎng)中，確定適合建集貨中心的站點，保證使離該中心最遠的站點往中心倉庫送貨時所走的路程最短？圖6-39地區(qū)交通線路圖三、運輸網(wǎng)絡(luò)中心和重心確定三、運輸網(wǎng)絡(luò)中心和重心確定所謂圖的中心，是在最小樹中先分別找出各頂點之間的最大距離，然后在各點的最大距離中找出一最小距離的點，則該點即為圖的中心，用數(shù)學(xué)公式描述，即上述第一個問題很明顯是個最小樹問題，而第二個問題就是最小樹的中心問題。三、運輸網(wǎng)絡(luò)中心和重心確定（1）確定線路總長度最小的公司運營線路網(wǎng)，可以用逐步生長法或破圈法求得最小樹，該最小樹就是總長度最小的運營網(wǎng)絡(luò)，如圖6-39所示。

圖6-40公司運營線路網(wǎng)三、運輸網(wǎng)絡(luò)中心和重心確定居民點V1V2V3V4V5V6V7d(vi)V10356.39.34.569.3V23023.36.31.536.3V35205.38.33.558.3V46.33.35.3031.83.36.3V59.36.38.3304.86.39.3V64.51.53.51.84.801.54.8V76353.36.31.506.3表6-6各點間的最大距離表三、運輸網(wǎng)絡(luò)中心和重心確定得：三、運輸網(wǎng)絡(luò)中心和重心確定（二）網(wǎng)絡(luò)重心接上述華陽物流公司問題，公司7個營運站點除了上述攬貨任務(wù)外，還負責(zé)各自所在區(qū)域的商超百貨店的快速消費品配送任務(wù)。這些貨物由公司中心貯存庫提前統(tǒng)一分發(fā)給各站點，然后由站點完成配送工作。今已知各站點每周快速消費品的配送量如圖6-41所示，那么公司中心貯存庫設(shè)在哪個站點，能使每周總的運輸量為最小？三、運輸網(wǎng)絡(luò)中心和重心確定圖6-41圖的重心問題三、運輸網(wǎng)絡(luò)中心和重心確定三、運輸網(wǎng)絡(luò)中心和重心確定三、運輸網(wǎng)絡(luò)中心和重心確定表6-7各站點對應(yīng)的每周總運輸量v1122300v5131600v271300v672800v389300v795300v492600三、運輸網(wǎng)絡(luò)中心和重心確定四、配送路線安排及效益評估四、配送路線安排及效益評估上述優(yōu)化問題利用節(jié)約里程法求解如下：四、配送路線安排及效益評估四、配送路線安排及效益評估