鄧芳敏南京農(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)濟(jì)效益化,實(shí)現(xiàn)物流運(yùn)作科學(xué)化和高效化。而集送貨一體化把配送和集貨兩個(gè)目標(biāo)結(jié)合在一起,統(tǒng)籌安排,能更好達(dá)到成本最小化和效益最大化的根本目的,因此本文針對有集送貨雙重需求，有時(shí)間窗約束的車輛路徑優(yōu)化問題，通過改進(jìn)后的節(jié)約算法實(shí)現(xiàn)了路徑優(yōu)化，同時(shí)對案例進(jìn)行了分析，給出了路徑優(yōu)化方案。

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

一、背景

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

二、研究現(xiàn)狀

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

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

三、研究方法

（一）節(jié)約算法

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

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

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

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

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

表1　各點(diǎn)之間的最短距離 （單位：km）

表2　每個(gè)點(diǎn)的配送量和集貨量表(單位：kg )

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

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

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

1、案例分析

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

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

四、優(yōu)化方案

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

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指每個(gè)客戶點(diǎn)

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

表4　計(jì)算結(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é)約算法達(dá)使得了該配送中心運(yùn)輸成本得以下降，達(dá)到了路徑優(yōu)化的效果。

五、總結(jié)

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

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

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