《物流運(yùn)籌方法與工具》第3版 課件 模塊六單元二 線路選擇的最短路法

物流運(yùn)籌方法與工具（第3版）目錄

CONTENTS物流運(yùn)籌方法與工具概述物流決策分析物流資源配置規(guī)劃物流任務(wù)指派運(yùn)輸方案優(yōu)化運(yùn)輸路徑規(guī)劃物流項目計劃物流需求預(yù)測庫存水平控制模塊六模塊二模塊三模塊四模塊五模塊七模塊八模塊九模塊一模塊六運(yùn)輸路徑規(guī)劃運(yùn)輸路徑規(guī)劃概述應(yīng)用舉例線路選擇的最短路法運(yùn)輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹法車輛配送路線的安排單元四單元三單元一單元二單元六單元五知識點(diǎn)1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義；掌握求解最短路問題的Dijkstra算法步驟。3．理解可行流、最大流、增廣鏈的概念；掌握求解最大流問題的標(biāo)號算法步驟。4．理解最小樹、圖的中心和重心的含義；掌握最小樹問題的逐步生長法步驟。5．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。6．掌握單回路路線優(yōu)化的最近鄰點(diǎn)法和最近插入法的求解步驟。7．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。本單元知識點(diǎn)能力點(diǎn)、素質(zhì)點(diǎn)能力點(diǎn)：1．能夠把相應(yīng)的實際問題歸結(jié)為最短路問題，并能夠熟練運(yùn)用Dijkstra算法求解。2．能夠把相應(yīng)的實際問題歸結(jié)為最大流問題，并能熟練運(yùn)用標(biāo)號算法求解。3．能夠把相應(yīng)的實際問題歸結(jié)為最小樹問題，并能熟練運(yùn)用逐步生長法求解。4．能夠把相應(yīng)的實際問題歸結(jié)為回路運(yùn)輸路線優(yōu)化問題，并能熟練運(yùn)用最近鄰點(diǎn)法和最近插入法、掃描法、節(jié)約法求解。素質(zhì)點(diǎn)：1．提高對大數(shù)據(jù)及云計算、物聯(lián)網(wǎng)、人工智能等新科技的應(yīng)用興趣，勇于實踐創(chuàng)新。2．加強(qiáng)“互聯(lián)網(wǎng)+高效物流”和“降本增效”理念。單元二線路選擇的最短路法

一、最短路的含義

二、最短路的Dijkstra算法線路選擇問題：最短路問題的一般提法：一、最短路的含義在已知的物流網(wǎng)絡(luò)（通過各段線路所需的時間、距離或費(fèi)用為已知）中，有一貨物發(fā)點(diǎn)（供應(yīng)點(diǎn)）對一貨物收點(diǎn)（客戶）專門送貨，在這種直送情況下找出貨物運(yùn)送所需的最少時間、最短距離或最少費(fèi)用的路徑問題。二、最短路的Dijkstra算法用dij表示圖中兩點(diǎn)i與j相鄰時的距離，即邊[i,j]的長度。若點(diǎn)i與j不相鄰時，dij=∞。顯然dii=0。用

表示從點(diǎn)s到點(diǎn)i的最短路的長度?，F(xiàn)在要求從點(diǎn)s到點(diǎn)t的最短路，相應(yīng)的Dijkstra算法步驟如下：1從點(diǎn)s出發(fā)，逐一地給其它的點(diǎn)i標(biāo)上記號：lsi

，把lsi

的數(shù)值標(biāo)注在點(diǎn)i旁邊的小方框內(nèi)，表示點(diǎn)i已標(biāo)號（標(biāo)號說明點(diǎn)s到點(diǎn)i的最短路已找到）。首先，給點(diǎn)s標(biāo)號lss=0。二、最短路的Dijkstra算法2找出與點(diǎn)s相鄰的點(diǎn)中距離最小的一個，若有幾個點(diǎn)同時達(dá)到最小，就都找出來。設(shè)找出的點(diǎn)為r，將lsr=lss+dsr

的值標(biāo)注給點(diǎn)r，表明點(diǎn)r也已標(biāo)號，同時把邊[s,r]加粗。3從已標(biāo)號的點(diǎn)出發(fā)，找出與這些點(diǎn)相鄰的所有未標(biāo)號的點(diǎn)。把每個已標(biāo)號點(diǎn)旁標(biāo)注的數(shù)字和與之相鄰的點(diǎn)到這個已標(biāo)號點(diǎn)間的距離加起來，從所有這些和中選出一個最小的來。再找出最小和對應(yīng)的未標(biāo)號點(diǎn)，然后給這個未標(biāo)號點(diǎn)比如q標(biāo)號：Lsq=lsk+dkg,，同時加粗邊[k,q]。二、最短路的Dijkstra算法4重復(fù)第（3）步，直到給點(diǎn)t標(biāo)上號

，而且相應(yīng)的t的關(guān)聯(lián)邊加粗為止。例6-1

用Dijkstra算法求圖6-1中從

到

的最短路。v1v2v3v4v5v6v752762247136二、最短路的Dijkstra算法v4v1v2v3v5v6v7527622471360圖6-1（a）二、最短路的Dijkstra算法圖6-1（b）v1v2v3v4v5v6v75276224713620二、最短路的Dijkstra算法圖6-1（c）v1v2v3v4v5v6v752762247136205二、最短路的Dijkstra算法圖6-1（d）v1v2v3v4v5v6v7527622471362605二、最短路的Dijkstra算法圖6-1（e）v1v2v3v4v5v6v752762247136260577二、最短路的Dijkstra算法圖6-1（f）v1v2v3v4v5v6v75276224