《物流運(yùn)籌方法與工具》第3版 課件 模塊六單元一 運(yùn)輸路徑規(guī)劃概述

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

CONTENTS物流運(yùn)籌方法與工具概述物流決策分析物流資源配置規(guī)劃物流任務(wù)指派運(yùn)輸方案優(yōu)化運(yùn)輸路徑規(guī)劃物流項(xiàng)目計(jì)劃技術(shù)物流需求預(yù)測(cè)庫(kù)存水平控制模塊六模塊二模塊三模塊四模塊五模塊七模塊八模塊九模塊一模塊六運(yùn)輸路徑規(guī)劃運(yùn)輸路徑規(guī)劃概述應(yīng)用舉例線路選擇的最短路法運(yùn)輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹(shù)法車(chē)輛配送路線的安排單元四單元三單元二單元一單元六單元五知識(shí)點(diǎn)1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問(wèn)題的含義；掌握求解最短路問(wèn)題的Dijkstra算法步驟。3．理解可行流、最大流、增廣鏈的概念；掌握求解最大流問(wèn)題的標(biāo)號(hào)算法步驟。4．理解最小樹(shù)、圖的中心和重心的含義；掌握最小樹(shù)問(wèn)題的逐步生長(zhǎng)法步驟。5．理解單、多車(chē)輛配送路線安排問(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é)為最小樹(shù)問(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)+高效物流”和“降本增效”理念。下圖是某鄉(xiāng)下屬的7個(gè)村間的公路交通圖，各條邊旁邊的數(shù)字是該條公路的長(zhǎng)度（單位：千米(km)）。已知各村的玉米產(chǎn)量為v1——30（kt下同），v2—40，v3—25，v4—20，v5—50，v6—60，v7—60，鄉(xiāng)糧庫(kù)建在哪個(gè)村子，才能使收購(gòu)各村玉米時(shí)所用的千噸·千米(kt·km)數(shù)最??？引導(dǎo)案例玉米收購(gòu)運(yùn)輸?shù)木W(wǎng)絡(luò)優(yōu)化問(wèn)題v1v2v3v4v5v6v752762247136單元一運(yùn)輸路徑規(guī)劃概述一、運(yùn)輸路徑規(guī)劃問(wèn)題二、圖的概念與模型運(yùn)輸路徑規(guī)劃：運(yùn)輸路徑規(guī)劃問(wèn)題種類(lèi)：一、運(yùn)輸路徑規(guī)劃問(wèn)題路徑是指物品運(yùn)輸?shù)穆肪€，網(wǎng)絡(luò)是指物品運(yùn)輸?shù)牡攸c(diǎn)與路徑的總和，運(yùn)輸路徑規(guī)劃是物流運(yùn)輸過(guò)程中的最重要環(huán)節(jié)，是在一定的運(yùn)輸網(wǎng)絡(luò)（公路網(wǎng)、鐵路線、水運(yùn)航道和航空線）內(nèi)，找到運(yùn)輸工具的最短運(yùn)輸線路、最大運(yùn)輸流量的線路分布、運(yùn)輸量最小的線路網(wǎng)布局、運(yùn)輸工作量最小的配送路線安排等路徑規(guī)劃方案。一是最短運(yùn)輸線路選擇的最短路法；二是最大網(wǎng)絡(luò)流量分布的最大流法；三是最小運(yùn)輸量線路網(wǎng)布局的最短樹(shù)法；四是最佳配送線路策略制定的節(jié)約法。二、圖的概念與模型圖6-3所示是某地的公路交通圖，vi表示城鎮(zhèn)，城鎮(zhèn)間的連線表示公路。例如連線v1v2

表示城鎮(zhèn)v1和v2之間有公路相通，依此類(lèi)推，v3和v5之間不存在連線，說(shuō)明這兩個(gè)城市時(shí)間沒(méi)有直接的公路相通。v1v2v3v4v5圖6-3某地的公路交通圖二、圖的概念與模型1．節(jié)點(diǎn)節(jié)點(diǎn)用來(lái)表示物理實(shí)體或事物，一般用vi

來(lái)表示。例如，圖6-3中的節(jié)點(diǎn)就是各城鎮(zhèn)。2．邊邊是節(jié)點(diǎn)間的連線，表示兩節(jié)點(diǎn)之間有關(guān)系，一般用eij來(lái)表示。圖6-3中的邊就是各城鎮(zhèn)之間的公路。二、圖的概念與模型4．網(wǎng)絡(luò)若對(duì)圖的每一邊定義一個(gè)表示連接關(guān)系的權(quán)值，用wij表示，則將該圖稱(chēng)為網(wǎng)絡(luò)。3．圖

圖是由一些節(jié)點(diǎn)和一些邊組成的圖形。所以，圖一定是節(jié)點(diǎn)和邊的集合，一般用

表示圖，其中

表示節(jié)點(diǎn)集合，

表示邊的集合二、圖的概念與模型5．鏈下圖中相鄰節(jié)點(diǎn)的序列

稱(chēng)為該圖的一個(gè)鏈。如圖6-5中的

就是一個(gè)鏈。v2v3v4v5e1v1e2e3e4e5e6e7圖6-5連通圖二、圖的概念與模型6．連通圖在一個(gè)圖中，若任意兩點(diǎn)之間至少存在一條鏈，則稱(chēng)該圖為連通圖，否則就稱(chēng)為不連通圖。圖6-6為不連通圖。圖6-6不連通圖v1v2v3v4v5v6二、圖的概念與模型7．圖模型對(duì)要研究的問(wèn)題確定了具體對(duì)象并找出這些對(duì)象之間的聯(lián)系后，如果用圖的形式表示出來(lái)，就是對(duì)研究的問(wèn)題建立了圖的模型。它是對(duì)大量