電商退換貨車輛路徑問題及蟻群算法研究

張慶華，呂小丹

北京科技大學(xué) 機(jī)械工程學(xué)院，北京 100083

1 引言

各大電商平臺為了提高服務(wù)質(zhì)量以搶占市場份額，提出了在消費(fèi)者要求退換貨后提供上門取件服務(wù)的措施。隨著相關(guān)法律的進(jìn)一步完善，電子商務(wù)中的退換貨現(xiàn)象已經(jīng)成為一種常態(tài)化的存在。物流企業(yè)必須在發(fā)展正向物流的同時(shí)重視逆向物流問題，因此研究此類問題具有重要實(shí)際意義。

逆向物流的概念較早時(shí)間就已經(jīng)被提出，但是電子商務(wù)中逆向物流問題的研究大都集中于逆向物流網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)[1]、應(yīng)用價(jià)值[2]等問題的研究中，關(guān)于整合正、逆向物流的車輛路徑問題的研究相對較少。羅耀波等[3]建立了帶退貨和軟時(shí)間窗的多倉庫選址-路徑數(shù)學(xué)模型，設(shè)計(jì)了自適應(yīng)混合遺傳算法，并以自己設(shè)計(jì)的10個(gè)客戶規(guī)模的測試數(shù)據(jù)進(jìn)行測試。馮芳媛等[4]研究了一個(gè)帶退貨的多配送站點(diǎn)車輛路徑優(yōu)化問題，設(shè)計(jì)了禁忌搜索算法進(jìn)行求解，并以自己設(shè)計(jì)的17個(gè)客戶規(guī)模的測試數(shù)據(jù)進(jìn)行測試。邢永峰[5]建立靜態(tài)條件下回程帶貨車輛路徑優(yōu)化模型，設(shè)計(jì)了自適應(yīng)算法對模型進(jìn)行求解，并結(jié)合算例對模型進(jìn)行了仿真實(shí)驗(yàn)分析?？梢钥闯?，在電子商務(wù)中關(guān)于整合正逆向物流的研究中，考慮時(shí)間窗因素的較少，并且測試數(shù)據(jù)大都是自行設(shè)計(jì)的較小規(guī)模的測試數(shù)據(jù)，沒有同其他算法進(jìn)行對比驗(yàn)證。

在本文研究的電子商務(wù)環(huán)境下的帶退換貨的車輛路徑問題中，客戶根據(jù)需求可分為：只需要提供配送服務(wù)的客戶，只需要提供取貨服務(wù)的客戶，既需要提供配送服務(wù)也需要提供取貨服務(wù)的客戶。其中，只具備單一需求的客戶可以看成該客戶的其他需求為0，實(shí)際上這是對同時(shí)取送貨問題的拓展。在現(xiàn)有文獻(xiàn)的研究中，雖然有大量的文獻(xiàn)研究VRPSPD（Vehicle Routing Problem with Simultaneous Pickup-Delivery）問 題 和 VRPTW（Vehicle Routing Problem with Time Windows）問題，但是關(guān)于VRPSPDTW（Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows）的研究國內(nèi)外卻很少。Wang等[6]于2012年在關(guān)于VRPTW問題的Solomon算例的基礎(chǔ)上，提出了求解VRPSPDTW問題的唯一測試數(shù)據(jù)集，并且用遺傳算法對這個(gè)數(shù)據(jù)集進(jìn)行了求解。在此之前，雖然有一些學(xué)者對此類問題進(jìn)行了相關(guān)研究，但是缺乏可靠的算例驗(yàn)證[7-9]。之后，文獻(xiàn)[10]和文獻(xiàn)[11]分別提出了一種并行的模擬退火算法和離散布谷鳥算法來求解該問題，并采取標(biāo)準(zhǔn)算例進(jìn)行實(shí)驗(yàn)。其他算法在該問題的求解上還有很大的研究空間。

