節(jié)約里程法課件

節(jié)約里程法節(jié)約里程法1一、配送線路的優(yōu)化方法㈠一對(duì)一配送的最短路線問(wèn)題示例：求1-6的最短距離。供應(yīng)商客戶(hù)配送線路的優(yōu)化一、配送線路的優(yōu)化方法㈠一對(duì)一配送的最短路線問(wèn)題供應(yīng)商客戶(hù)配2首先求出從1出發(fā)的一條最短路徑（1-2：4），求次短路徑（2-5：2），

依次類(lèi)推：（5-6：8），

（5-4-6：7），

（5-4-3-6：6），最短距離

求得的最短路徑是：1-2-5-4-3-6

距離是：4+2+6=12首先求出從1出發(fā)的一條最短路徑（1-2：4），求次短路徑（23㈡一對(duì)多配送的最短路線問(wèn)題一、配送線路的優(yōu)化方法配送線路的優(yōu)化㈡一對(duì)多配送的最短路線問(wèn)題一、配送線路的優(yōu)化方法配送線路的優(yōu)4節(jié)約里程法

原理：三角形一邊之長(zhǎng)必定小于另外兩邊之和。在汽車(chē)載重量允許的情況下，采用巡回發(fā)貨比采用往返發(fā)貨可節(jié)約汽車(chē)走行里程為：?L=[2(L1+L2)]-(L1+L2+L3)=L1+L2-L3節(jié)約里程法原理：三角形一邊之長(zhǎng)必定小于另外兩邊之和。在汽車(chē)5節(jié)約里程法的基本規(guī)定

利用里程節(jié)約法確定配送路線的主要出發(fā)點(diǎn)是，根據(jù)配送方的運(yùn)輸能力及其到客戶(hù)之間的距離和各客戶(hù)之間的相對(duì)距離來(lái)制定使配送車(chē)輛總的周轉(zhuǎn)量達(dá)到或接近最小的配送方案。節(jié)約里程法的基本規(guī)定利用里程節(jié)約法確定配送路6節(jié)約里程法應(yīng)用案例

某連鎖零售店，下設(shè)有一個(gè)配送中心P和10個(gè)連鎖分店A～J，配送中心和各連鎖分店及各連鎖分店之間的位置關(guān)系如下圖1所示，兩點(diǎn)間連線上的數(shù)字為兩點(diǎn)間的路線長(zhǎng)度（單位：公里）。各連鎖分店對(duì)某種商品的需求量見(jiàn)表1，該商品由配送中心統(tǒng)一采購(gòu)并進(jìn)行配送。配送中心備用2t和4t的貨車(chē)，限定送貨車(chē)輛一次巡回距離不超過(guò)35公里，設(shè)送到時(shí)間均符合用戶(hù)要求，求配送中心的最優(yōu)送貨方案。節(jié)約里程法應(yīng)用案例某連鎖零售店，下設(shè)有一個(gè)配送中7圖1配送網(wǎng)絡(luò)圖圖1配送網(wǎng)絡(luò)圖8

表1各連鎖分店需求量重量單位：噸用節(jié)約里程法進(jìn)行求解，其步驟如下：第一步：從配送網(wǎng)絡(luò)圖中計(jì)算出配送中心至各連鎖分店及各連鎖分店之間的最短距離，并做出最短距離表（見(jiàn)表2）。

9表2最短距離表表2最短距離表10

第二步：由最短距離表，利用“節(jié)約里程”法計(jì)算出各連鎖分店之間的節(jié)約里程，做出節(jié)約里程表（見(jiàn)表3），計(jì)算結(jié)果有正有負(fù)，節(jié)約里程為負(fù)數(shù)時(shí)，無(wú)實(shí)際意義，在表內(nèi)寫(xiě)0。表3節(jié)約里程表第二步：由最短距離表，利用“節(jié)約里程”法計(jì)算出各連鎖分11節(jié)約里程法ppt課件12

