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

CONTENTS物流運(yùn)籌方法與工具概述物流決策分析物流資源配置規(guī)劃物流任務(wù)指派運(yùn)輸方案優(yōu)化運(yùn)輸路徑規(guī)劃物流項(xiàng)目計(jì)劃技術(shù)物流需求預(yù)測(cè)庫存水平控制模塊六模塊二模塊三模塊四模塊五模塊七模塊八模塊九模塊一模塊六運(yùn)輸路徑規(guī)劃運(yùn)輸路徑規(guī)劃概述應(yīng)用舉例線路選擇的最短路法運(yùn)輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹法車輛配送路線的安排單元四單元三單元二單元一單元六單元五知識(shí)點(diǎn)1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義；掌握求解最短路問題的Dijkstra算法步驟。3．理解可行流、最大流、增廣鏈的概念；掌握求解最大流問題的標(biāo)號(hào)算法步驟。4．理解最小樹、圖的中心和重心的含義；掌握最小樹問題的逐步生長(zhǎng)法步驟。5．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。6．掌握單回路路線優(yōu)化的最近鄰點(diǎn)法和最近插入法的求解步驟。7．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。本單元知識(shí)點(diǎn)能力點(diǎn)、素質(zhì)點(diǎn)能力點(diǎn)：1．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最短路問題，并能夠熟練運(yùn)用Dijkstra算法求解。2．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最大流問題，并能熟練運(yùn)用標(biāo)號(hào)算法求解。3．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最小樹問題，并能熟練運(yùn)用逐步生長(zhǎng)法求解。4．能夠把相應(yīng)的實(shí)際問題歸結(jié)為回路運(yùn)輸路線優(yōu)化問題，并能熟練運(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)糧庫建在哪個(gè)村子，才能使收購各村玉米時(shí)所用的千噸·千米(kt·km)數(shù)最??？引導(dǎo)案例玉米收購運(yùn)輸?shù)木W(wǎng)絡(luò)優(yōu)化問題v1v2v3v4v5v6v752762247136單元一運(yùn)輸路徑規(guī)劃概述一、運(yùn)輸路徑規(guī)劃問題二、圖的概念與模型運(yùn)輸路徑規(guī)劃：運(yùn)輸路徑規(guī)劃問題種類：一、運(yùn)輸路徑規(guī)劃問題路徑是指物品運(yùn)輸?shù)穆肪€，網(wǎng)絡(luò)是指物品運(yùn)輸?shù)牡攸c(diǎn)與路徑的總和，運(yùn)輸路徑規(guī)劃是物流運(yùn)輸過程中的最重要環(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)布局的最短樹法；四是最佳配送線路策略制定的節(jié)約法。二、圖的概念與模型圖6-3所示是某地的公路交通圖，vi表示城鎮(zhèn)，城鎮(zhèn)間的連線表示公路。例如連線v1v2

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

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

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

表示圖，其中

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

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

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