蟻群算法由于其自身性能上的魯棒性和搜索較好解的能力，近年來被廣泛應(yīng)用在各種領(lǐng)域，但是由于初始信息素的匱乏，蟻群算法一般需要較長的搜索時(shí)間，同時(shí)容易陷入局部最優(yōu)。凌海峰等[12]依據(jù)混沌理論的特點(diǎn)來調(diào)整蟻群算法參數(shù)，并且利用2-opt算法對最優(yōu)解進(jìn)行優(yōu)化。何小鋒等[13]針對蟻群算法在求解VRPTW問題時(shí)易陷入局部最優(yōu)和收斂速度慢的問題，結(jié)合量子計(jì)算提出一種求解VRPTW的量子蟻群算法。李琳等[14]設(shè)計(jì)了一種改進(jìn)的蟻群算法，在狀態(tài)轉(zhuǎn)移規(guī)則中引入時(shí)間窗跨度與服務(wù)等待時(shí)間因素。本文基于基本蟻群算法，在狀態(tài)轉(zhuǎn)移規(guī)則和信息素的更新規(guī)則上對蟻群算法進(jìn)行了一些改進(jìn)，同時(shí)將其和變鄰域搜索算法相結(jié)合，提升算法的性能。最后通過與其他算法的對比和標(biāo)準(zhǔn)算例實(shí)驗(yàn)來驗(yàn)證所提算法的性能，并且結(jié)合企業(yè)真實(shí)數(shù)據(jù)來驗(yàn)證其有效性。

2 帶軟時(shí)間窗和退換貨的車輛路徑問題

2.1 問題描述

為了更好地界定所要研究的問題，方便模型建立和求解，需要對實(shí)際情況進(jìn)行一些簡化和抽象，提出以下假設(shè)：

（1）研究從一個(gè)配送中心向多個(gè)客戶配送和取走商品的問題，客戶可能同時(shí)存在取貨送貨兩種需求，也可能只存在一種需求。配送中心和客戶居住位置一定，配送中心產(chǎn)品可以滿足客戶配送需求。

（2）車輛均從配送中心出發(fā)并且需要返回配送中心，每輛車只經(jīng)過各客戶一次，每個(gè)客戶只允許一輛配送車輛訪問一次，每個(gè)客戶需求必須滿足。

（3）在每個(gè)客戶處，車輛先卸貨，然后再裝貨。

（4）模型的目標(biāo)函數(shù)是配送總成本最低，配送成本包括車輛固定成本（輪胎損耗費(fèi)用、保養(yǎng)費(fèi)用、折舊費(fèi)用等）、行駛成本、等待成本和延遲成本。

基于以上假設(shè)，本文所研究的帶軟時(shí)間窗的電商退換貨車輛路徑問題可以描述為：某配送中心向一定客戶提供配送貨物和取走退換貨物的服務(wù)，已知配送中心和各個(gè)客戶之間的距離和車輛行駛時(shí)間，車輛的最大承載能力以及在每個(gè)客戶提供服務(wù)的時(shí)間，車輛的固定動用成本和單位距離行駛成本。車輛可以在客戶所要求的時(shí)間窗范圍外對客戶提供服務(wù)，但是違背時(shí)間窗會得到一定懲罰，車輛遵守“早到等待”原則，即車輛若早于客戶所要求的最早開始服務(wù)時(shí)間到達(dá)，需要等待至最早開始服務(wù)時(shí)間再進(jìn)行服務(wù)。要求合理安排車輛路徑，在滿足車輛載重和客戶時(shí)間窗要求的前提下，使所有客戶的需求量均被滿足，并且使車輛配送成本最小。

2.2 符號含義

K：配送中心擁有的車輛的集合；

N：需要配送的客戶集合；

V：配送網(wǎng)絡(luò)中所有的節(jié)點(diǎn)集合，V=N?{}0；

dij：車輛從客戶i到客戶 j之間的行駛距離；

tij：車輛從客戶i到客戶 j之間的行駛時(shí)間；

Q：車輛的最大載重限制；

pi：客戶i的退貨收集需求量；

qi：客戶i的配送需求量；

Wijk：車輛k從客戶i到客戶 j的途中車上裝載的已收集的貨物總量；

Zijk：車輛k從客戶i到客戶 j的途中車上裝載的還未配送的貨物總量；

Tik：車輛k到達(dá)客戶i的時(shí)間；

