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

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

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

一、最短路的含義

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

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

，把lsi

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

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