第三步：將節(jié)約里程由大到小順序排列，列出節(jié)約里程排序表（見(jiàn)表4），以便盡量使節(jié)約里程最多的點(diǎn)組合裝車(chē)配送。第三步：將節(jié)約里程由大到小順序排列，列出節(jié)約里程排序13

第四步：根據(jù)節(jié)約里程排序表和配送車(chē)輛載重及行駛里程等約束條件，漸近繪出如圖2所示的配送路線圖。

圖2配送路線圖從配送路線圖可看出，依次確定的三條配送路線均符合配送中心的約束條件，需要2t貨車(chē)3輛，總走行里程為70km，若簡(jiǎn)單地每個(gè)連鎖分店送貨，需要2t貨車(chē)10輛，走行總里程148km。第四步：根據(jù)節(jié)約里程排序表和配送車(chē)輛載重及行駛里程等約14案例分析例：某一配送中心p0向10個(gè)客戶(hù)pj(j=1,2,…,10)配送貨物，其配送網(wǎng)絡(luò)如圖11-9所示。圖中括號(hào)內(nèi)的數(shù)字表示客戶(hù)的需求量（T），線路上的數(shù)字表示兩節(jié)點(diǎn)之間的距離。配送中心有2t和4t兩種車(chē)輛可供使用，試制定最優(yōu)的配送方案。案例分析例：某一配送中心p0向10個(gè)客戶(hù)pj(j=1,2,…15節(jié)約里程法ppt課件16第一步：計(jì)算最短距離。根據(jù)配送網(wǎng)絡(luò)中的已知條件，計(jì)算配送中心與客戶(hù)及客戶(hù)之間的最短距離，結(jié)果見(jiàn)表11-11。第二步：計(jì)算節(jié)約里程sij,結(jié)果見(jiàn)表11-12。第一步：計(jì)算最短距離。根據(jù)配送網(wǎng)絡(luò)中的已知條件，計(jì)算配送中心17第三步：將節(jié)約sij,進(jìn)行分類(lèi)，按從大到小的順序排列，得表11-13第三步：將節(jié)約sij,進(jìn)行分類(lèi)，按從大到小的順序排列，得表118第四步：確定配送線路。從分類(lèi)表中，按節(jié)約里程大小順序，組成線路圖第四步：確定配送線路。從分類(lèi)表中，按節(jié)約里程大小順序，組成線19（1）初始方案：對(duì)每一客戶(hù)分別單獨(dú)派車(chē)送貨，結(jié)果如圖11-10。

（1）初始方案：對(duì)每一客戶(hù)分別單獨(dú)派車(chē)送貨，結(jié)果如圖11-120修正方案4

修正方案421第四節(jié)配送路線設(shè)計(jì)

一、配送路線選擇問(wèn)題

物流中心在組織貨物配送時(shí)，有n個(gè)客戶(hù)，處在同一城市不同地區(qū)，如何取定最佳的配送路線？ 例題：如圖8-1所示的運(yùn)輸網(wǎng)絡(luò)，試求出最優(yōu)路線。

V1V2V7V4V3V6V55712481296910109圖8-1V1V2V7V4V3V6V55712481296910109圖8-2第四節(jié)配送路線設(shè)計(jì)一、配送路線選擇問(wèn)題V1V2V722

解：圖中頂點(diǎn)V2，V4，V5，V7為奇數(shù)頂點(diǎn)，要使它成為歐拉圖，需用加重復(fù)邊的方法使這四個(gè)頂點(diǎn)變?yōu)榕即雾旤c(diǎn)。選擇在（V2，V5）（V4，V7）上加重復(fù)邊，得到的初始方案示于圖8-2中，圈（V2,V5,V4,V7,V2）中，重復(fù)邊總權(quán)為9+4=13，非重復(fù)邊總權(quán)為5+7=12，所以此方案不滿足最優(yōu)條件，需繼續(xù)調(diào)整。調(diào)整時(shí)在不滿足條件的圈中，將重復(fù)邊與非重復(fù)邊對(duì)換，即將重復(fù)邊由（V2，V5）（V4，V7）換成（V2，V7）（V4，V5），得到圖8-3。經(jīng)檢驗(yàn)所有圈均滿足最優(yōu)條件，即得最優(yōu)路線。V1V2V7V4V3V6V55712481296910109圖8-3解：圖中頂點(diǎn)V2，V4，V5，V7為奇數(shù)頂點(diǎn)23二、簡(jiǎn)單配送路線設(shè)計(jì)例題：在一個(gè)配送中心P有一輛載重量為Q的貨車(chē)，現(xiàn)有N個(gè)客戶(hù)需要配送，已知用戶(hù)i的需求量是Gi（i=1,2,3……,n），且≤Q，求在滿足各個(gè)用戶(hù)需求的條件下，總運(yùn)送路程最短的路線，即為簡(jiǎn)單配送路線問(wèn)題。其求解思路是把配送中心也作為一個(gè)用戶(hù)點(diǎn)，這樣就把問(wèn)題轉(zhuǎn)化為n+1個(gè)點(diǎn)的旅行商問(wèn)題。例表8-4給出了配送中心P（標(biāo)記為中心0）和7個(gè)用戶(hù)之間的距離，求最短配送路線？

