基于蟻群算法的共享快遞盒配送回收網(wǎng)絡優(yōu)化研究

牟能冶，賈程方，康秋萍，龔 迪

（1. 西南交通大學，交通運輸與物流學院，成都 611756；2. 綜合交通運輸智能化國家地方聯(lián)合工程實驗室，成都 611756）

0 引 言

隨著環(huán)境污染和資源浪費問題在物流業(yè)日益凸顯，各大電商企業(yè)開始采取措施促進快遞包裝的“綠色化”，共享快遞盒作為綠色包裝的產(chǎn)物應運而生[1]。然而回收情況并不理想，原因一是客戶的配合意愿不夠強烈且影響快遞員的工作效率，二是回收成本高昂[2]。因此，通過對配送回收網(wǎng)絡進行路徑優(yōu)化，從而提高企業(yè)的回收效率，加速共享快遞盒的循環(huán)使用，以及降低企業(yè)的運作成本成為當前亟須解決的問題。

同時取送貨問題（VRPSPD）是經(jīng)典車輛路徑問題（VRP）的一種擴展，該問題由Min 于1989年首次提出[3]，隨著應用背景和適用范圍的深入，使得研究更加貼近實際。Liu 等[4]針對家庭醫(yī)療物流領域構建了帶時間窗的VRPSPD 模型；陸志強等[5]針對航空領域構建了飛機移動生產(chǎn)線物料配送與空箱回收集成決策模型；陳俊[6]針對汽車領域構建零部件供應和回收雙向物流路徑優(yōu)化模型。與此同時，學者們針對實際情況考慮不同的因素，孫青偉等[7]考慮集成物流概念下構建了同時取送貨的選址-多車型路徑模型；趙燕偉等[8]構建了以碳排放最小為目標的多車型 VPRSPD模型；Shimizu 等[9]考慮了裝載重量影響下的多倉庫路徑優(yōu)化問題；馬艷芳等[10]構建了以總成本最小為目標的低碳環(huán)境與模糊需求下的同時取送貨模型；張濤等[11]構建了以總行程最小的逆向同時取送貨模型。由于VRPSPD 問題屬于NP-hard問題，所以多采用粒子群算法[12]、蟻群算法[13]、離散布谷鳥算法[14]、自適應并行遺傳算法[15]、改進的迭代局部搜索算法[16]、模擬退火算法[17]、離散差分進化算法[18]等啟發(fā)式算法進行求解。

綜上所述，VRPSPD 問題研究豐富，但是考慮因素較為單一，且大多以成本、路程等單目標進行優(yōu)化。而本文根據(jù)共享快遞盒實際運作中存在的成本高昂和工作量分配不均等問題，考慮到配送與回收的不確定性、時間窗，構建同時配送與回收的多目標路徑優(yōu)化模型，引入等待時間因素設計蟻群算法的轉移規(guī)則并求解，通過仿真實驗驗證模型和算法的有效性。

1 數(shù)學模型

1.1 問題描述

本文的問題可具體描述為：車輛從確定的分撥中心出發(fā)，對各快遞站點所屬的快遞件進行相應的配送，并同時將自營的快遞站點、第三方快遞點的共享快遞盒進行回收，直至車輛完成所在路徑的配送和回收，接著返回回收檢測中心卸載回收到的所有損壞的共享快遞盒，并將完好的返回分撥中心進行下一次調(diào)撥。由于整個配送回收網(wǎng)絡是基于自營的角度，且存在客戶需求、配送與回收的不確定性，因此自營快遞站點的配送量和回收量均為不確定需求。而第三方快遞點的配送由第三方物流完成，因此，在該網(wǎng)絡下的配送量為0，同時需要負責回收第三方快遞站點的共享快遞盒，且回收量不確定。該問題的結構如圖1 所示。

圖1 共享快遞盒的配送回收網(wǎng)絡優(yōu)化

1.2 模型假設

