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

鄧芳敏

【摘要】車(chē)輛路徑問(wèn)題是物流系統(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á)到成本最小化和效益最大化的根本目的，因此本文針對(duì)有集送貨雙重需求，有時(shí)間窗約束的車(chē)輛路徑優(yōu)化問(wèn)題，通過(guò)改進(jìn)后的節(jié)約算法實(shí)現(xiàn)了路徑優(yōu)化，同時(shí)對(duì)案例進(jìn)行了分析，給出了路徑優(yōu)化方案。

【關(guān)鍵詞】路徑優(yōu)化；節(jié)約算法；集送貨一體化；時(shí)間窗約束

一、背景

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

二、研究現(xiàn)狀

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

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

三、研究方法

（一）節(jié)約算法

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

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

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

對(duì)配送量和集貨量有如下改進(jìn)：各節(jié)點(diǎn)配送量和集貨量）表示在節(jié)點(diǎn)j加入路線后可以留出的空間效益，把差值越大的節(jié)點(diǎn)放在運(yùn)輸路線的前面部分，并考慮車(chē)輛的載重限制。因此對(duì)節(jié)約算法進(jìn)行一定的修正。即。

對(duì)于時(shí)間窗約束有：設(shè)Si為完成任務(wù)i所需的時(shí)間，Ti為裝貨或卸貨所需的時(shí)間，ETi為i的允許最早開(kāi)始時(shí)間，LTi為i的允許最遲開(kāi)始時(shí)間，則Si需滿足：ETi≤Si≤LTi ， S0=0令ti，j為車(chē)輛由點(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)成各車(chē)輛配送點(diǎn)集，令；（2）計(jì)算各客戶(hù)點(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)相鄰。

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

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

1、案例分析

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

四、優(yōu)化方案

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

五、總結(jié)

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

參考文獻(xiàn)

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