二、簡(jiǎn)單配送路線設(shè)計(jì)24此類(lèi)問(wèn)題的解法是運(yùn)用節(jié)約算法求解最優(yōu)路線，節(jié)約算法又稱(chēng)C-W算法，是由Clarke和Wright在1964年提出的。它的基本思想是首先把各用戶(hù)單獨(dú)與配送中心相連，構(gòu)成一條僅含以各點(diǎn)的線路。此時(shí)線路距離Z為：然后計(jì)算將點(diǎn)i和j到同一條線路上得到的節(jié)約值：

S(i,j)=C0i+Ci0+C0j+Cj0－(C0i+Cij+Cj0)=Ci0+C0j－Cij或S(j,i)=Cj0+C0i－CjiS(i,j)越大，說(shuō)明把i和j連接在一起時(shí)總路程減少越多。構(gòu)造線路時(shí)，根據(jù)S(i,j)從大道小的順序進(jìn)行，進(jìn)行表上操作，具體步驟如下：第一步，計(jì)算節(jié)約值S(i,j)，并排列成表格形式。第二步在表格種選擇最大的S(i,j)。

此類(lèi)問(wèn)題的解法是運(yùn)用節(jié)約算法求解最優(yōu)路線，節(jié)約算法又25

第三步考察S(i,j)對(duì)應(yīng)的點(diǎn)i和j，檢查是否滿足下列條件。

若點(diǎn)i和j均不在已構(gòu)成的線路上，則可連接點(diǎn)i和j，得到線路段0-i-j-0，轉(zhuǎn)第四步；若點(diǎn)i和j在已構(gòu)成的線路上，但不是線路的內(nèi)點(diǎn)（即不與配送中心0直接相連）。則可以連接，連接后得到線路0…-i-j-0,或0-i-j-…0，轉(zhuǎn)第四步；若點(diǎn)i和j在已構(gòu)成的同一線路上，則不能連接，轉(zhuǎn)第四步；第四步劃去第i行和第j列，即i點(diǎn)不能再到其他點(diǎn)，而點(diǎn)j也不能有其他點(diǎn)到達(dá)；第五步若所有點(diǎn)均被劃去，則已得到完整線路，算法終止；否則，在為劃去的點(diǎn)中選擇最大S(i,j)，轉(zhuǎn)第三步。解得本題最優(yōu)路線為0-2-3-4-6-7-5-1-0。

第三步考察S(i,j)對(duì)應(yīng)的點(diǎn)i和j，檢查是否滿足下26三、理想化的車(chē)輛調(diào)度設(shè)計(jì)例題：現(xiàn)有一配送中心為八個(gè)零售商供貨，各個(gè)零售商的需求量是Gi（噸），這些零售商由配送中心（標(biāo)號(hào)是0）發(fā)出的8噸的載貨車(chē)輛供應(yīng)，具體數(shù)據(jù)如表8-5與8-6所示，把各點(diǎn)之間的距離作為成本考慮的主要因素，即Cij=Dij(i,j=0,1,……，8)，求最優(yōu)的配送路線。表8-6配送中心與零售商之間的距離