（1）共享快遞盒配送回收網(wǎng)絡的分撥中心、快遞站點和回收檢測中心的位置已知，即分撥中心到快遞站點、快遞站點到快遞站點、快遞站點到回收檢測中心的距離已知。

（2）共享快遞盒分撥中心是所有路徑的起點和終點，所有車輛均從分撥中心出發(fā)，完成配送和回收任務后先到回收檢測中心卸損壞的共享快遞盒，再返回分撥中心。

（3）本文考慮一種車型，且車輛數(shù)量足夠多，其最大載重量、最長行駛距離、單次使用的固定成本已知。

（4）本文考慮使用的共享快遞盒為同一型號，且損壞率已知。

（5）所有的快遞站點均被服務，且每一個快遞站點只能被一輛車服務一次，同時全部快遞站點對回收的共享快遞盒具有好壞識別作用。

（6）本文考慮早到與晚到的單位懲罰成本相同，運輸成本與運輸距離成正比。

（7）在配送回收過程中，不考慮突發(fā)狀況的影響。

1.3 符號定義

1.4 多目標優(yōu)化模型

本文從降低運作成本和平衡員工工作量兩個角度出發(fā)，考慮不確定需求的、帶時間窗的、同時配送與回收問題（Vehicle Routing Problem with Simultaneous Pickup and Delivery、Time Window and Fuzzy Demand，簡稱VRPSPDTWFD），具體建模如下：

s.t.

目標函數(shù)（1）表示共享快遞盒配送回收網(wǎng)絡路徑規(guī)劃的總成本最??；目標函數(shù)（2）表示最小化最長行駛距離和最短行駛路徑的距離差，從而平衡工作量；公式（3）與（4）表示車輛從共享快遞盒分撥中心出發(fā)，且從回收檢測中心回到分撥中心；公式（5）表示車輛行駛至路徑節(jié)點j 后必須從此節(jié)點駛出；公式（6）表示一個快遞站點或者回收檢測中心只被一輛車服務，且只能被服務一次；公式（7）表示從分撥中心發(fā)出的共享快遞盒的總裝載量不超過車輛的最大容量；公式（8）表示在到回收檢測中心前的子路徑下回收的共享快遞盒的總量不超過車輛的最大容量；公式（9）表示車輛行駛至任意節(jié)點j 的共享快遞盒的裝載量不超過車輛的最大容量；公式（10）表示車輛k 由i 到j 但還未開始給j 服務時的裝載量；公式（11）表示車輛k 行駛的路徑總長度，公式（12）表示車輛的行駛路徑總長度不超過該車輛的最大行駛里程；公式（13）表示車輛k 行駛到任意節(jié)點i 的累計距離不超過車輛的最大行駛里程；公式（14）表示車輛到達j 的時間，公式（15）表示整數(shù)約束。

1.5 模糊約束處理

本文對不確定環(huán)境下帶時間窗的共享快遞盒配送回收車輛路徑優(yōu)化問題構建了含有模糊變量的多目標數(shù)學規(guī)劃模型，包括配送量和回收量這兩個模糊變量。因此，本文擬用機會約束規(guī)劃方法對帶模糊變量的約束條件進行處理。

因此，根據(jù)上述定義，易將模糊機會約束條件（7）、（8）、（9）、（10）轉化為與之對應的等價約束，如下所示：

1.6 多目標轉化為單目標

本文考慮的兩個目標函數(shù)分別為配送回收網(wǎng)絡路徑規(guī)劃的總成本最小和最長最短路徑距離差最小化，其量綱不一致，因此，需通過無量綱和線性加權處理轉化為單目標問題：

式中，1β ，2β 為權重系數(shù)，其大小取決于兩個目標的重要程度。

2 蟻群算法設計

2.1 路徑的構造

本文考慮了各快遞點可接受服務的時間窗，因此，在螞蟻的轉移過程中會優(yōu)先服務時間窗較短的快遞點并且縮短車輛訪問各快遞點時的等待時間，因此，將等待時間waitj這一因素考慮進轉移概率，waitj具體表達式如下：

