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

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

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

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

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

表示圖，其中

表示節(jié)點集合，

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

稱為該圖的一個鏈。如圖6-5中的

就是一個鏈。v2v3v4v5e1v1e2e3e4e5e6e7圖6-5連通圖二、圖的概念與模型6．連通圖在一個圖中，若任意兩點之間至少存在一條鏈，則稱該圖為連通圖，否則就稱為不連通圖。圖6-6為不連通圖。圖6-6不連通圖v1v2v3v4v5v6二、圖的概念與模型7．圖模型對要研究的問題確定了具體對象并找出這些對象之間的聯(lián)系后，如果用圖的形式表示出來，就是對研究的問題建立了圖的模型。它是對大量實際問題的抽象和概括。譬如我們在生產(chǎn)和生活中，常見到公路或鐵路交通圖、管網(wǎng)圖、通訊聯(lián)絡(luò)圖等，其中點（車站、自來水廠、通訊臺、用戶等）表示研究對象，邊表示這些對象之間的相互聯(lián)系。模塊六運輸路徑規(guī)劃運輸路徑規(guī)劃概述應(yīng)用舉例線路選擇的最短路法運輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹法車輛配送路線的安排單元四單元三單元一單元二單元六單元五知識點1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義；掌握求解最短路問題的Dijkstra算法步驟。3．理解可行流、最大流、增廣鏈的概念；掌握求解最大流問題的標號算法步驟。4．理解最小樹、圖的中心和重心的含義；掌握最小樹問題的逐步生長法步驟。5．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。6．掌握單回路路線優(yōu)化的最近鄰點法和最近插入法的求解步驟。7．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。本單元知識點能力點、素質(zhì)點能力點：1．能夠把相應(yīng)的實際問題歸結(jié)為最短路問題，并能夠熟練運用Dijkstra算法求解。2．能夠把相應(yīng)的實際問題歸結(jié)為最大流問題，并能熟練運用標號算法求解。3．能夠把相應(yīng)的實際問題歸結(jié)為最小樹問題，并能熟練運用逐步生長法求解。4．能夠把相應(yīng)的實際問題歸結(jié)為回路運輸路線優(yōu)化問題，并能熟練運用最近鄰點法和最近插入法、掃描法、節(jié)約法求解。素質(zhì)點：1．提高對大數(shù)據(jù)及云計算、物聯(lián)網(wǎng)、人工智能等新科技的應(yīng)用興趣，勇于實踐創(chuàng)新。2．加強“互聯(lián)網(wǎng)+高效物流”和“降本增效”理念。單元二線路選擇的最短路法

一、最短路的含義

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

表示從點s到點i的最短路的長度?，F(xiàn)在要求從點s到點t的最短路，相應(yīng)的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ù)字和與之相鄰的點到這個已標號點間的距離加起來，從所有這些和中選出一個最小的來。再找出最小和對應(yīng)的未標號點，然后給這個未標號點比如q標號：Lsq=lsk+dkg,，同時加粗邊[k,q]。二、最短路的Dijkstra算法4重復(fù)第（3）步，直到給點t標上號

，而且相應(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)于最短路問題的實踐應(yīng)用請看單元六中的一和三的內(nèi)容。模塊六運輸路徑規(guī)劃運輸路徑規(guī)劃概述應(yīng)用舉例線路選擇的最短路法運輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹法車輛配送路線的安排單元四單元三單元二單元一單元六單元五本章知識點1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義。3．掌握求解最短路問題的Dijkstra算法步驟。4．理解可行流、最大流、增廣鏈的概念。5．掌握求解最大流問題的標號算法步驟。6．理解最小樹、圖的中心和重心的含義。7．掌握最小樹問題的逐步生長法步驟。8．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。9．掌握單回路路線優(yōu)化的最近鄰點法和最近插入法的求解步驟。10．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。本節(jié)知識點知識點1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義；掌握求解最短路問題的Dijkstra算法步驟。3．理解可行流、最大流、增廣鏈的概念；掌握求解最大流問題的標號算法步驟。4．理解最小樹、圖的中心和重心的含義；掌握最小樹問題的逐步生長法步驟。5．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。6．掌握單回路路線優(yōu)化的最近鄰點法和最近插入法的求解步驟。7．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。本單元知識點能力點、素質(zhì)點能力點：1．能夠把相應(yīng)的實際問題歸結(jié)為最短路問題，并能夠熟練運用Dijkstra算法求解。2．能夠把相應(yīng)的實際問題歸結(jié)為最大流問題，并能熟練運用標號算法求解。3．能夠把相應(yīng)的實際問題歸結(jié)為最小樹問題，并能熟練運用逐步生長法求解。4．能夠把相應(yīng)的實際問題歸結(jié)為回路運輸路線優(yōu)化問題，并能熟練運用最近鄰點法和最近插入法、掃描法、節(jié)約法求解。素質(zhì)點：1．提高對大數(shù)據(jù)及云計算、物聯(lián)網(wǎng)、人工智能等新科技的應(yīng)用興趣，勇于實踐創(chuàng)新。2．加強“互聯(lián)網(wǎng)+高效物流”和“降本增效”理念。單元三

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

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

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

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

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

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