三、理想化的車(chē)輛調(diào)度設(shè)計(jì)表8-6配送中心與零售商之間的距離27節(jié)約里程法ppt課件28解：首先計(jì)算節(jié)約值：S(i,j)=C0i+Ci0+C0j+Cj0－(C0i+Cij+Cj0)=Ci0+C0j－CijS(2,8)=C20+C08－C28=60+80－75=65；S（1,3）=C10+C03－C13=40+75－40=75；……按照從大到小的順序得表8-6，然后計(jì)算S(i,j)中，判斷是否連接i和j。最后根據(jù)表8-6~8-8，得到最優(yōu)配送路線：0-6-5-7-0；0-3-1-0；0-2-8-4-0。

解：首先計(jì)算節(jié)約值：29四、配送車(chē)輛優(yōu)化調(diào)度設(shè)計(jì)

配送車(chē)輛優(yōu)化調(diào)度是配送中心向其多個(gè)客戶(hù)配送貨物需要多輛車(chē)，這些車(chē)的類(lèi)型不一樣，運(yùn)輸?shù)呢浳锓N類(lèi)包括食品、日用品和蔬菜等多類(lèi)，調(diào)度優(yōu)化時(shí)希望運(yùn)輸費(fèi)用最省，同時(shí)也希望運(yùn)輸時(shí)間最短的一類(lèi)問(wèn)題，是一個(gè)多車(chē)型、多貨種的送貨滿載車(chē)輛的多目標(biāo)優(yōu)化調(diào)度問(wèn)題。

車(chē)輛的優(yōu)化調(diào)度問(wèn)題是一個(gè)有約束的組合優(yōu)化問(wèn)題，是一個(gè)非確定型的多項(xiàng)式問(wèn)題。此類(lèi)問(wèn)題的解有多個(gè)，隨著其輸入規(guī)模的擴(kuò)大，問(wèn)題的求解難度大大增加，求解的時(shí)間呈幾何級(jí)數(shù)上升。在求解車(chē)輛優(yōu)化調(diào)度問(wèn)題時(shí)，常常將問(wèn)題分解或轉(zhuǎn)化為一個(gè)或幾個(gè)已經(jīng)研究過(guò)的基本問(wèn)題，如旅行商問(wèn)題、最短路徑問(wèn)題、最小費(fèi)用流問(wèn)題、中國(guó)郵遞員問(wèn)題等。再用比較成熟的理論和方法進(jìn)行求解，以得到原車(chē)輛調(diào)度問(wèn)題的最優(yōu)解或滿意解。

采用神經(jīng)網(wǎng)絡(luò)來(lái)求解車(chē)輛調(diào)度問(wèn)題時(shí)一般按下列步驟進(jìn)行：1．產(chǎn)生鄰接矩陣。

2．約束的處理。3．神經(jīng)網(wǎng)絡(luò)計(jì)算。

4．調(diào)度方案的形成。

四、配送車(chē)輛優(yōu)化調(diào)度設(shè)計(jì)30第四節(jié)

配送線路優(yōu)化技術(shù)

一、線路優(yōu)化設(shè)計(jì)的意義配送線路設(shè)計(jì)就是整合影響配送運(yùn)輸?shù)母鞣N因素，適時(shí)適當(dāng)?shù)乩矛F(xiàn)有的運(yùn)輸工具和道路狀況，及時(shí)、安全、方便、經(jīng)濟(jì)地將客戶(hù)所需的商品準(zhǔn)確地送達(dá)客戶(hù)手中。在配送運(yùn)輸線路設(shè)計(jì)中，需根據(jù)不同客戶(hù)群的特點(diǎn)和要求，選擇不同的線路設(shè)計(jì)方法，最終達(dá)到節(jié)省時(shí)間、運(yùn)距和降低配送運(yùn)輸成本的目的第四節(jié)配送線路優(yōu)化技術(shù)一、線路優(yōu)化設(shè)計(jì)的意義31二、直送式配送運(yùn)輸直送式配送運(yùn)輸，是指由一個(gè)供應(yīng)點(diǎn)對(duì)一個(gè)客戶(hù)的專(zhuān)門(mén)送貨BCDK58位勢(shì)法確定最短路線HIJGFAE791081210813611102141146二、直送式配送運(yùn)輸直送式配送運(yùn)輸，是指由一個(gè)供應(yīng)點(diǎn)對(duì)一個(gè)客戶(hù)32尋找最短線路的方法步驟如下：