因此，螞蟻k 從快遞點i 轉移到快遞點j 的轉移規(guī)則如下式所示：

2.2 信息素的更新

本文在蟻群算法求解過程中，采用全局信息素更新規(guī)則，ijτ 更新規(guī)則如下式所示：

針對信息素釋放的問題，本文采用ant cycle system 模型，具體表示如下：

式中，Q 代表常數(shù)，指螞蟻循環(huán)一次釋放的信息素總量； fpbest 指的是第k 只螞蟻經(jīng)過路徑所得到的最優(yōu)成本。

2.3 蟻群算法流程

利用蟻群算法求解共享快遞盒配送回收網(wǎng)絡模型的具體算法流程描述如下：

Step1 讀取快遞點相關數(shù)據(jù)，包括需求量、回收量、時間窗、服務時間、各節(jié)點間的距離，并初始化相關參數(shù)，此時迭代步數(shù)N =1 ；

Step2 將m 只螞蟻隨機放置到各快遞節(jié)點；

Step3 對于每個螞蟻k （k =1,2,3, …,m），根據(jù)轉移概率規(guī)則計算螞蟻k 的下一訪問節(jié)點j，直到螞蟻訪問完所有節(jié)點；

Step4 計算每條完整路徑的長度kL 、總成本F1、總固定成本CT1、總行駛成本CT2、總懲罰成本CT3、總行駛時間CT4，并記錄當前迭代次數(shù)的最優(yōu)值fpbest；

Step5 同時，按照全局式信息素更新規(guī)則更新全局信息素矩陣；

Step6 若迭代次數(shù)達到Nmax，則跳到Step7，否則清空ijτΔ ， N =N+1 ，跳轉到Step2；

Step7 輸出最優(yōu)解。

3 算例分析

3.1 算例背景及基礎數(shù)據(jù)

以蘇寧成都某片區(qū)的共享快遞盒配送回收網(wǎng)絡為基礎，進行模型的仿真求解分析。網(wǎng)絡中有一個共享快遞盒分撥中心，其地址坐標為（104.187 638，30.560 487），分撥中心的開啟和關閉時刻為（6，20），假設分撥中心各配送車輛車型一致，車輛信息如表1 所示。網(wǎng)絡中只有一個回收檢測中心，地址坐標為（104.226 985，30.503 652），服務時間窗為（8，18），服務時間為0.5h。該網(wǎng)絡中需要服務的客戶即快遞點共有31 個，包括19 個蘇寧自營快遞點和12 個第三方快遞點，其中，分撥中心、檢測中心以及31 個快遞節(jié)點的編號依次為0，1，2，…，32，故分撥中心在程序中表達的節(jié)點是0，回收檢測中心為1，快遞節(jié)點的編號是從2 開始，依次類推，31 個快遞站點的地址信息如表2 所示。

表1 車輛相關參數(shù)

表2 快遞站點信息

續(xù)表2

對市場進行調(diào)查分析，假設早于時間窗到達需要等待的單位懲罰成本 C1=10 ，晚于時間窗到達產(chǎn)生延誤的單位懲罰成本 C2=10 。

3.2 算例求解

算法中相關參數(shù)設置如下：算法最大迭代步數(shù)Nmax=500，信息素重要程度因子α = 1，啟發(fā)函數(shù)重要度因子β = 5，揮發(fā)系數(shù)ρ =0.2，控制參數(shù) q0=0.2，信息素強度Q= 50，螞蟻總數(shù)為50，需求和回收量的置信水平系數(shù)均取0.9，目標函數(shù)權重系數(shù)均取0.5。為兼顧算法穩(wěn)定性和精確性，進行10 次仿真，并選取最優(yōu)結果如圖2、表3 所示。

圖2 最優(yōu)配送回收網(wǎng)絡路徑圖

表3 最優(yōu)配送回收網(wǎng)絡路徑?jīng)Q策

