《物流運籌方法與工具》第3版 課件 模塊六單元五 車輛配送路線的安排

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

CONTENTS物流運籌方法與工具概述物流決策分析物流資源配置規(guī)劃物流任務指派運輸方案優(yōu)化運輸路徑規(guī)劃物流項目計劃物流需求預測庫存水平控制模塊六模塊二模塊三模塊四模塊五模塊七模塊八模塊九模塊一模塊六運輸路徑規(guī)劃運輸路徑規(guī)劃概述應用舉例線路選擇的最短路法運輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹法車輛配送路線的安排單元四單元三單元二單元一單元六單元五知識點1．理解圖、網(wǎng)絡、鏈、連通圖、圖模型的概念。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)+高效物流”和“降本增效”理念。單元五車輛配送路線的安排一、單車配送路線優(yōu)化的啟發(fā)式算法二、多車配送路線優(yōu)化的啟發(fā)式算法車輛配送路線優(yōu)化問題：單一配送車輛的路線安排：一、單車配送路線優(yōu)化的啟發(fā)式算法對一系列裝貨點和卸貨點，組織適當?shù)男熊嚲€路，使車輛有序地通過它們，在滿足一定的約束條件下（如需求量、發(fā)送量、交/發(fā)貨時間、車輛容量、行駛里程、時間等限制），達到一定的目標（如行程最短、費用最小、時間最少、運力最省等）。車輛從倉庫出發(fā)送貨或取貨，遍歷所有的客戶（每個客戶僅一次）然后返回倉庫，為其選擇一條行駛距離（或時間、費用）最短的路徑。（一）TSP模型TSP模型是單回路運輸問題的最為典型的一個模型，它的全稱是TravelingSalesmanProblem，中文叫做旅行商問題。TSP模型可以如下描述：在給出的一個n個頂點網(wǎng)絡（有向或無向），要求找出一個包含所有n個頂點的具有最小耗費的環(huán)路。任何一個包含網(wǎng)絡中所有n個頂點的環(huán)路被稱作一個回路。在旅行商問題中，要設法找到一條最小耗費的回路。對于大規(guī)模的TSP問題，一般都采用啟發(fā)式算法（根據(jù)人類的經(jīng)驗對無法求得最優(yōu)解的問題，得出一個可接受/滿意的解，縮短求解時間）獲得近優(yōu)解。（二）單回路運輸線路優(yōu)化的最近鄰點法1．從零點開始，作為整個回路的起點。2．找到離剛剛加入到回路的上一頂點最近的一個頂點，并將其加入到回路中。3．重復步驟二，直到頂點集合A中所有的頂點都加入到回路T中。4．最后，將最后一個加入的頂點和起點連接起來。最近鄰點法可以由4步完成：（二）單回路運輸線路優(yōu)化的最近鄰點法例6-6

現(xiàn)有一個連通圖，有6個頂點，它們的距離矩陣如表6-1所示，它們的相對位置如圖6-18所示，假設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．重復步驟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）行車路線應避免交叉且呈凸形。（3）盡可能使用大載重量車輛，減少出車數(shù)量。（4）取貨、送貨混合安排。（5）從距倉庫最遠的需求點開始設計線路。（三）多車配送路線優(yōu)化的掃描法二、多車配送路線優(yōu)化的啟發(fā)式算法掃描法在VRP求解方法中是一種先分群再尋找最佳路線的算法。該方法采用極坐標來表示各需求點的區(qū)位，然后任取一需求點為起始點，定其角度為零度，以順時鐘或逆時鐘方向，以車容量為限制條件進行服務區(qū)域（需求點群）的分割，再借由TSP模型啟發(fā)式算法進行區(qū)域內(nèi)需求點的排序（安排行車路線）。例6-8

某物流公司為其客戶提供取貨服務，貨物運回倉庫集中后，再以更大的批量進行長途發(fā)運。所有取貨任務均由載重量為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客戶信息及服務區(qū)域劃分（三）多車配送路線優(yōu)化的掃描法2．然后，以倉庫為原點，向右水平方向畫一條直線，進行逆時針方向“掃描”，將直線經(jīng)過的客戶貨物裝上貨車，直到裝載的貨物能裝上一輛10噸的貨車上，同時又不超重。此時，完成一個服務區(qū)域的劃分。3．繼續(xù)逆時針旋轉(zhuǎn)直線，重復上述過程，直到所有的客戶都分派有車輛取貨，就完成了一個服務區(qū)域的劃分，服務區(qū)域數(shù)就是需要派的貨車數(shù)。4．在每個服務區(qū)域內(nèi)確定到各客戶點的取貨順序，即行車路線安排。行車路線應避免交叉且呈凸形。（三）多車配送路線優(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ǎng)絡、配送中心與客戶以及客戶之間的距離如圖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)絡及客戶需求信息（四）多車配送路線優(yōu)化的節(jié)約法解：1．作運輸里程表。計算配送中心與各需求點以及各需求點之間的最短距離，即計算網(wǎng)絡圖中每對點之間的最短距離，見表所示。PABCDEFGHIP1110967101087A51014182121136B591520201811C41019191716D615161413E9171514F141817G1217H7I（四）多車配送路線優(yōu)化的節(jié)約法解：2．作節(jié)約里程表。由運輸里程表，按節(jié)約里程計算公式，計算每對需求點連接后的節(jié)約里程量，編制節(jié)約里程表。ABCDEFGHIA16103000612B14720006C1160000D71000E8000F600G60H8I（四）多車配送路線優(yōu)化的節(jié)約法解：3．作節(jié)約里程排序表。根據(jù)節(jié)約里程表，將每對點對應的節(jié)約里程量排序，按從大到小順序排列，編制節(jié)約里程排序表。排序號連接點節(jié)約里程排序號連接點節(jié)約里程排序號連接點節(jié)約里程1A-B166H-I810F-G62B-C148B-D710G-H63A-I128D-E715A-D34C-D1110A-H616B-E2