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

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

CONTENTS物流運(yùn)籌方法與工具概述物流決策分析物流資源配置規(guī)劃物流任務(wù)指派運(yùn)輸方案優(yōu)化運(yùn)輸路徑規(guī)劃物流項(xiàng)目計(jì)劃物流需求預(yù)測庫存水平控制模塊六模塊二模塊三模塊四模塊五模塊七模塊八模塊九模塊一模塊六運(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．理解最小樹、圖的中心和重心的含義；掌握最小樹問題的逐步生長法步驟。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)用逐步生長法求解。4．能夠把相應(yīng)的實(shí)際問題歸結(jié)為回路運(yùn)輸路線優(yōu)化問題，并能熟練運(yùn)用最近鄰點(diǎn)法和最近插入法、掃描法、節(jié)約法求解。素質(zhì)點(diǎn)：1．提高對大數(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)化問題：單一配送車輛的路線安排：一、單車配送路線優(yōu)化的啟發(fā)式算法對一系列裝貨點(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)的回路。對于大規(guī)模的TSP問題，一般都采用啟發(fā)式算法（根據(jù)人類的經(jīng)驗(yàn)對無法求得最優(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所示，它們的相對位置如圖6-18所示，假設(shè)i，j兩點(diǎn)之間的距離是對稱的。求距離較短的一條回路安排。表6-1-距離矩陣元素V1V2V3V4V5V6V1－1068715V2－5201516V3－1478V4－412V5－6V6－（二）單回路運(yùn)輸線路優(yōu)化的最近鄰點(diǎn)法例6-6圖6-18節(jié)點(diǎn)相對位置圖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

用最近插入法對上面的例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

用最近插入法對上面的例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

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

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

用最近插入法對上面的例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)行長途發(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ù)字表示客戶每天對貨物的需求量（t）。配送中心備有2t和4t載重量貨車多部，且貨車每次送貨運(yùn)行里程（從配送中心出發(fā)到返回）不能超過35km，客戶對貨物送到時(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ò)圖中每對點(diǎn)之間的最短距離，見表所示。PABCDEFGHIP1110967101087A51014182121136B591520201811C41019191716D615161413E9171514F141817G1217H7I（四）多車配送路線優(yōu)化的節(jié)約法解：2．作節(jié)約里程表。由運(yùn)輸里程表，按節(jié)約里程計(jì)算公式，計(jì)算每對需求點(diǎn)連接后的節(jié)約里程量，編制節(jié)約里程表。ABCDEFGHIA16103000612B14720006C1160000D71000E8000F600G60H8I（四）多車配送路線優(yōu)化的節(jié)約法解：3．作節(jié)約里程排序表。根據(jù)節(jié)約里程表，將每對點(diǎn)對應(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-E2