目前，共享快遞盒的運作模式采用傳統(tǒng)的正向配送與逆向回收分開進行，且配送針對自營快遞站點，不需要返回回收檢測中心，所以，分撥中心與19 個自營快遞點的編號依次為0，1，2，…，19，其中，0 表示分撥中心，自營快遞點的編號從1 開始，依次類推。多次仿真分析，選取最優(yōu)的傳統(tǒng)配送和回收路徑方案，具體如圖3、圖4所示。

圖3 最優(yōu)配送方案路徑圖

圖4 最優(yōu)回收方案路徑圖

通過以上仿真分析，對同時配送回收模式和傳統(tǒng)配送、傳統(tǒng)回收模式兩種方案進行對比，具體比較結果如表4 所示。

表4 兩種模式的結果對比

由結果對比可知，同時配送與回收所需車輛數(shù)比傳統(tǒng)配送、傳統(tǒng)回收方案所需車輛數(shù)降低50%，極大提高了車輛的使用率；且行駛總距離降低43.6%，使得在同時配送與回收模式下的總成本降低45.9%，大幅度降低了企業(yè)的運作成本。此種模式下，配送與回收同時進行，可以加速共享快遞盒的循環(huán)，且在快遞站點進行回收的共享快遞盒，給客戶一定的時間進行返回，從而進一步提高回收的效率。并且同時配送與回收模式下，配送量與回收量更接近車輛的最大載貨量，使得車輛空載率低，路徑差也相對較小，員工的工作量也較平衡。

為分析決策者決策偏好對結果的影響，本文在同一實驗數(shù)據(jù)下，分別選取不同的車輛載重量kQ 、單位懲罰成本C、目標權重系數(shù)1β 及2β 的值，比較不同決策對行駛距離kL 、總成本1f 、最長最短路徑差 f2的影響，具體如圖5、圖6、圖7所示。

圖5 k、 f 1、L k 隨Qk 變化趨勢圖

圖6 k、 f1 隨C 變化趨勢圖

由圖5、圖6 可知，車輛載重量kQ 和單位懲罰成本C 對總成本的影響明顯，隨著kQ 的增加，車輛數(shù)k 減少，車輛的行駛距離降低，總成本降低；而總成本與C 呈正相關，隨著C 增加，且C= 40時，通過犧牲行駛距離，即先配送距離相對較遠的快遞點來減少懲罰成本的影響。

由圖7 可知，隨著1β 逐漸減小，2β 逐漸增大，最長最短路徑差會減少，即快遞員的工作量越來越平衡，總成本呈不斷增加的趨勢；但當2β 從0.4 增加到0.5 時，為了平衡工作量，所以會犧牲一定的運輸距離，此時車輛數(shù)減少，固定成本降低，總成本會出現(xiàn)下降拐點，但此后總成本繼續(xù)呈增加趨勢。

圖7 f 1、 f 2、 Lk 隨 β1 及 β 2變化趨勢圖

4 結 論

本文針對共享快遞盒實際運行模式的不足，在模型中考慮了需求與回收的不確定因素，從運作總成本最低和平衡員工工作量兩個角度出發(fā)，構建了同時配送與回收共享快遞盒的路徑優(yōu)化模型（VRPSPDTWFD），并設計改進的蟻群算法求解帶時間窗的路徑規(guī)劃問題，通過算例驗證了模型的合理性和算法的有效性。此外，算例表明，決策者的決策偏好對總成本和員工的工作量平衡影響明顯，因此，在保證快遞員合理工作量的前提下，盡量選擇較大的載重量汽車，并采用較低的單位懲罰成本，可以有效降低網(wǎng)絡運行的總成本；同時，相對平均的目標權重系數(shù)，可以保證整個網(wǎng)絡運作成本和工作量差異的相對最優(yōu)。

然而，本文在模型方面未考慮交通路網(wǎng)受路況變化以及突發(fā)狀況的影響，同時，由于員工的工作量不僅包括行駛距離，也包括在各快遞站點的等待時間、服務時間等，因此，在未來的研究中，可考慮動態(tài)交通路網(wǎng)，且使用時間因素來平衡員工之間的工作量。