就是一個(gè)鏈。v2v3v4v5e1v1e2e3e4e5e6e7圖6-5連通圖二、圖的概念與模型6．連通圖在一個(gè)圖中，若任意兩點(diǎn)之間至少存在一條鏈，則稱該圖為連通圖，否則就稱為不連通圖。圖6-6為不連通圖。圖6-6不連通圖v1v2v3v4v5v6二、圖的概念與模型7．圖模型對(duì)要研究的問題確定了具體對(duì)象并找出這些對(duì)象之間的聯(lián)系后，如果用圖的形式表示出來，就是對(duì)研究的問題建立了圖的模型。它是對(duì)大量實(shí)際問題的抽象和概括。譬如我們?cè)谏a(chǎn)和生活中，常見到公路或鐵路交通圖、管網(wǎng)圖、通訊聯(lián)絡(luò)圖等，其中點(diǎn)（車站、自來水廠、通訊臺(tái)、用戶等）表示研究對(duì)象，邊表示這些對(duì)象之間的相互聯(lián)系。模塊六運(yùn)輸路徑規(guī)劃運(yùn)輸路徑規(guī)劃概述應(yīng)用舉例線路選擇的最短路法運(yùn)輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹法車輛配送路線的安排單元四單元三單元一單元二單元六單元五知識(shí)點(diǎn)1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義；掌握求解最短路問題的Dijkstra算法步驟。3．理解可行流、最大流、增廣鏈的概念；掌握求解最大流問題的標(biāo)號(hào)算法步驟。4．理解最小樹、圖的中心和重心的含義；掌握最小樹問題的逐步生長(zhǎng)法步驟。5．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。6．掌握單回路路線優(yōu)化的最近鄰點(diǎn)法和最近插入法的求解步驟。7．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。本單元知識(shí)點(diǎn)能力點(diǎn)、素質(zhì)點(diǎn)能力點(diǎn)：1．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最短路問題，并能夠熟練運(yùn)用Dijkstra算法求解。2．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最大流問題，并能熟練運(yùn)用標(biāo)號(hào)算法求解。3．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最小樹問題，并能熟練運(yùn)用逐步生長(zhǎng)法求解。4．能夠把相應(yīng)的實(shí)際問題歸結(jié)為回路運(yùn)輸路線優(yōu)化問題，并能熟練運(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ǎng)絡(luò)（通過各段線路所需的時(shí)間、距離或費(fèi)用為已知）中，有一貨物發(fā)點(diǎn)（供應(yīng)點(diǎn)）對(duì)一貨物收點(diǎn)（客戶）專門送貨，在這種直送情況下找出貨物運(yùn)送所需的最少時(shí)間、最短距離或最少費(fèi)用的路徑問題。二、最短路的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)度。現(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)說明點(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á)到最小，就都找出來。設(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)間的距離加起來，從所有這些和中選出一個(gè)最小的來。再找出最小和對(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）v1v2v3v4v5v6v75276224713626057710二、最短路的Dijkstra算法★最短路問題在物流規(guī)劃中處于很重要的地位，關(guān)于最短路問題的實(shí)踐應(yīng)用請(qǐng)看單元六中的一和三的內(nèi)容。模塊六運(yùn)輸路徑規(guī)劃運(yùn)輸路徑規(guī)劃概述應(yīng)用舉例線路選擇的最短路法運(yùn)輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹法車輛配送路線的安排單元四單元三單元二單元一單元六單元五本章知識(shí)點(diǎn)1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義。3．掌握求解最短路問題的Dijkstra算法步驟。4．理解可行流、最大流、增廣鏈的概念。5．掌握求解最大流問題的標(biāo)號(hào)算法步驟。6．理解最小樹、圖的中心和重心的含義。7．掌握最小樹問題的逐步生長(zhǎng)法步驟。8．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。9．掌握單回路路線優(yōu)化的最近鄰點(diǎn)法和最近插入法的求解步驟。10．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。本節(jié)知識(shí)點(diǎn)知識(shí)點(diǎn)1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義；掌握求解最短路問題的Dijkstra算法步驟。3．理解可行流、最大流、增廣鏈的概念；掌握求解最大流問題的標(biāo)號(hào)算法步驟。4．理解最小樹、圖的中心和重心的含義；掌握最小樹問題的逐步生長(zhǎng)法步驟。5．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。6．掌握單回路路線優(yōu)化的最近鄰點(diǎn)法和最近插入法的求解步驟。7．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。本單元知識(shí)點(diǎn)能力點(diǎn)、素質(zhì)點(diǎn)能力點(diǎn)：1．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最短路問題，并能夠熟練運(yùn)用Dijkstra算法求解。2．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最大流問題，并能熟練運(yùn)用標(biāo)號(hào)算法求解。3．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最小樹問題，并能熟練運(yùn)用逐步生長(zhǎng)法求解。4．能夠把相應(yīng)的實(shí)際問題歸結(jié)為回路運(yùn)輸路線優(yōu)化問題，并能熟練運(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)+高效物流”和“降本增效”理念。單元三

運(yùn)輸網(wǎng)流量分布的最大流法一、最大流的含義二、最大流的標(biāo)號(hào)算法三、最大流的圖解算法運(yùn)輸網(wǎng)最大流量分布問題：最大流問題的一般提法：一、最大流的含義在已知的物流網(wǎng)絡(luò)（各段線路的通過能力、運(yùn)輸費(fèi)用或運(yùn)輸時(shí)間為已知）中，有一貨物發(fā)點(diǎn)（供應(yīng)點(diǎn)）和一貨物收點(diǎn)（客戶），在這種情況下找出最佳流量安排（線路流量分配）方案，使通過網(wǎng)絡(luò)的流量達(dá)到最大（或運(yùn)輸費(fèi)用最省、或運(yùn)輸時(shí)間最小）。在有一個(gè)起點(diǎn)和一個(gè)終點(diǎn)的網(wǎng)絡(luò)中，最大流問題是企圖找出，在一定時(shí)期內(nèi)，能在起點(diǎn)進(jìn)入，并通過這個(gè)網(wǎng)絡(luò)，在終點(diǎn)輸出的最大流量（不管它是物資、卡車、飛機(jī)、液體或電流）。即最大流問題，就是在一定條件下，要求流過網(wǎng)絡(luò)的流量為最大的問題。一、最大流的含義（一）網(wǎng)絡(luò)流量在一定條件下流過一個(gè)網(wǎng)絡(luò)的總流量，它等于起點(diǎn)的總發(fā)量或終點(diǎn)的總收量。網(wǎng)絡(luò)流量記作

，網(wǎng)絡(luò)邊上的實(shí)際流量記作fij。一、最大流的含義（二）可行

流滿足以下條件的流叫可行流（記為可行流f）：一、最大流的含義（三）最大

流在一個(gè)網(wǎng)絡(luò)中，流量達(dá)到最大值的可行流。求網(wǎng)絡(luò)的最大流，就是指在滿足上述（二）中條件1、2、3的前提下，使的值達(dá)到最大。一、最大流的含義（四）增廣

鏈如果從網(wǎng)絡(luò)的發(fā)點(diǎn)s到收點(diǎn)t能找出一條鏈，在這條鏈上，所有指向?yàn)閟→t的邊（稱為前向邊），其上的流量都小于容量，而所有指向?yàn)閠→s的邊（稱為后向邊），其上的流量都大于0，則稱這樣的鏈為增廣鏈，如圖6-8所示。f45>0f23>0f34<c34v5v3fs2<cs2sv2v4tf5t<c5t圖6-8網(wǎng)絡(luò)中的一條增廣鏈一、最大流的含義（四）增廣

鏈如果從網(wǎng)絡(luò)的發(fā)點(diǎn)s到收點(diǎn)t能找出一條鏈，在這條鏈上，所有指向?yàn)閟→t的邊（稱為前向邊），其上的流量都小于容量，而所有指向?yàn)閠→s的邊（稱為后向邊），其上的流量都大于0，則稱這樣的鏈為增廣鏈，如圖6-8所示。f45>0f23>0f34<c34v5v3fs2<cs2sv2v4tf5t<c5t圖6-8網(wǎng)絡(luò)中的一條增廣鏈二、最大流的標(biāo)號(hào)算法1先給發(fā)點(diǎn)s標(biāo)號(hào)

，其中s是發(fā)點(diǎn)，此前還沒有已標(biāo)號(hào)點(diǎn)，所以給s標(biāo)的第一個(gè)記號(hào)是0，第二個(gè)記號(hào)

