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

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

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

0 引 言

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

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

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

1 數(shù)學(xué)模型

1.1 問題描述

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

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

1.2 模型假設(shè)

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

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

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

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

（5）所有的快遞站點(diǎn)均被服務(wù)，且每一個(gè)快遞站點(diǎn)只能被一輛車服務(wù)一次，同時(shí)全部快遞站點(diǎn)對(duì)回收的共享快遞盒具有好壞識(shí)別作用。

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

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

1.3 符號(hào)定義

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

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

s.t.

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

1.5 模糊約束處理

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

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

1.6 多目標(biāo)轉(zhuǎn)化為單目標(biāo)

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

式中，1β ，2β 為權(quán)重系數(shù)，其大小取決于兩個(gè)目標(biāo)的重要程度。

2 蟻群算法設(shè)計(jì)

2.1 路徑的構(gòu)造

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

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

2.2 信息素的更新

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

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

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

2.3 蟻群算法流程

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

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

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

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

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

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

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

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

3 算例分析

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

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

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

表2 快遞站點(diǎn)信息

續(xù)表2

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

3.2 算例求解

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

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

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

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

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

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

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

表4 兩種模式的結(jié)果對(duì)比

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

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

圖5 k、 f 1、L k 隨Qk 變化趨勢(shì)圖

圖6 k、 f1 隨C 變化趨勢(shì)圖

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

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

圖7 f 1、 f 2、 Lk 隨 β1 及 β 2變化趨勢(shì)圖

4 結(jié) 論

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

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