，其中s是發(fā)點，此前還沒有已標號點，所以給s標的第一個記號是0，第二個記號

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

，對增廣鏈上的后向邊，其流量減少

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

用標號算法求圖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二、最大流的標號算法解：1．先給發(fā)點s標號：（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二、最大流的標號算法解：二、最大流的標號算法解：二、最大流的標號算法解：非增廣鏈上所有邊的流量都不變，這樣便得到網(wǎng)絡(luò)的一個新的可行流，其流量分布情況見圖6-10所示。二、最大流的標號算法圖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任意選擇從

到

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

到

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

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

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

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

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

一、最小樹的含義

二、最小樹的逐步生長法

三、最小樹的破圈法1．樹所謂樹（樹圖），就是沒有圈的連通圖。一、最小樹的含義2．部分樹如果樹T是圖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）對應(yīng)的部分樹的權(quán)為14，6-12（c）為7。具有最小權(quán)的部分樹，稱為最小部分樹，簡稱最小樹。一、最小樹的含義二、最小樹的逐步生長法例6-4

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

供氣，網(wǎng)絡(luò)中各邊的權(quán)代表相應(yīng)小區(qū)之間所鋪設(shè)天然氣管道的實際長度（公里）。試問：應(yīng)如何鋪設(shè)管道，既能保證向五個居民小區(qū)供應(yīng)天然氣，又能使管道的總長度最短從而使費用最省？v1v2v3v5v45613849109圖6－13(a)二、最小樹的逐步生長法解：1．先將圖6-13所示網(wǎng)絡(luò)圖列出相應(yī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逐步生長法求解過程圖6-14逐步生長法求解過程二、最小樹的逐步生長法3．在F（1）左部上面一行中，填寫v1行的元素值；而下面一行中全部填寫v1

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

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

到v2點

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

到v2點

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

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

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

。從節(jié)點

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

v1節(jié)點到第3個節(jié)點v3

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

加入到回路中，

。

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

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

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

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

這樣v5

是最近的點，將

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

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

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

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

最小的節(jié)點

，形成一個子回路，

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

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

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

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

，

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

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

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

、v5、v6到

和

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

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

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

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

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

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

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

某物流公司配送中心負責A、B、C、┅、I共9個客戶的送貨任務(wù)，其運輸路線網(wǎng)絡(luò)、配送中心與客戶以及客戶之間的距離如圖6-31所示，圖中連線上的數(shù)字表示公路里程（km），節(jié)點旁括號內(nèi)的數(shù)字表示客戶每天對貨物的需求量（t）。配送中心備有2t和4t載重量貨車多部，且貨車每次送貨運行里程（從配送中心出發(fā)到返回）不能超過35km，客戶對貨物送到時間沒有要求。試確定該配送中心的每天最優(yōu)配送方案，即保證滿足客戶送貨要求，同時使用的車輛數(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．作運輸里程表。計算配送中心與各需求點以及各需求點之間的最短距離，即計算網(wǎng)絡(luò)圖中每對點之間的最短距離，見表所示。PABCDEFGHIP1110967101087A51014182121136B591520201811C41019191716D615161413E9171514F141817G1217H7I（四）多車配送路線優(yōu)化的節(jié)約法解：2．作節(jié)約里程表。由運輸里程表，按節(jié)約里程計算公式，計算每對需求點連接后的節(jié)約里程量，編制節(jié)約里程表。ABCDEFGHIA16103000612B14720006C1160000D71000E8000F600G60H8I（四）多車配送路線優(yōu)化的節(jié)約法解：3．作節(jié)約里程排序表。根據(jù)節(jié)約里程表，將每對點對應(yīng)的節(jié)約里程量排序，按從大到小順序排列，編制節(jié)約里程排序表。排序號連接點節(jié)約里程排序號連接點節(jié)約里程排序號連接點節(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é)約里程排序表、配送車輛的載重和容積因素、車輛行駛里程等約束條件，逐一將符合條件的需求點合并到一條線路上，按需求點接入順序逐步繪出配送線路。重復(fù)這個過程，直到所有的需求點都被合并到各自的配送線路上為止。（四）多車配送路線優(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。總共行駛里程93km，與向客戶分別單獨送貨的方案相比，共節(jié)約里程：（16+14+12）+（8+7）+6=63km。（四）多車配送路線優(yōu)化的節(jié)約法模塊六運輸路徑規(guī)劃運輸路徑規(guī)劃概述應(yīng)用舉例線路選擇的最短路法運輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹法車輛配送路線的安排單元四單元三單元二單元六單元一單元五知識點1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義；掌握求解最短路問題的Dijkstra算法步驟。3．理解可行流、最大流、增廣鏈的概念；掌握求解最大流問題的標號算法步驟。4．理解最小樹、圖的中心和重心的含義；掌握最小樹問題的逐步生長法步驟。5．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。6．掌握單回路路線優(yōu)化的最近鄰點法和最近插入法的求解步驟。7．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。能力點、素質(zhì)點能力點：1．能夠把相應(yīng)的實際問題歸結(jié)為最短路問題，并能夠熟練運用Dijkstra算法求解。2．能夠把相應(yīng)的實際問題歸結(jié)為最大流問題，并能熟練運用標號算法求解。3．能夠把相應(yīng)的實際問題歸結(jié)為最小樹問題，并能熟練運用逐步生長法求解。4．能夠把相應(yīng)的實際問題歸結(jié)為回路運輸路線優(yōu)化問題，并能熟練運用最近鄰點法和最近插入法、掃描法、節(jié)約法求解。素質(zhì)點：1．提高對大數(shù)據(jù)及云計算、物聯(lián)網(wǎng)、人工智能等新科技的應(yīng)用興趣，勇于實踐創(chuàng)新。2．加強“互聯(lián)網(wǎng)+高效物流”和“降本增效”理念。單元六應(yīng)用舉例一、車輛運輸路線選擇二、運輸網(wǎng)送貨能力分析三、運輸網(wǎng)絡(luò)中心和重心確定四、配送路線安排及效益評估一、車輛運輸路線選擇王健是一家運輸公司的車輛調(diào)度員。他的公司已經(jīng)簽訂了一項運輸合同，要把沈陽的一批貨物運送到北京附近地區(qū)。王健查看了這兩個城市之間可選擇的行車路線的地圖，然后繪制了公路網(wǎng)絡(luò)圖，并在每一條公路上標出了里程數(shù)（公里），如圖6-33所示。王健的任務(wù)是找出沈陽到北京的最短路線。一、車輛運輸路線選擇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)線王健運用Dijkstra算法尋找最短路線的過程如下：1．從終點開始逐步逆向推算：與終點10連接的有兩個點，即9和8，先從9開始計算。9到10只有一條路線，因此沒有選擇余地，9-10就是最短的路線，它的里程為100，寫在節(jié)點9上方的框中，并注上9-10。同樣8至10也只有一條路線，最短路線為8-10，里程為150，也按相同方式記上。2．再看節(jié)點6：與6連接的只有一個節(jié)點9，因此最短路線為6-9，6至9的里程為200，而9至終點10的最短里程為100，因此6至終點的最短里程為200+100=300。記入方式同上，方框上注上6-9-10。一、車輛運輸路線選擇王健運用Dijkstra算法尋找最短路線的過程如下：3．再看節(jié)點5：與5連接的節(jié)點有9、8兩個，5至9再至終點的最短里程為400+100=500，5至8再至終點的最短里程為250+150=400。400<500，所以5至終點的最短里程為400，寫在節(jié)點5上方的方框中，方框上再注上5-8-10。點7至終點的最短里程為125+150=275。記入格式同上。4．再看節(jié)點4：與4連接的節(jié)點有5、6、7三個。4至6再到終點的最短里程為200+300=500，4至5再到終點的最短里程為175+400=575，4至7再到終點的最短里程為275+275=550。三個里程中以500為最小，所以把500寫在節(jié)點4上方的方框中，方框上注上4-6-9-10。一、車輛運輸路線選擇王健運用Dijkstra算法尋找最短路線的過程如下：用同樣的方法，算出了節(jié)點2到終點的最短里程為600，節(jié)點3到終點的最短里程也為600。記入的格式同上。5．最后看節(jié)點1，與節(jié)點1連接的路線有3條：1至2再到終點的最短里程100+600=700；1至4再到終點的最短里程150+500=650；1至3再到終點的最短里程175+600=775。；三個里程中以650為最小，這就是從沈陽到北京的最短里程，而對應(yīng)的最短路線為1-4-6-9-10。如圖6-34中加粗線所示。一、車輛運輸路線選擇二、運輸網(wǎng)送貨能力分析

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

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

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