[ETi,LTi]：客戶i要求的時(shí)間窗，ETi表示最早開始服務(wù)時(shí)間，LTi表示最晚開始服務(wù)時(shí)間；

yik：車輛k是否參與客戶i的配送任務(wù)，yik=1表示車輛k參與客戶i的配送任務(wù)，yik=0表示車輛k不參與客戶i的配送任務(wù)；

xijk：車輛k是否由客戶i駛向客戶 j，xijk=1表示從客戶i到客戶 j的配送任務(wù)由車輛k完成，xijk=0表示從客戶i到客戶 j的配送任務(wù)不是由車輛k完成；

sti：在客戶i的服務(wù)時(shí)間；

C1：動用一輛車的固定費(fèi)用；

C2：車輛行駛單位距離的成本；

e1：車輛的單位等待成本；

e2：車輛的單位遲到成本。

其中，i,j∈V，k∈K。

2.3 模型建立

3 混合變鄰域改進(jìn)蟻群算法

3.1 初始解的產(chǎn)生

本文在求解帶軟時(shí)間窗的電商退換貨車輛路徑問題時(shí)采取整數(shù)編碼的方式，用0表示配送中心，1～n表示客戶編號，1～k表示車輛編號，每個(gè)解的路徑采用一個(gè)n+k+1的整型向量表示，每個(gè)解包含k條子路徑，每條子路徑表示一輛車的行駛回路，編碼結(jié)構(gòu)如圖1所示。

圖1 編碼結(jié)構(gòu)

蟻群算法由于在初期信息素匱乏，會導(dǎo)致整個(gè)算法搜索速度緩慢，因此較好的初始解能夠提升整個(gè)算法的性能，根據(jù)初始解設(shè)置的初始信息素則能加快算法的搜索速度。目前，構(gòu)建初始解常用的方法一般為掃描法、節(jié)約算法、貪婪算法等，其中Solomon[15]經(jīng)過測試證明插入啟發(fā)式算法求得解最優(yōu)，通過擴(kuò)展傳統(tǒng)的節(jié)約插入算法提出了Solomon插入算法。本文借鑒潘立軍等[16]提出的改進(jìn)的Solomon插入法——時(shí)差法，提出了適合本文研究問題的插入前檢測算法來構(gòu)建初始解。即根據(jù)時(shí)間窗要求，計(jì)算出車輛在各客戶點(diǎn)的最遲開始服務(wù)時(shí)間，根據(jù)車輛的裝載能力約束和各客戶點(diǎn)的取送貨需求量，計(jì)算出車輛從各客戶點(diǎn)出發(fā)的最大裝載量，在滿足時(shí)間約束和車輛裝載能力約束的前提下，在最優(yōu)插入位置插入評價(jià)最優(yōu)的客戶點(diǎn)。相對于插入后檢測，可省去一部分不可行插入的過程，從而有利于提高算法速度。具體步驟如下所示：

步驟1確定起始客戶。Solomon經(jīng)過相關(guān)測試之后，指出問題中客戶所要求的服務(wù)時(shí)間窗口較窄時(shí)，選取距離配送中心最遠(yuǎn)的未構(gòu)成線路的客戶作為線路的起始用戶得到的解較好，而客戶所要求的服務(wù)時(shí)間窗口較寬時(shí)，選取最早結(jié)束服務(wù)時(shí)間未構(gòu)成線路的客戶作為起始用戶得到的解較好。

步驟2將最優(yōu)插入客戶插入到最佳的插入位置。若該條配送子路徑不能繼續(xù)插入滿足約束的客戶點(diǎn)，則結(jié)束在該路徑上插入客戶，重新開始一條子路徑并且確定起始用戶。

步驟3判斷是否所有的客戶均已經(jīng)被插入到路徑中，若所有客戶均已經(jīng)被插入，則初始解構(gòu)造完成，并且根據(jù)初始解更新信息素，否則執(zhí)行步驟2。

3.2 可行路徑的構(gòu)建