可取∞。2找出和已標(biāo)號(hào)點(diǎn)i相鄰的所有未標(biāo)號(hào)點(diǎn)，比如j。二、最大流的標(biāo)號(hào)算法3重復(fù)步驟2，可能出現(xiàn)兩種結(jié)局：（1）標(biāo)號(hào)過程中斷，即t得不到標(biāo)號(hào)，這表明該網(wǎng)絡(luò)中不存在增廣鏈，此時(shí)的可行流已是最大流，計(jì)算即告結(jié)束。（2）t得到標(biāo)號(hào)，這時(shí)可用反向追蹤法在網(wǎng)絡(luò)中找出一條從s→t的由標(biāo)號(hào)點(diǎn)及相應(yīng)的邊連接而成的增廣鏈，接下去轉(zhuǎn)入步驟4。二、最大流的標(biāo)號(hào)算法5抹掉圖上所有標(biāo)號(hào)，重復(fù)第1到第4步，直到圖中找不出任何增廣鏈，即出現(xiàn)第3步的結(jié)局（1）為止，這時(shí)，網(wǎng)絡(luò)中的可行流就是最大流。4調(diào)整網(wǎng)絡(luò)中的可行流f的流量：對(duì)增廣鏈上的前向邊，其流量增加

，對(duì)增廣鏈上的后向邊，其流量減少

