基于節(jié)約算法的集送貨車輛路徑優(yōu)化研究

鄧芳敏南京農(nóng)業(yè)大學(xué)工學(xué)院 江蘇南京 210031

基于節(jié)約算法的集送貨車輛路徑優(yōu)化研究

鄧芳敏
南京農(nóng)業(yè)大學(xué)工學(xué)院 江蘇南京 210031

車輛路徑問題是物流系統(tǒng)調(diào)度中的關(guān)鍵環(huán)節(jié),它可以使物流經(jīng)濟效益化,實現(xiàn)物流運作科學(xué)化和高效化。而集送貨一體化把配送和集貨兩個目標(biāo)結(jié)合在一起,統(tǒng)籌安排,能更好達到成本最小化和效益最大化的根本目的,因此本文針對有集送貨雙重需求，有時間窗約束的車輛路徑優(yōu)化問題，通過改進后的節(jié)約算法實現(xiàn)了路徑優(yōu)化，同時對案例進行了分析，給出了路徑優(yōu)化方案。

路徑優(yōu)化；節(jié)約算法；集送貨一體化；時間窗約束

一、背景

在物流運輸過程中，運輸成本占了60％，部分產(chǎn)品的運輸成本甚至高于產(chǎn)品的生產(chǎn)成本，因此對配送進行優(yōu)化成為公司降低物流成本，實現(xiàn)自身利益最大化的一個重要方面。而運輸車輛的行車路線是配送優(yōu)化的核心問題，在配送的同時回收貨物是現(xiàn)代物流的發(fā)展方向，因此，一體化集貨與配送的車輛路徑問題（Vehicle Routing Problem with Back-hauls，VRPB)得到了廣泛重視。

二、研究現(xiàn)狀

目前國內(nèi)對于帶集貨送貨車輛路徑規(guī)劃的研究主要有霍佳震，張磊把上述問題分解為兩個階段進行求解:第一階段對每一項任務(wù)內(nèi)部的集貨點與送貨點進行內(nèi)部安排行車路線；第二階段再對各項任務(wù)之間進行外部安排行車路線，以此簡化問題。鐘石泉，賀國光提出一種改進的禁忌算法來解決這類問題。李華建立多目標(biāo)優(yōu)化模型，用混合遺傳算法進行仿真求解。

本文重點討論通過簡單節(jié)約算法進行修正得到的改進型節(jié)約算法，對有集送貨雙重需求，有硬時間窗約束的車輛路徑進行優(yōu)化，并對某案例進行分析，給出優(yōu)化方案。

三、研究方法

（一）節(jié)約算法

節(jié)約算法的基本步驟是先將各客戶點分別與配送中心相連形成初始路線，然后將任意兩客戶點（即i，j）相連并計算節(jié)約值越大，節(jié)約的費用越多。S(i,j)按由大到小排序后，按照S(i,j)排序順序依次連接各點。若連接過程中出現(xiàn)該路線運貨總量超過車輛載重，則不連接這兩點，考慮后面兩點的連接。

本案例增加了集送貨任務(wù)以及硬時間窗要求，要首先判斷各點集送貨量之和有無超過車輛載重Q，如果超出，需要在滿足Q的情況下對該點單獨集送貨，而超出Q的部分再參與計算。

（二）改進的節(jié)約算法

對于時間窗約束有：設(shè)Si為完成任務(wù)i所需的時間，Ti為裝貨或卸貨所需的時間，ETi為i的允許最早開始時間，LTi為i的允許最遲開始時間，則Si需滿足：ETi≤Si≤LTi, S0=0令ti,j為車輛由點i行駛到點j的時間，則到達j點時間的推遲（或提前）量EFj可表示為，則有：EFj<0，提前到達；EFj>0，推遲到達。定義參數(shù)分別為j點的到達時間最大可提前量和最大允許推遲量，則有

其具體步驟如下：(1)形成一個初始解。采取單點配送構(gòu)成各車輛配送點集令(2)計算各客戶點間的距離節(jié)約值S(i,j)及S'(i,j)；(3)按S(i,j)值的上述順序，逐個考察其端點i和j，若滿足以下條件，則轉(zhuǎn)下步，否則，不連接。條件是：1)點i和點j不在一條線路上；2)點i和點j均與基點相鄰。

表1　各點之間的最短距離 （單位：km）

表2　每個點的配送量和集貨量表(單位：kg )