在本文提出的蟻群算法中，將各螞蟻放在配送中心，每只螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選擇需要去往的下一個(gè)客戶，當(dāng)沒有滿足車輛載重約束的客戶時(shí)，螞蟻返回配送中心并且重新出發(fā)，直至所有客戶被遍歷，即每只螞蟻都構(gòu)建了一條完整的可行路徑。本文的狀態(tài)轉(zhuǎn)移規(guī)則借鑒了蟻群系統(tǒng)（Ant Colony System，ACS）的狀態(tài)轉(zhuǎn)移規(guī)則，并進(jìn)行適當(dāng)調(diào)整。令wtj表示車輛在客戶點(diǎn)j的等待時(shí)間，ltj表示車輛在客戶點(diǎn) j的延遲時(shí)間，當(dāng)車輛早于客戶所要求的最早開始服務(wù)時(shí)間到達(dá)，則需要等待至最早開始服務(wù)時(shí)間才能開始提供服務(wù)，過長的等待時(shí)間會影響車輛的配送效率；當(dāng)車輛晚于最晚開始服務(wù)時(shí)間到達(dá)，就會產(chǎn)生延遲時(shí)間，過長的延遲時(shí)間則會大大影響客戶的滿意度。因此本文算法在狀態(tài)轉(zhuǎn)移規(guī)則中，考慮了車輛的等待時(shí)間或者延遲時(shí)間這個(gè)因素，有利于保障企業(yè)的利益和客戶的服務(wù)質(zhì)量。

所采取的狀態(tài)轉(zhuǎn)移規(guī)則如式（10）和（11）所示，其中τij為信息素濃度，ηij=1/dij為啟發(fā)式信息，為螞蟻k下一個(gè)可以訪問的客戶點(diǎn)集合，q0、α、β、γ、δ為預(yù)先設(shè)置的參數(shù)。

3.3 變鄰域搜索

變鄰域搜索（Variable Neighborhood Search，VNS）是由Hansen等在1997年提出的，使用不同鄰域結(jié)構(gòu)進(jìn)行搜索，從而不斷提高解的質(zhì)量，具有很強(qiáng)的局部搜索能力。變鄰域算法主要包括兩個(gè)階段，產(chǎn)生鄰域解階段和局部搜索階段。通過閱讀相關(guān)文獻(xiàn)，并且結(jié)合所研究問題的特點(diǎn)，本文設(shè)計(jì)了四種鄰域結(jié)構(gòu)，并且設(shè)計(jì)了重定位（Relocate）算子[17]對產(chǎn)生的鄰域解進(jìn)行局部搜索。

四種鄰域結(jié)構(gòu)分別為：（1）2-OPT算子，在同一條路徑中交換兩個(gè)客戶點(diǎn)；（2）Swap算子，在兩條路徑之間交換某個(gè)客戶點(diǎn)；（3）Cross-exchange算子，在兩條路徑之間交換隨機(jī)數(shù)量連續(xù)的客戶點(diǎn)來產(chǎn)生鄰域解；（4）2-OPT*算子。算法依次采用四種鄰域結(jié)構(gòu)產(chǎn)生鄰域解進(jìn)行局部搜索，當(dāng)搜索到較優(yōu)解時(shí)繼續(xù)在該鄰域搜索。

本文采用Relocate算子對所產(chǎn)生的鄰域解進(jìn)行局部搜索。Relocate算子就是對當(dāng)前路徑方案內(nèi)所有的客戶尋找其他的可行位置點(diǎn)進(jìn)行插入，若搜索到新的解時(shí)，將其和當(dāng)前最優(yōu)解進(jìn)行對比，若優(yōu)于則更新當(dāng)前最優(yōu)解，并且繼續(xù)在更新后的最優(yōu)解基礎(chǔ)上進(jìn)行重定位操作。其中，每次Relocate算子搜索到新的最優(yōu)解之后，會再次調(diào)用Relocate算子將最短路徑上的客戶定位到更新的減少了客戶點(diǎn)的路徑上，從而有利于消除最短路徑，降低所使用的車輛數(shù)。局部搜索過程仍然采用3.1節(jié)中的插入前檢測法，每次重定位操作都是將最優(yōu)插入客戶點(diǎn)插入到最優(yōu)插入位置。

基于上述四種鄰域結(jié)構(gòu)和局部搜索方法，變鄰域搜索的整個(gè)過程如下所示：

