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

張慶華，呂小丹

北京科技大學 機械工程學院，北京 100083

1 引言

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

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

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

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

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

2.1 問題描述

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

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

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

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

（4）模型的目標函數是配送總成本最低，配送成本包括車輛固定成本（輪胎損耗費用、保養費用、折舊費用等）、行駛成本、等待成本和延遲成本。

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

2.2 符號含義

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

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

V：配送網絡中所有的節點集合，V=N?{}0；

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

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

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

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

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

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

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

Tik：車輛k到達客戶i的時間；

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

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

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

sti：在客戶i的服務時間；

C1：動用一輛車的固定費用；

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

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

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

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

2.3 模型建立

3 混合變鄰域改進蟻群算法

3.1 初始解的產生

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

圖1 編碼結構

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

步驟1確定起始客戶。Solomon經過相關測試之后，指出問題中客戶所要求的服務時間窗口較窄時，選取距離配送中心最遠的未構成線路的客戶作為線路的起始用戶得到的解較好，而客戶所要求的服務時間窗口較寬時，選取最早結束服務時間未構成線路的客戶作為起始用戶得到的解較好。

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

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

3.2 可行路徑的構建

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

所采取的狀態轉移規則如式（10）和（11）所示，其中τij為信息素濃度，ηij=1/dij為啟發式信息，為螞蟻k下一個可以訪問的客戶點集合，q0、α、β、γ、δ為預先設置的參數。

3.3 變鄰域搜索

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

四種鄰域結構分別為：（1）2-OPT算子，在同一條路徑中交換兩個客戶點；（2）Swap算子，在兩條路徑之間交換某個客戶點；（3）Cross-exchange算子，在兩條路徑之間交換隨機數量連續的客戶點來產生鄰域解；（4）2-OPT*算子。算法依次采用四種鄰域結構產生鄰域解進行局部搜索，當搜索到較優解時繼續在該鄰域搜索。

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

基于上述四種鄰域結構和局部搜索方法，變鄰域搜索的整個過程如下所示：

步驟1初始化參數設置。確定了四種鄰域結構LYk,k={ }

1,2,3,4，最大循環次數CT，當前循環次數i=1。

步驟2判斷是否超過最大循環次數，若超過則直接輸出最優解；否則令k=1。

步驟3在當前鄰域k中隨機產生一個鄰域解。

步驟4對產生的鄰域解進行局部搜索。

步驟5判斷局部搜索后的新解是否優于當前最優解，若優于則更新當前最優解；否則令k=k+1。

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

3.4 信息素更新策略

在對蟻群算法的研究中，信息素的更新策略一般有局部更新和全局更新兩種，局部更新策略是在螞蟻每經過一條邊之后就進行信息素更新，全局更新策略則是在所有螞蟻走完它們的路徑之后進行信息素更新。文獻[18]提出了一種混合的全局更新策略，即在前10次迭代過程中根據本次迭代中的最優解進行信息素更新，10次迭代之后根據全局最優解進行信息素更新。采取這樣的信息素更新策略可以在保持較好的收斂速度的同時提高搜索能力，更新規則如下：

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

本文所設計的算法具體流程如圖2所示。

圖2 算法整體流程圖

步驟1初始化參數。設置最大迭代次數MaxGen和最優解出現的最大重復次數MaxRT。

步驟2采用啟發式算法產生初始解，令其為最優解BX,并且根據初始解更新信息素，令迭代次數Gen=0。

步驟3如果滿足終止準則(Gen＞MaxGen)，則輸出最優解BX；否則，對蟻群內每只螞蟻根據狀態轉移規則生成配送路徑，記錄當前蟻群中的最優個體X。

步驟4對BX和X進行變鄰域搜索，將其變鄰域搜索后的結果同BX進行比較，若出現更優解則更新BX，否則最優解重復次數RT=RT+1。

步驟5如果RT＞Max RT，隨機選取最優路徑上的一定路段，清空其信息素并且令RT=0；否則根據BX進行信息素更新，繼續執行步驟3。

4 算例實驗

為檢驗混合變鄰域改進蟻群算法的求解性能，本文設計了4個實驗。其中，實驗1為了驗證3.1節改進插入法產生初始解的作用，將使用插入算法前后結果進行對比。實驗2和實驗3采用其他文獻中的算例數據和國際標準算例，對本文提出的算法性能進行測試。為了驗證本文所提出的模型和算法在實際問題中的適用情況，設計了實驗4，采用企業的真實數據進行實驗。

本文算法中的參數設置規則為：每次固定其他參數，對某一個參數進行取值，然后根據算例結果來確定最終取值。本文參數設置如表1所示。

表1 參數設置

實驗1以Wang等[6]提出的關于VRPSPDTW的標準算例中的Cdp101算例進行實驗，對比使用改進的插入法和不使用的結果，每個實驗重復20次，分別記錄第一次迭代中蟻群最優解和解的均值，其中車輛固定成本為100元，單位距離成本為1元/公里，單位等待成本為1元/公里，單位延遲成本為2元/公里。實驗結果如表2所示。

表2 實驗1對比結果表

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

實驗2的數據來源于文獻[19]。設置最大迭代次數為100次，蟻群規模為20，本文算法的運算結果如表3所示。

表3 實驗2算法結果對比表

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

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

表4 實驗3算法結果對比表

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

表5 實驗4客戶信息數據

圖3 實驗4客戶分布及路徑規劃結果

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

表6 實驗4算法結果表

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

5 結束語

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