基于節約算法的集送貨車輛路徑優化研究

鄧芳敏南京農業大學工學院 江蘇南京 210031

基于節約算法的集送貨車輛路徑優化研究

鄧芳敏
南京農業大學工學院 江蘇南京 210031

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

路徑優化；節約算法；集送貨一體化；時間窗約束

一、背景

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

二、研究現狀

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

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

三、研究方法

（一）節約算法

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

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

（二）改進的節約算法

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

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

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

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

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

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

（三）節約算法具體應用

1、案例分析

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

根據節約算法的步驟可以得到表3;

四、優化方案

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

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農產品配送中心，數字序號1-8指每個客戶點

通過應用節約算法進行優化后，最后得出的結果如表4

表4　計算結果表

得出優化方案為：

路徑1：農產品配送中心 ---贛州格蘭云天國際酒店 ---鐵龍大酒店---江西環境工程學院 --- 農產品配送中心

路徑2：農產品配送中心---江西理工大學---贛南醫學院---農產品配送中心

路徑3：農產品配送中心---匯康大酒店---贛州國光超市---天虹商場---農產品配送中心

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

五、總結

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

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

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