步驟1初始化參數(shù)設(shè)置。確定了四種鄰域結(jié)構(gòu)LYk,k={ }

1,2,3,4，最大循環(huán)次數(shù)CT，當(dāng)前循環(huán)次數(shù)i=1。

步驟2判斷是否超過最大循環(huán)次數(shù)，若超過則直接輸出最優(yōu)解；否則令k=1。

步驟3在當(dāng)前鄰域k中隨機(jī)產(chǎn)生一個(gè)鄰域解。

步驟4對產(chǎn)生的鄰域解進(jìn)行局部搜索。

步驟5判斷局部搜索后的新解是否優(yōu)于當(dāng)前最優(yōu)解，若優(yōu)于則更新當(dāng)前最優(yōu)解；否則令k=k+1。

步驟6判斷k是否小于5，若小于則轉(zhuǎn)入步驟3；否則令i=i+1，轉(zhuǎn)入步驟2。

3.4 信息素更新策略

在對蟻群算法的研究中，信息素的更新策略一般有局部更新和全局更新兩種，局部更新策略是在螞蟻每經(jīng)過一條邊之后就進(jìn)行信息素更新，全局更新策略則是在所有螞蟻?zhàn)咄晁鼈兊穆窂街筮M(jìn)行信息素更新。文獻(xiàn)[18]提出了一種混合的全局更新策略，即在前10次迭代過程中根據(jù)本次迭代中的最優(yōu)解進(jìn)行信息素更新，10次迭代之后根據(jù)全局最優(yōu)解進(jìn)行信息素更新。采取這樣的信息素更新策略可以在保持較好的收斂速度的同時(shí)提高搜索能力，更新規(guī)則如下：

其中，ρ表示信息素?fù)]發(fā)系數(shù)；Lib表示當(dāng)前迭代次數(shù)中的最優(yōu)解；Lob表示全局最優(yōu)解；Gen表示當(dāng)前迭代次數(shù)；θ表示不同更新策略的迭代次數(shù)界限。為提高算法的收斂速度，本文采取上述對最優(yōu)解的信息素全局更新策略，但是會出現(xiàn)算法在后期一旦陷入局部最優(yōu)，就無法跳出的情況。因此在最優(yōu)解連續(xù)一定迭代次數(shù)沒有更新時(shí)，采取隨機(jī)選取最優(yōu)解中一定數(shù)量的路段，清空其信息素的措施，從而有利于跳出局部最優(yōu)解繼續(xù)搜索，避免陷入局部最優(yōu)。

本文所設(shè)計(jì)的算法具體流程如圖2所示。

圖2 算法整體流程圖

步驟1初始化參數(shù)。設(shè)置最大迭代次數(shù)MaxGen和最優(yōu)解出現(xiàn)的最大重復(fù)次數(shù)MaxRT。

步驟2采用啟發(fā)式算法產(chǎn)生初始解，令其為最優(yōu)解BX,并且根據(jù)初始解更新信息素，令迭代次數(shù)Gen=0。

步驟3如果滿足終止準(zhǔn)則(Gen＞MaxGen)，則輸出最優(yōu)解BX；否則，對蟻群內(nèi)每只螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則生成配送路徑，記錄當(dāng)前蟻群中的最優(yōu)個(gè)體X。

步驟4對BX和X進(jìn)行變鄰域搜索，將其變鄰域搜索后的結(jié)果同BX進(jìn)行比較，若出現(xiàn)更優(yōu)解則更新BX，否則最優(yōu)解重復(fù)次數(shù)RT=RT+1。

步驟5如果RT＞Max RT，隨機(jī)選取最優(yōu)路徑上的一定路段，清空其信息素并且令RT=0；否則根據(jù)BX進(jìn)行信息素更新，繼續(xù)執(zhí)行步驟3。

4 算例實(shí)驗(yàn)