，增廣鏈以外的邊上的流量不變。這樣得到一個(gè)新的可行流f`。二、最大流的標(biāo)號(hào)算法例6-2

用標(biāo)號(hào)算法求圖6-7中s→t的最大流，圖中邊旁數(shù)字為。9(4)2(0)9(9)6(1)5(5)10(8)5(4)7(5)8(8)sv1v2v3v4t圖6-7二、最大流的標(biāo)號(hào)算法解：1．先給發(fā)點(diǎn)s標(biāo)號(hào)：（0，∞），見圖6-9；圖6-9v4v1(v4，1)(v1，2)v2(s，2)(v3-，1)(v2-，2)(0，∞)s9(4)2(0)9(9)6(1)5(5)10(8)5(4)7(5)8(8)v3t二、最大流的標(biāo)號(hào)算法解：二、最大流的標(biāo)號(hào)算法解：二、最大流的標(biāo)號(hào)算法解：非增廣鏈上所有邊的流量都不變，這樣便得到網(wǎng)絡(luò)的一個(gè)新的可行流，其流量分布情況見圖6-10所示。二、最大流的標(biāo)號(hào)算法圖6-10新可行流的流量分布方案s9(5)2(0)9(9)6(0)5(5)10(9)5(3)7(6)8(8)v1v2v3v4t解：三、最大流的圖解算法圖解算法就是根據(jù)最大流問題的網(wǎng)絡(luò)圖來尋找從

到

所允許流過的最大流量。其具體步驟是：01020304任意選擇從

到

的通路，一般從最外層開始。接著找出該通路中允許通過的最小流量，并給該通路中各邊上安排這個(gè)最小流量。將上述具有最小流量的邊刪去，余下的重新畫出網(wǎng)絡(luò)圖。重復(fù)上述步驟，直到從

到

已無通路時(shí)為止。05將以上所得的通路最小流量值相加，即得該網(wǎng)絡(luò)的最大流量。例6-3某地區(qū)從北到南的交通，平時(shí)是利用高速公路通行的。現(xiàn)在，將有一個(gè)月的時(shí)間因?yàn)楦咚俟芬M(jìn)行路面修理，車輛不能行駛，因此該地區(qū)公路管理部門的工程技術(shù)人員需要查明，穿過該地區(qū)的其它幾條道路，是不是有把握每小時(shí)通過6000輛汽車，這些汽車在正常情況下，是走高速公路通行的。圖6-11所示是穿過該地區(qū)的道路通行情況，每條道路的通行能力用每小時(shí)千輛汽車為單位來表示。各支線每小時(shí)流量能力為：1——2線：6000輛；1——3線：5000輛；1——4線：3000輛；2——5線：4000輛；2——3線：7000輛；3——5線：5000輛；3——4線：3000輛；4——6線：7000輛；5——6線：2000輛；試計(jì)算該地區(qū)的道路通行能力有多大？三、最大流的圖解算法三、最大流的圖解算法3（3）5（0）7（0）3（3）5（3）7（3+3）6（2）1234564（2）2（2）圖6-11該地區(qū)汽車通過能力的計(jì)算解：該問題實(shí)質(zhì)就是求解圖6-11的最大流問題。計(jì)算過程如下：1．任意選擇從起點(diǎn)到終點(diǎn)的第一條路線（即增廣鏈）。這里，選擇路線1-2-5-6。該路線上支線5-6的流量能力最小，為每小時(shí)2000輛，用2表示。因此該路線的每小時(shí)的最大流量是2000輛。給該路線上每條支線安排流量2000輛，圖中線路旁的數(shù)字為

，見圖6-11所示。支線5-6已無剩余能力，從圖中劃掉。三、最大流的圖解算法解：

2．另選第二條從起點(diǎn)到終點(diǎn)的路線，如1-4-6。該路線上支線1-4的流量能力最小，其最小流量能力為3。因此第二條路線的最大流量是3。給該路線上每條支線安排流量3，見圖6-11所示。支線1-4已無剩余能力，從圖中劃掉。3．另選第三條從起點(diǎn)到終點(diǎn)的路線，如1-3-4-6。該路線上支線3-4的流量能力最小，其最小流量能力為3。因此第三條路線的最大流量是3。給該路線上每條支線安排流量3，見圖6-11所示。支線3-4已無剩余能力，從圖中劃掉。三、最大流的圖解算法解：

4．此時(shí)，從起點(diǎn)到終點(diǎn)，已找不到一條連通的路線，也就是說已找不到一條增廣鏈。

這樣，我們已經(jīng)求得了這個(gè)網(wǎng)絡(luò)的最大流量：即第一條路線上的2000輛，第二條路線上的3000輛，第三條路線上的3000輛，共為8000輛。計(jì)算結(jié)果表明，穿過該地區(qū)的幾條路線，要讓每小時(shí)6000輛汽車通過，是綽綽有余的?！镪P(guān)于最大流問題的實(shí)踐應(yīng)用請(qǐng)看第七節(jié)二中的內(nèi)容。三、最大流的圖解算法模塊六運(yùn)輸路徑規(guī)劃運(yùn)輸路徑規(guī)劃概述應(yīng)用舉例線路選擇的最短路法運(yùn)輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹法車輛配送路線的安排單元一單元三單元二單元四單元六單元五知識(shí)點(diǎn)1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義；掌握求解最短路問題的Dijkstra算法步驟。3．理解可行流、最大流、增廣鏈的概念；掌握求解最大流問題的標(biāo)號(hào)算法步驟。4．理解最小樹、圖的中心和重心的含義；掌握最小樹問題的逐步生長(zhǎng)法步驟。5．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。6．掌握單回路路線優(yōu)化的最近鄰點(diǎn)法和最近插入法的求解步驟。7．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。本單元知識(shí)點(diǎn)能力點(diǎn)、素質(zhì)點(diǎn)能力點(diǎn)：1．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最短路問題，并能夠熟練運(yùn)用Dijkstra算法求解。2．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最大流問題，并能熟練運(yùn)用標(biāo)號(hào)算法求解。3．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最小樹問題，并能熟練運(yùn)用逐步生長(zhǎng)法求解。4．能夠把相應(yīng)的實(shí)際問題歸結(jié)為回路運(yùn)輸路線優(yōu)化問題，并能熟練運(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)+高效物流”和“降本增效”理念。單元四線路網(wǎng)布局的最小樹法

一、最小樹的含義

二、最小樹的逐步生長(zhǎng)法

三、最小樹的破圈法1．樹所謂樹（樹圖），就是沒有圈的連通圖。一、最小樹的含義2．部分樹如果樹T是圖G的一個(gè)部分圖，則稱樹T是圖G的部分樹。v2v1v3(a)925v2v1v3(b)95v2v1v3(c)25圖6-12連通圖a與部分樹b、c3．最小樹在賦權(quán)圖中，構(gòu)成其部分樹各邊權(quán)的總和稱為部分樹的權(quán)，如圖6-12（b）對(duì)應(yīng)的部分樹的權(quán)為14，6-12（c）為7。具有最小權(quán)的部分樹，稱為最小部分樹，簡(jiǎn)稱最小樹。一、最小樹的含義二、最小樹的逐步生長(zhǎng)法例6-4

某天然氣公司計(jì)劃在如圖6-13(a)所示的網(wǎng)絡(luò)中鋪設(shè)天然氣管道，向五個(gè)居民小區(qū)v1、v2、v3、v4、v5

供氣，網(wǎng)絡(luò)中各邊的權(quán)代表相應(yīng)小區(qū)之間所鋪設(shè)天然氣管道的實(shí)際長(zhǎng)度（公里）。試問：應(yīng)如何鋪設(shè)管道，既能保證向五個(gè)居民小區(qū)供應(yīng)天然氣，又能使管道的總長(zhǎng)度最短從而使費(fèi)用最??？v1v2v3v5v45613849109圖6－13(a)二、最小樹的逐步生長(zhǎng)法解：1．先將圖6-13所示網(wǎng)絡(luò)圖列出相應(yīng)的矩陣。二、最小樹的逐步生長(zhǎng)法2．從v1出發(fā)，于是除去D中的v1列，保留v1

行做圖表F（1），如圖6-14所示。956V4V3V5V3V4V5∞994V2V3V4V4V5F(1)V1V1V1V1∞85F(2)V1V2V198V5F(3)V2V39V5F(4)V22行V4V51063行V5134行圖6-14逐步生長(zhǎng)法求解過程圖6-14逐步生長(zhǎng)法求解過程二、最小樹的逐步生長(zhǎng)法3．在F（1）左部上面一行中，填寫v1行的元素值；而下面一行中全部填寫v1

，表示上面一行的數(shù)值全部來自v1

行。然后，在F（1）左部上面一行找出最小值4，即由v1點(diǎn)

到v2點(diǎn)

的距離d12=4為最小，因此把4圈起來，說明可以從v1點(diǎn)

到v2點(diǎn)

鋪設(shè)一條管道，記作

。接著，除去D的第二列（v2列）元素，保留第二行余下的元素做F（1）右面部分的副表。二、最小樹的逐步生長(zhǎng)法二、最小樹的逐步生長(zhǎng)法最后，可按最小樹鋪設(shè)管道，其距離總長(zhǎng)為：4+5+6+9=24為最短，圖6-13（b）所示為最小樹示意圖。圖6-14（b）三、最小樹的破圈法破圈法在連通圖G中任意選取一個(gè)回路，從該回路中去掉一條權(quán)數(shù)最大的邊（如果權(quán)數(shù)最大的邊不唯一，則任意選取其中一條）。在余下的圖中，重復(fù)這一步驟，直到得到一個(gè)不含回路的連通圖（有n個(gè)頂點(diǎn)、n-1條邊），該連通圖便是最小部分樹。三、最小樹的破圈法例6-5如圖6-15所示，A、B、C、D、E、F、G代表某集團(tuán)公司及下屬的工廠，它們之間的連線代表彼此之間的道路交通情況，連線旁的數(shù)字代表相應(yīng)道路的長(zhǎng)度?，F(xiàn)在要沿道路鋪設(shè)通訊電纜，使公司、各工廠彼此之間都能通上電話，問應(yīng)如何鋪設(shè)才能使線路總長(zhǎng)度最短。ABEDCG7564F5289783圖6-16三、最小樹的破圈法解：用破圈法求解該問題的過程和結(jié)果分別見圖6-16，6-17，6-18所示，鋪設(shè)線路的最短長(zhǎng)度是8+2+5+4+3+7=29，其中，打×的邊是找出某個(gè)圈后決定去掉的邊。ABEDCG7564F5289783AEDCG54F2873B圖6-17求解過程圖6-18求解結(jié)果模塊六運(yùn)輸路徑規(guī)劃運(yùn)輸路徑規(guī)劃概述應(yīng)用舉例線路選擇的最短路法運(yùn)輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹法車輛配送路線的安排單元四單元三單元二單元一單元六單元五知識(shí)點(diǎn)1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義；掌握求解最短路問題的Dijkstra算法步驟。3．理解可行流、最大流、增廣鏈的概念；掌握求解最大流問題的標(biāo)號(hào)算法步驟。4．理解最小樹、圖的中心和重心的含義；掌握最小樹問題的逐步生長(zhǎng)法步驟。5．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。6．掌握單回路路線優(yōu)化的最近鄰點(diǎn)法和最近插入法的求解步驟。7．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。本單元知識(shí)點(diǎn)能力點(diǎn)、素質(zhì)點(diǎn)能力點(diǎn)：1．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最短路問題，并能夠熟練運(yùn)用Dijkstra算法求解。2．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最大流問題，并能熟練運(yùn)用標(biāo)號(hào)算法求解。3．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最小樹問題，并能熟練運(yùn)用逐步生長(zhǎng)法求解。4．能夠把相應(yīng)的實(shí)際問題歸結(jié)為回路運(yùn)輸路線優(yōu)化問題，并能熟練運(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)+高效物流”和“降本增效”理念。單元五車輛配送路線的安排一、單車配送路線優(yōu)化的啟發(fā)式算法二、多車配送路線優(yōu)化的啟發(fā)式算法車輛配送路線優(yōu)化問題：?jiǎn)我慌渌蛙囕v的路線安排：一、單車配送路線優(yōu)化的啟發(fā)式算法對(duì)一系列裝貨點(diǎn)和卸貨點(diǎn)，組織適當(dāng)?shù)男熊嚲€路，使車輛有序地通過它們，在滿足一定的約束條件下（如需求量、發(fā)送量、交/發(fā)貨時(shí)間、車輛容量、行駛里程、時(shí)間等限制），達(dá)到一定的目標(biāo)（如行程最短、費(fèi)用最小、時(shí)間最少、運(yùn)力最省等）。車輛從倉庫出發(fā)送貨或取貨，遍歷所有的客戶（每個(gè)客戶僅一次）然后返回倉庫，為其選擇一條行駛距離（或時(shí)間、費(fèi)用）最短的路徑。（一）TSP模型TSP模型是單回路運(yùn)輸問題的最為典型的一個(gè)模型，它的全稱是TravelingSalesmanProblem，中文叫做旅行商問題。TSP模型可以如下描述：在給出的一個(gè)n個(gè)頂點(diǎn)網(wǎng)絡(luò)（有向或無向），要求找出一個(gè)包含所有n個(gè)頂點(diǎn)的具有最小耗費(fèi)的環(huán)路。任何一個(gè)包含網(wǎng)絡(luò)中所有n個(gè)頂點(diǎn)的環(huán)路被稱作一個(gè)回路。在旅行商問題中，要設(shè)法找到一條最小耗費(fèi)的回路。對(duì)于大規(guī)模的TSP問題，一般都采用啟發(fā)式算法（根據(jù)人類的經(jīng)驗(yàn)對(duì)無法求得最優(yōu)解的問題，得出一個(gè)可接受/滿意的解，縮短求解時(shí)間）獲得近優(yōu)解。（二）單回路運(yùn)輸線路優(yōu)化的最近鄰點(diǎn)法1．從零點(diǎn)開始，作為整個(gè)回路的起點(diǎn)。2．找到離剛剛加入到回路的上一頂點(diǎn)最近的一個(gè)頂點(diǎn)，并將其加入到回路中。3．重復(fù)步驟二，直到頂點(diǎn)集合A中所有的頂點(diǎn)都加入到回路T中。4．最后，將最后一個(gè)加入的頂點(diǎn)和起點(diǎn)連接起來。最近鄰點(diǎn)法可以由4步完成：（二）單回路運(yùn)輸線路優(yōu)化的最近鄰點(diǎn)法例6-6

現(xiàn)有一個(gè)連通圖，有6個(gè)頂點(diǎn)，它們的距離矩陣如表6-1所示，它們的相對(duì)位置如圖6-18所示，假設(shè)i，j兩點(diǎn)之間的距離是對(duì)稱的。求距離較短的一條回路安排。表6-1-距離矩陣元素V1V2V3V4V5V6V1－1068715V2－5201516V3－1478V4－412V5－6V6－（二）單回路運(yùn)輸線路優(yōu)化的最近鄰點(diǎn)法例6-6圖6-18節(jié)點(diǎn)相對(duì)位置圖6-19最近鄰點(diǎn)法求解結(jié)果（二）單回路運(yùn)輸線路優(yōu)化的最近鄰點(diǎn)法解：先將節(jié)點(diǎn)１加入到回路中，

。從節(jié)點(diǎn)

v1出發(fā)，比較其到節(jié)點(diǎn)2、3、4、5、6的距離，選擇其最小值，加入到回路中。從距離矩陣中可以看到，從

v1節(jié)點(diǎn)到第3個(gè)節(jié)點(diǎn)v3

的距離最小，為6。因此將節(jié)點(diǎn)

加入到回路中，

。

然后從節(jié)點(diǎn)v3出發(fā)，觀察離v3

最近的節(jié)點(diǎn)。這樣就可以將

節(jié)點(diǎn)加入到回路中，（二）單回路運(yùn)輸線路優(yōu)化的最近鄰點(diǎn)法從節(jié)點(diǎn)v2

出發(fā)，觀察離v2最近的節(jié)點(diǎn)。

這樣v5

是最近的點(diǎn)，將

加入到回路中，依次類推，分別再將v4

、v6加入回路中，得到最后的解為：

結(jié)果用圖形表達(dá)，如圖6-19所示；總行駛距離為：

（三）單回路運(yùn)輸線路優(yōu)化的最近插入法1．找到

最小的節(jié)點(diǎn)

，形成一個(gè)子回路，

2．在剩下的節(jié)點(diǎn)中，尋找一個(gè)離子回路中某一節(jié)點(diǎn)最近的節(jié)點(diǎn)vk

。3．在子回路中找到一條?。╥，j），使得增量=最小，然后將節(jié)點(diǎn)vk

插入到vi、vj之間，并將節(jié)點(diǎn)vk加入到子回路中。4．重復(fù)步驟2、3，直到所有的節(jié)點(diǎn)都加入子回路中。最近插入法可以由4步完成：（三）單回路運(yùn)輸線路優(yōu)化的最近插入法例6-7

用最近插入法對(duì)上面的例6-6進(jìn)行求解。這樣，就由節(jié)點(diǎn)v1和v3構(gòu)一個(gè)子回路

，

，如6-20所示。圖6-20由v1和v3構(gòu)成的子回路解：比較表6-2中的從v1

出發(fā)的所有路徑的大小，（三）單回路運(yùn)輸線路優(yōu)化的最近插入法例6-7

用最近插入法對(duì)上面的例6-6進(jìn)行求解。然后考慮剩下的節(jié)點(diǎn)v2、v4

、v5、v6到

和

中某一個(gè)節(jié)點(diǎn)的最小距離：圖6-21由v1、v3和v2構(gòu)成的子回路構(gòu)成一個(gè)新的子回路，

其結(jié)如圖6-21所示。

（三）單回路運(yùn)輸線路優(yōu)化的最近插入法例6-7

用最近插入法對(duì)上面的例6-6進(jìn)行求解。（三）單回路運(yùn)輸線路優(yōu)化的最近插入法例6-7

用最近插入法對(duì)上面的例6-6進(jìn)行求解。（三）單回路運(yùn)輸線路優(yōu)化的最近插入法例6-7

用最近插入法對(duì)上面的例6-6進(jìn)行求解。圖6-22由v1、v5、v3和v2構(gòu)成的子回路圖6-23由最近插入法求得的最終結(jié)果（一）多車配送路線優(yōu)化問題二、多車配送路線優(yōu)化的啟發(fā)式算法多車配送路線優(yōu)化問題的含義：有多個(gè)貨物需求點(diǎn)，已知每個(gè)需求點(diǎn)的需求量及位置，至多用m輛貨車從配送中心倉庫送貨，然后返回，每輛貨車載重量一定，安排貨車行駛路線，要求每條路線不超過車輛載重量和每個(gè)需求點(diǎn)的需求必須且只能由一輛車來滿足，目標(biāo)是使總運(yùn)距最短或總運(yùn)輸費(fèi)用最少。（二）多車配送路線的優(yōu)化原則二、多車配送路線優(yōu)化的啟發(fā)式算法多車配送路線的優(yōu)化原則：（1）同一車輛負(fù)責(zé)相互距離最接近的需求點(diǎn)的貨物配送。（2）行車路線應(yīng)避免交叉且呈凸形。（3）盡可能使用大載重量車輛，減少出車數(shù)量。（4）取貨、送貨混合安排。（5）從距倉庫最遠(yuǎn)的需求點(diǎn)開始設(shè)計(jì)線路。（三）多車配送路線優(yōu)化的掃描法二、多車配送路線優(yōu)化的啟發(fā)式算法掃描法在VRP求解方法中是一種先分群再尋找最佳路線的算法。該方法采用極坐標(biāo)來表示各需求點(diǎn)的區(qū)位，然后任取一需求點(diǎn)為起始點(diǎn)，定其角度為零度，以順時(shí)鐘或逆時(shí)鐘方向，以車容量為限制條件進(jìn)行服務(wù)區(qū)域（需求點(diǎn)群）的分割，再借由TSP模型啟發(fā)式算法進(jìn)行區(qū)域內(nèi)需求點(diǎn)的排序（安排行車路線）。例6-8

某物流公司為其客戶提供取貨服務(wù)，貨物運(yùn)回倉庫集中后，再以更大的批量進(jìn)行長(zhǎng)途發(fā)運(yùn)。所有取貨任務(wù)均由載重量為10噸的貨車完成?，F(xiàn)在有12家客戶有取貨要求，客戶的取貨量、客戶的地理位置坐標(biāo)見表6-2。物流公司倉庫的坐標(biāo)為（19.50，5.56）。試確定一個(gè)合理的取貨方案，要求合理安排車輛，并確定各車輛行駛路線，使總的運(yùn)輸里程最短。表6-2客戶的取貨量（噸）及地理位置客戶123456789101112取貨量3.42.83.152.4232.252.51.82.151.62.6Xi20.018.818.319.118.818.619.519.920.019.518.719.5Yi4.805.175.004.786.425.885.985.935.554.554.555.19（三）多車配送路線優(yōu)化的掃描法解：1．首先，根據(jù)倉庫、客戶的坐標(biāo)位置和客戶取貨量信息，繪制倉庫和客戶的地理位置圖，然后將客戶取貨量標(biāo)注到圖上，如圖6-29所示?？蛻魝}庫1234567891011122.52.25232.83.12.41.61.82.62.153.4圖6-29客戶信息及服務(wù)區(qū)域劃分（三）多車配送路線優(yōu)化的掃描法2．然后，以倉庫為原點(diǎn)，向右水平方向畫一條直線，進(jìn)行逆時(shí)針方向“掃描”，將直線經(jīng)過的客戶貨物裝上貨車，直到裝載的貨物能裝上一輛10噸的貨車上，同時(shí)又不超重。此時(shí)，完成一個(gè)服務(wù)區(qū)域的劃分。3．繼續(xù)逆時(shí)針旋轉(zhuǎn)直線，重復(fù)上述過程，直到所有的客戶都分派有車輛取貨，就完成了一個(gè)服務(wù)區(qū)域的劃分，服務(wù)區(qū)域數(shù)就是需要派的貨車數(shù)。4．在每個(gè)服務(wù)區(qū)域內(nèi)確定到各客戶點(diǎn)的取貨順序，即行車路線安排。行車路線應(yīng)避免交叉且呈凸形。（三）多車配送路線優(yōu)化的掃描法圖6-30所示是優(yōu)化后的一種取貨路線安排方案，共需派3輛貨車，每輛車的行駛路線安排如圖中所示。客戶倉庫1234567891011122.52.25232.83.12.41.61.82.62.153.4圖6-30最優(yōu)車輛調(diào)度和最佳行車路線安排（三）多車配送路線優(yōu)化的掃描法（四）多車配送路線優(yōu)化的節(jié)約法二、多車配送路線優(yōu)化的啟發(fā)式算法節(jié)約里程法核心思想是依次將運(yùn)輸問題中的兩個(gè)回路合并為一個(gè)回路，每次使合并后的總運(yùn)輸距離減小的幅度最大，直到達(dá)到一輛車的裝載限制時(shí)，再進(jìn)行下一輛車的優(yōu)化。利用節(jié)約法確定配送路線的主要出發(fā)點(diǎn)是，根據(jù)配送中心的運(yùn)輸能力和配送中心到各客戶以及各客戶之間的距離來制定使總的車輛運(yùn)輸?shù)膰嵐飻?shù)最小的配送方案。需滿足以下條件；（1）滿足所有用戶的要求；（2）不使任何一輛車超載；（3）每輛車每次出行的總運(yùn)行時(shí)間或行駛里程不超過規(guī)定的上限；（4）滿足用戶收貨時(shí)間要求等。例6-9

某物流公司配送中心負(fù)責(zé)A、B、C、┅、I共9個(gè)客戶的送貨任務(wù)，其運(yùn)輸路線網(wǎng)絡(luò)、配送中心與客戶以及客戶之間的距離如圖6-31所示，圖中連線上的數(shù)字表示公路里程（km），節(jié)點(diǎn)旁括號(hào)內(nèi)的數(shù)字表示客戶每天對(duì)貨物的需求量（t）。配送中心備有2t和4t載重量貨車多部，且貨車每次送貨運(yùn)行里程（從配送中心出發(fā)到返回）不能超過35km，客戶對(duì)貨物送到時(shí)間沒有要求。試確定該配送中心的每天最優(yōu)配送方案，即保證滿足客戶送貨要求，同時(shí)使用的車輛數(shù)和車輛總行駛里程盡可能少。（四）多車配送路線優(yōu)化的節(jié)約法二、多車配送路線優(yōu)化的啟發(fā)式算法倉庫PCIBADEFHG(1.6)(1.2)(0.5)(1.7)(0.9)(0.6)(0.9)(1.1)(0.9)444555556677769101014123118圖6-32

配送路線網(wǎng)絡(luò)及客戶需求信息（四）多車配送路線優(yōu)化的節(jié)約法解：1．作運(yùn)輸里程表。計(jì)算配送中心與各需求點(diǎn)以及各需求點(diǎn)之間的最短距離，即計(jì)算網(wǎng)絡(luò)圖中每對(duì)點(diǎn)之間的最短距離，見表所示。PABCDEFGHIP1110967101087A51014182121136B591520201811C41019191716D615161413E9171514F141817G1217H7I（四）多車配送路線優(yōu)化的節(jié)約法解：2．作節(jié)約里程表。由運(yùn)輸里程表，按節(jié)約里程計(jì)算公式，計(jì)算每對(duì)需求點(diǎn)連接后的節(jié)約里程量，編制節(jié)約里程表。ABCDEFGHIA16103000612B14720006C1160000D71000E8000F600G60H8I（四）多車配送路線優(yōu)化的節(jié)約法解：3．作節(jié)約里程排序表。根據(jù)節(jié)約里程表，將每對(duì)點(diǎn)對(duì)應(yīng)的節(jié)約里程量排序，按從大到小順序排列，編制節(jié)約里程排序表。排序號(hào)連接點(diǎn)節(jié)約里程排序號(hào)連接點(diǎn)節(jié)約里程排序號(hào)連接點(diǎn)節(jié)約里程1A-B166H-I810F-G62B-C148B-D710G-H63A-I128D-E715A-D34C-D1110A-H616B-E25A-C1010B-I617D-F16E-F810C-E6（四）多車配送路線優(yōu)化的節(jié)約法解：4．安排配送路線。根據(jù)節(jié)約里程排序表、配送車輛的載重和容積因素、車輛行駛里程等約束條件，逐一將符合條件的需求點(diǎn)合并到一條線路上，按需求點(diǎn)接入順序逐步繪出配送線路。重復(fù)這個(gè)過程，直到所有的需求點(diǎn)都被合并到各自的配送線路上為止。（四）多車配送路線優(yōu)化的節(jié)約法倉庫PCIBADEFHG(1.6)(1.2)(0.5)(1.7)(0.9)(0.6)(0.9)(1.1)(0.9)445555666910101233線路①線路②線路③圖6-33

優(yōu)化后的配送路線方案（四）多車配送路線優(yōu)化的節(jié)約法線路①：安排一輛4t車，配送路線及送貨順序：P→I→A→B→C→P,行程32km，載貨量3.7t；線路②：安排一輛4t車，配送路線及順序：P→D→E→F→P,行程31km，載貨量3.9t；線路③：安排一輛2t車，配送路線及順序：P→G→H→P,行程30km，載貨量1.8t?？偣残旭偫锍?3km，與向客戶分別單獨(dú)送貨的方案相比，共節(jié)約里程：（16+14+12）+（8+7）+6=63km。（四）多車配送路線優(yōu)化的節(jié)約法模塊六運(yùn)輸路徑規(guī)劃運(yùn)輸路徑規(guī)劃概述應(yīng)用舉例線路選擇的最短路法運(yùn)輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹法車輛配送路線的安排單元四單元三單元二單元六單元一單元五知識(shí)點(diǎn)1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義；掌握求解最短路問題的Dijkstra算法步驟。3．理解可行流、最大流、增廣鏈的概念；掌握求解最大流問題的標(biāo)號(hào)算法步驟。4．理解最小樹、圖的中心和重心的含義；掌握最小樹問題的逐步生長(zhǎng)法步驟。5．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。6．掌握單回路路線優(yōu)化的最近鄰點(diǎn)法和最近插入法的求解步驟。7．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。能力點(diǎn)、素質(zhì)點(diǎn)能力點(diǎn)：1．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最短路問題，并能夠熟練運(yùn)用Dijkstra算法求解。2．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最大流問題，并能熟練運(yùn)用標(biāo)號(hào)算法求解。3．能夠把相應(yīng)的實(shí)際問題歸結(jié)為最小樹問題，并能熟練運(yùn)用逐步生長(zhǎng)法求解。4．能夠把相應(yīng)的實(shí)際問題歸結(jié)為回路運(yùn)輸路線優(yōu)化問題，并能熟練運(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)+高效物流”和“降本增效”理念。單元六應(yīng)用舉例一、車輛運(yùn)輸路線選擇二、運(yùn)輸網(wǎng)送貨能力分析三、運(yùn)輸網(wǎng)絡(luò)中心和重心確定四、配送路線安排及效益評(píng)估一、車輛運(yùn)輸路線選擇王健是一家運(yùn)輸公司的車輛調(diào)度員。他的公司已經(jīng)簽訂了一項(xiàng)運(yùn)輸合同，要把沈陽的一批貨物運(yùn)送到北京附近地區(qū)。王健查看了這兩個(gè)城市之間可選擇的行車路線的地圖，然后繪制了公路網(wǎng)絡(luò)圖，并在每一條公路上標(biāo)出了里程數(shù)（公里），如圖6-33所示。王健的任務(wù)是找出沈陽到北京的最短路線。一、車輛運(yùn)輸路線選擇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)線王健運(yùn)用Dijkstra算法尋找最短路線的過程如下：1．從終點(diǎn)開始逐步逆向推算：與終點(diǎn)10連接的有兩個(gè)點(diǎn)，即9和8，先從9開始計(jì)算。9到10只有一條路線，因此沒有選擇余地，9-10就是最短的路線，它的里程為100，寫在節(jié)點(diǎn)9上方的框中，并注上9-10。同樣8至10也只有一條路線，最短路線為8-10，里程為150，也按相同方式記上。2．再看節(jié)點(diǎn)6：與6連接的只有一個(gè)節(jié)點(diǎn)9，因此最短路線為6-9，6至9的里程為200，而9至終點(diǎn)10的最短里程為100，因此6至終點(diǎn)的最短里程為200+100=300。記入方式同上，方框上注上6-9-10。一、車輛運(yùn)輸路線選擇王健運(yùn)用Dijkstra算法尋找最短路線的過程如下：3．再看節(jié)點(diǎn)5：與5連接的節(jié)點(diǎn)有9、8兩個(gè)，5至9再至終點(diǎn)的最短里程為400+100=500，5至8再至終點(diǎn)的最短里程為250+150=400。400<500，所以5至終點(diǎn)的最短里程為400，寫在節(jié)點(diǎn)5上方的方框中，方框上再注上5-8-10。點(diǎn)7至終點(diǎn)的最短里程為125+150=275。記入格式同上。4．再看節(jié)點(diǎn)4：與4連接的節(jié)點(diǎn)有5、6、7三個(gè)。4至6再到終點(diǎn)的最短里程為200+300=500，4至5再到終點(diǎn)的最短里程為175+400=575，4至7再到終點(diǎn)的最短里程為275+275=550。三個(gè)里程中以500為最小，所以把500寫在節(jié)點(diǎn)4上方的方框中，方框上注上4-6-9-10。一、車輛運(yùn)輸路線選擇王健運(yùn)用Dijkstra算法尋找最短路線的過程如下：用同樣的方法，算出了節(jié)點(diǎn)2到終點(diǎn)的最短里程為600，節(jié)點(diǎn)3到終點(diǎn)的最短里程也為600。記入的格式同上。5．最后看節(jié)點(diǎn)1，與節(jié)點(diǎn)1連接的路線有3條：1至2再到終點(diǎn)的最短里程100+600=700；1至4再到終點(diǎn)的最短里程150+500=650；1至3再到終點(diǎn)的最短里程175+600=775。；三個(gè)里程中以650為最小，這就是從沈陽到北京的最短里程，而對(duì)應(yīng)的最短路線為1-4-6-9-10。如圖6-34中加粗線所示。一、車輛運(yùn)輸路線選擇二、運(yùn)輸網(wǎng)送貨能力分析

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

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

，見圖6-35。2．再選第二條從甲市到乙市的送貨線路，可選：甲→2→4→乙，最多可安排送貨10噸，在圖上作標(biāo)記，見圖6-35。二、運(yùn)輸網(wǎng)送貨能力分析10（5）10411（10）5（5）112