表3　距離節(jié)約值S＇(i,j)（單位：km）

(4)考察點i和點j連接后線路上的總配送量要小于車載量且集貨量之和要小于車載量減去總配送量,則轉(zhuǎn)下步，否則不連接。(5)計算EFj，若滿足弧(i,j)插入到線路中，否則，不連接。(6)計算連接點i和點j后車輛到達各項任務(wù)的新時間，返回步驟(3),直至考察完所有的弧為止。

（三）節(jié)約算法具體應(yīng)用

1、案例分析

本文在符合客戶可接受送達時間的前提下，不考慮運送次序?qū)蛻魸M意度和運輸成本的影響，以贛州YQ農(nóng)產(chǎn)品配送中心為實例并優(yōu)化該配送中心的物流配送路徑，贛州YQ農(nóng)產(chǎn)品配送中心主要給贛州市區(qū)的15個大客戶運送農(nóng)產(chǎn)品，每天一定的時間段進行配送，配送中心目前有4輛車，核定載重量為10噸。每天運輸?shù)乃俣葹?0km/h，由配送中心負責(zé)配送和集貨。A值取0.6。在此情況下為使配送中心自身運輸成本最低，合理規(guī)劃其路徑。本案例取配送中心附近的8個點，配送中心為0點，其他贛州國光超市為1、天虹商場2、鐵龍大酒店3、匯康大酒店4、贛州格蘭云天國際酒店5、江西理工大學(xué)6、贛南醫(yī)學(xué)院7、江西環(huán)境工程學(xué)院8。其各地點的距離以及它們的需求量和配送量如上表所示：

根據(jù)節(jié)約算法的步驟可以得到表3;

四、優(yōu)化方案

贛州YQ農(nóng)產(chǎn)品配送中心的在日常的配送過程中，其農(nóng)產(chǎn)品配送路線計劃主要是依據(jù)駕駛員的配送經(jīng)驗來安排，當(dāng)配送客戶點較少時，此類方法才有一定可行性，但在配送客戶點很多時，這種方法缺乏科學(xué)依據(jù)，可操作性不強，同時存在許多不合理的地方，這時候配送成本會增加很多。贛州YQ農(nóng)產(chǎn)品配送中心，由文獻知贛州YQ農(nóng)產(chǎn)配送中心的原有農(nóng)產(chǎn)品配送計劃和車輛配送對應(yīng)客戶點的實際情況，車輛編號配送線路計劃如下：

1 0一5一3一4一7一6一0 22/2（載重量/集貨量）502（距離km）

2 0一1一0 3 （載重量/集貨量） 64（距離km）

3 0一2一8一0 4 /8（載重量/集貨量） 180（距離km）

注:表中的“0”表示贛州YQ農(nóng)產(chǎn)品配送中心，數(shù)字序號1-8指每個客戶點

通過應(yīng)用節(jié)約算法進行優(yōu)化后，最后得出的結(jié)果如表4

表4　計算結(jié)果表

得出優(yōu)化方案為：

路徑1：農(nóng)產(chǎn)品配送中心 ---贛州格蘭云天國際酒店 ---鐵龍大酒店---江西環(huán)境工程學(xué)院 --- 農(nóng)產(chǎn)品配送中心

路徑2：農(nóng)產(chǎn)品配送中心---江西理工大學(xué)---贛南醫(yī)學(xué)院---農(nóng)產(chǎn)品配送中心

路徑3：農(nóng)產(chǎn)品配送中心---匯康大酒店---贛州國光超市---天虹商場---農(nóng)產(chǎn)品配送中心

通過利用節(jié)約算法達使得了該配送中心運輸成本得以下降，達到了路徑優(yōu)化的效果。

五、總結(jié)

本文從改進C一W節(jié)約算法入手，對有時間窗約束的VRPSDP式進行了研究，提出了以集貨量和送貨量共同作為各客戶點歸并的判斷條件，并與其最短距離結(jié)合其來在規(guī)定的時間將貨物送到以及集貨。案例表明文中所提出的算法實現(xiàn)了路徑優(yōu)化，并節(jié)約了配送中心的運輸費用。

鄧芳敏，（1994—），女，漢，江西，本科，物流工程。

[1]馮芳媛.B2C電子商務(wù)中帶逆向物流的車輛路徑優(yōu)化問題研究[D].沈陽師范大學(xué),2012