為檢驗(yàn)混合變鄰域改進(jìn)蟻群算法的求解性能，本文設(shè)計(jì)了4個(gè)實(shí)驗(yàn)。其中，實(shí)驗(yàn)1為了驗(yàn)證3.1節(jié)改進(jìn)插入法產(chǎn)生初始解的作用，將使用插入算法前后結(jié)果進(jìn)行對比。實(shí)驗(yàn)2和實(shí)驗(yàn)3采用其他文獻(xiàn)中的算例數(shù)據(jù)和國際標(biāo)準(zhǔn)算例，對本文提出的算法性能進(jìn)行測試。為了驗(yàn)證本文所提出的模型和算法在實(shí)際問題中的適用情況，設(shè)計(jì)了實(shí)驗(yàn)4，采用企業(yè)的真實(shí)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。

本文算法中的參數(shù)設(shè)置規(guī)則為：每次固定其他參數(shù)，對某一個(gè)參數(shù)進(jìn)行取值，然后根據(jù)算例結(jié)果來確定最終取值。本文參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置

實(shí)驗(yàn)1以Wang等[6]提出的關(guān)于VRPSPDTW的標(biāo)準(zhǔn)算例中的Cdp101算例進(jìn)行實(shí)驗(yàn)，對比使用改進(jìn)的插入法和不使用的結(jié)果，每個(gè)實(shí)驗(yàn)重復(fù)20次，分別記錄第一次迭代中蟻群最優(yōu)解和解的均值，其中車輛固定成本為100元，單位距離成本為1元/公里，單位等待成本為1元/公里，單位延遲成本為2元/公里。實(shí)驗(yàn)結(jié)果如表2所示。

表2 實(shí)驗(yàn)1對比結(jié)果表

從表2可以看出，采用改進(jìn)后的插入法產(chǎn)生初始解，并且根據(jù)初始解設(shè)置初始信息素后，實(shí)驗(yàn)20次后，蟻群在第一次迭代中最優(yōu)解的平均值為3 411.28，種群均值的平均值為5 895.95；不采用插入法產(chǎn)生初始解，實(shí)驗(yàn)20次后，蟻群在第一次迭代中最優(yōu)解的平均值為3 945.92，種群均值的平均值為6 123.87。采用改進(jìn)后的插入法產(chǎn)生的蟻群解的質(zhì)量明顯好于不采用的蟻群解的質(zhì)量。

實(shí)驗(yàn)2的數(shù)據(jù)來源于文獻(xiàn)[19]。設(shè)置最大迭代次數(shù)為100次，蟻群規(guī)模為20，本文算法的運(yùn)算結(jié)果如表3所示。

表3 實(shí)驗(yàn)2算法結(jié)果對比表

從表3可以看出，本文研究的算法得到的結(jié)果比文獻(xiàn)[19]采取模擬退火算法得到的結(jié)果更優(yōu)。本文的結(jié)果只需要3輛車進(jìn)行配送，相對于文獻(xiàn)[19]減少了1輛車，提高了所用車輛的裝載率；在各個(gè)客戶點(diǎn)的平均等待時(shí)間和延遲時(shí)間也均小于文獻(xiàn)[19]的結(jié)果，提高了客戶滿意度；總配送成本相對于文獻(xiàn)[19]降低了12%，降低了企業(yè)的物流費(fèi)用。

實(shí)驗(yàn)3為了進(jìn)一步測試本文提出的混合變鄰域改進(jìn)蟻群算法的性能，以Wang等[6]提出的關(guān)于VRPSPDTW的標(biāo)準(zhǔn)算例作為實(shí)驗(yàn)對象，比較相關(guān)文獻(xiàn)的結(jié)果。本文選取了客戶規(guī)模10、25、50和100的算例各兩個(gè)，與當(dāng)前國際最優(yōu)解[11]的對比如表4所示。在8個(gè)算例中，本文提出的變鄰域改進(jìn)蟻群算法在6個(gè)算例中求得的解與已知最優(yōu)解一致，在算例Rcdp5001和算例Cdp101上，求得了和已知最優(yōu)解相同的車輛數(shù)，距離上最大相差1.2%，十分接近最優(yōu)解，從而進(jìn)一步證明了本文所提出的算法在求解VRPSPDTW問題上的可行性和有效性。

表4 實(shí)驗(yàn)3算法結(jié)果對比表