第一步：選擇貨物供應(yīng)點(diǎn)為初始結(jié)點(diǎn)，并取其位勢(shì)值為“零”即Vi＝０第二步：考慮與I點(diǎn)直接相連的所有線路結(jié)點(diǎn)。第三步：從所得到的所有位勢(shì)值中選出最小者，此值即為從初始結(jié)點(diǎn)到該點(diǎn)的最短距離，將其標(biāo)在該結(jié)點(diǎn)旁的方框內(nèi)，并用箭頭標(biāo)出該聯(lián)線I—J，以此表示從I點(diǎn)到J點(diǎn)的最短線路走法。第四步：重復(fù)以上步驟，直到物流網(wǎng)絡(luò)中所有的結(jié)點(diǎn)的位勢(shì)值均達(dá)到最小為止。最終，各結(jié)點(diǎn)的位勢(shì)值表示從初始結(jié)點(diǎn)到該點(diǎn)的最短距離尋找最短線路的方法步驟如下：33IJGFBCDAHKE58最優(yōu)線路圖61371708152024由供應(yīng)點(diǎn)A到客戶(hù)K的最段距離為24。IJGFBCDAHKE58最優(yōu)線路圖6137170815234二、分送式配送運(yùn)輸

分送式配送是指由一個(gè)供應(yīng)點(diǎn)對(duì)多個(gè)客戶(hù)的共同送貨?；緱l件：同一條線路上所有客戶(hù)的需求量總和不大于一輛車(chē)的額定載重量，送貨時(shí)，由這一輛車(chē)裝著所有客戶(hù)的貨物，沿著一條精心挑選的最佳路線依次將貨物送到各個(gè)客戶(hù)手中，這樣既保證按時(shí)按量將用戶(hù)需要的貨物及時(shí)送到，又節(jié)約了車(chē)輛，節(jié)省了費(fèi)用，緩解了交通緊張的壓力，并減少了運(yùn)輸對(duì)環(huán)境造成的污染。二、分送式配送運(yùn)輸分送式配送是指由一個(gè)供應(yīng)點(diǎn)對(duì)多個(gè)客戶(hù)的共35配送線路的優(yōu)化（一）直送式配送：位勢(shì)法（二）分送式配送：節(jié)約里程法1、節(jié)約里程的基本原理用一輛車(chē)將所有客戶(hù)的貨物裝在一起，沿著一條精心選擇的最佳路線，將貨物送到客戶(hù)手中。目標(biāo)：節(jié)約車(chē)輛、節(jié)約費(fèi)用、緩解交通壓力、減少環(huán)境污染?！鱏=S1+S2-S3配送線路的優(yōu)化362、按節(jié)約里程法制定配送計(jì)劃例有一配送中心（Q）要向10個(gè)用戶(hù)配送，配送距離（公里）和需用量（噸）如下圖所示。假設(shè)：采用最大載重量2噸、4噸、8噸三種汽車(chē)，并限定車(chē)輛一次運(yùn)行距離50公里。用節(jié)約里程法選擇最佳配送路線和車(chē)輛的調(diào)度。2、按節(jié)約里程法制定配送計(jì)劃37配送網(wǎng)絡(luò)圖Q9e1.4861076f1.58g0.6329h0.84i0.510j0.67a0.710b1.59c0.87d0.485544118第一步：選擇初始方案：從Q點(diǎn)向各點(diǎn)分別派車(chē)送貨。配送網(wǎng)絡(luò)圖Q9e1.4861076f1.58g0.6329h38P0109479581410581814968181715137313121011106414131112128210111517181817119P1P2P3P4P5P6P7P8P9P107481315151510118P1P2P3P4P5P6P7P8P9P10

