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

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

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

一、最短路的含義

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

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

，把lsi

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

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

，而且相應的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