實(shí)驗(yàn)4中客戶點(diǎn)的分布情況如圖3所示，客戶點(diǎn)之間的距離信息和行駛時(shí)間數(shù)據(jù)均由真實(shí)的地圖數(shù)據(jù)獲得，客戶所要求的時(shí)間窗(ET,LT)、送貨量q、取貨量p和服務(wù)時(shí)間ST如表5所示。配送中心有6輛車，車輛8：00從配送中心出發(fā)，最晚18：00返回配送中心，車輛的裝載能力是4 m3。本文采取和文獻(xiàn)[19]相同的參數(shù)設(shè)置規(guī)則，車輛的單位行駛成本是1元/公里，早于時(shí)間窗到達(dá)的等待成本為3元/小時(shí)，晚于時(shí)間窗到達(dá)的延遲成本為6元/小時(shí)，動用一輛車的固定成本是20元。根據(jù)上述條件，要求合理安排配送路線，使配送總成本最低。

表5 實(shí)驗(yàn)4客戶信息數(shù)據(jù)

圖3 實(shí)驗(yàn)4客戶分布及路徑規(guī)劃結(jié)果

實(shí)驗(yàn)結(jié)果如表6所示，車輛在各個(gè)客戶點(diǎn)均沒有延遲服務(wù)，使得在此方面的顧客滿意度達(dá)到最大，在各個(gè)點(diǎn)的平均等待時(shí)間為0.076 h，等待時(shí)間較小，4輛車的路線規(guī)劃結(jié)果如圖3所示，因此本文所建立的模型和求解算法能夠滿足實(shí)際問題的需要。

表6 實(shí)驗(yàn)4算法結(jié)果表

通過上述算例實(shí)驗(yàn)，本文所設(shè)計(jì)的改進(jìn)蟻群算法，改善了基本蟻群算法在初期由于信息素匱乏而搜索速度慢的情況。在求解帶軟時(shí)間窗和同時(shí)取送貨的車輛路徑問題上，相對于模擬退火算法求得的結(jié)果，使用的車輛數(shù)量更少，等待延遲時(shí)間也更少。在關(guān)于VRPSPDTW問題不同規(guī)模的標(biāo)準(zhǔn)算例求解上，有些已經(jīng)能夠取得已知最優(yōu)解，其余取得的結(jié)果也十分接近最優(yōu)解。在實(shí)際問題的處理中，求得的結(jié)果能夠滿足實(shí)際需要。這都說明了本文算法具有良好的求解性能，能夠搜索到較好的結(jié)果。

5 結(jié)束語

為了適應(yīng)電子商務(wù)發(fā)展，整合物流企業(yè)的正、逆向物流，本文建立了關(guān)于電子商務(wù)環(huán)境下帶軟時(shí)間窗和退換貨的車輛路徑規(guī)劃模型，并且在基本蟻群算法的基礎(chǔ)上，設(shè)計(jì)了一種混合變鄰域改進(jìn)蟻群算法。使用插入法產(chǎn)生的初始解設(shè)置初始信息素，通過對比實(shí)驗(yàn)表明，采取這一措施后生成的蟻群解相比未采取時(shí)更優(yōu)。將等待、延遲時(shí)間這些因素引入蟻群的狀態(tài)轉(zhuǎn)移規(guī)則，從而保障企業(yè)的利益和客戶的服務(wù)質(zhì)量。同時(shí)，為了提高算法的搜索能力和跳出局部最優(yōu)的能力，本文設(shè)計(jì)了四種鄰域結(jié)構(gòu)的變鄰域搜索算法進(jìn)行局部優(yōu)化。通過和其他文獻(xiàn)中的算法對比和對標(biāo)準(zhǔn)算例的驗(yàn)證，本文所設(shè)計(jì)的算法均能夠取得較優(yōu)的結(jié)果，具有較強(qiáng)適應(yīng)性，是求解本文提出問題的一種有效算法。本文研究的問題屬于靜態(tài)調(diào)度問題，在實(shí)際生活中，配送過程中往往會出現(xiàn)動態(tài)性事件，需要對現(xiàn)有的配送路線進(jìn)行動態(tài)調(diào)整。因此，針對動態(tài)事件進(jìn)行的動態(tài)調(diào)度研究將是接下來的研究方向。