0.71.50.80.41.41.50.60.80.50.6需要量最短距離矩陣

第二步：作出最短距離矩陣，從配送網(wǎng)絡(luò)圖中列出配送中心至用戶(hù)相互間的最短距離矩陣。P0P1P2P3P4P5P6P7P8P9P10P1P2P3P39第三步：從最短矩陣中，計(jì)算用戶(hù)相互間的節(jié)約里程。1581147100361000039000015000004594000125P1P2P3P4P5P6P7P8P9P1P2P3P4P5P6P7P8P9P101381000009節(jié)約里程計(jì)算過(guò)程

第三步：從最短矩陣中，計(jì)算用戶(hù)相互間的節(jié)約里程。1581140第四步：將節(jié)約里程按大小順序排列分類(lèi)。Ⅰa—b15Ⅱa—j13Ⅲb—c11Ⅸf—g5Ⅸg—h5Ⅸh—i5Ⅹa—d4Ⅹb—i4Ⅹf—h4Ⅳc—d10Ⅳd—e10Ⅴa—i9Ⅴe—f9Ⅴi—j9Ⅵa—c8Ⅵb—j8Ⅶb—d7Ⅷc—e6Ⅻg—i2Ⅺb—e3Ⅺd—f3XIIIc—j1XIIIe—g1XIIIf—i1節(jié)約里程順序表分類(lèi)用戶(hù)連接線節(jié)約里程分類(lèi)用戶(hù)連接線節(jié)約里程第四步：將節(jié)約里程按大小順序排列分類(lèi)。Ⅰa—b15Ⅱa—j41第五步：按節(jié)約里程大小順序，組成配送線路。dcaeQfghbji888734544710初始配送路線圖

第五步：按節(jié)約里程大小順序，組成配送線路。dcaeQfgh42按上述方法，逐次選代，優(yōu)化配送線路。dcaQfghbjie5546783729104最佳配送線路

按上述方法，逐次選代，優(yōu)化配送線路。dcaQfghbjie437.2.4節(jié)約里程法基本原理是幾何學(xué)中三角形一邊之長(zhǎng)必定小于另外兩邊之和。往返發(fā)貨與巡回發(fā)貨車(chē)輛行走距離?l=[2(l1+l2)]-(l1+l2+l3)=l1+l2-l37.2.4節(jié)約里程法基本原理是幾何學(xué)中三角形一邊之長(zhǎng)必定44節(jié)約里程法應(yīng)用案例

由配送中心P向A~I等9個(gè)用戶(hù)配送貨物。圖中連線上的數(shù)字表示公路里程（km）?？拷饔脩?hù)括號(hào)內(nèi)的數(shù)字，表示各用戶(hù)對(duì)貨物的需求量（t）。配送中心備有2t和4t載重量的汽車(chē)，且汽車(chē)一次巡回走行里程不能超過(guò)35km，設(shè)送到時(shí)間均符合用戶(hù)要求，求該配送中心的最優(yōu)送貨方案。節(jié)約里程法應(yīng)用案例由配送中心P向A45某配送中心配送網(wǎng)絡(luò)圖某46計(jì)算配送中心至各用戶(hù)以及各用戶(hù)之間的最短距離，列表得最短距離表：計(jì)算配送中心至各用戶(hù)以及各用戶(hù)之間的最短距離，列表得最短距離47PABCDEFGHIPABCDEFGHI11109671010875101418212113659152020181141019191716615161413917151414181712177PABC48由最短距離表，利用節(jié)約法計(jì)算出各用戶(hù)之間的節(jié)約里程，編制節(jié)約里程表：由最短距離表，利用節(jié)約法計(jì)算出各用戶(hù)之間的節(jié)約里程，編制節(jié)約49ABCDEFGHIABCDEFGHI16103000612147200061160000