考慮灰需求的電動汽車配送路徑優化

王海燕，韓已晴

（福州大學 經濟與管理學院，福建 福州 350000）

1 引言

隨著電子商務的發展和交通運輸網絡的完善，物流市場不斷擴大，物流配送帶來的高能源消耗和高碳排放問題逐漸引起了社會的廣泛關注。在新能源汽車技術進步和政府扶持政策的共同推動下，越來越多的企業致力于發展綠色物流，開始采用純電動物流車進行城市配送。相較于傳統燃油車，利用純電動汽車進行配送具有低能耗、低碳排、低污染等優點，但行駛里程短、充電時間長、充電設施不足等問題是制約電動汽車配送進一步發展的主要障礙。為規避電動汽車的技術缺陷，促進電動汽車在物流配送行業的長足發展，眾多學者針對電動汽車路徑優化問題（Electric Vehicle Routing Problem，EVRP）展開了研究。

Schneider，等[1]提出了同時考慮客戶時間窗和充電站的電動汽車路徑優化問題；Schiffer，等[2]將充電站選址和電動汽車路徑優化問題相結合進行研究；郭放[3]認為電池損耗不容忽略，提出將電動物流車的電池損耗成本納入到目標函數。

上述研究主要是在靜態確定的情況下，從時間窗約束、里程約束和充電約束等方面對電動汽車配送路徑進行優化。然而，在實際的物流配送過程中，用戶需求、時間窗、道路擁堵情況和配送成本等信息很可能是動態不確定的，其不確定性主要表現為動態性、隨機性、模糊性或灰性。因此，考慮動態不確定信息對于電動汽車路徑優化問題是很有必要的。當前，國內外關于不確定型EVRP的研究主要集中在時間窗、用戶需求和交通狀況的不確定性方面。Zarandi，等[4]假設顧客需求和車輛行駛時間是模糊變量，提出了不確定型電動汽車選址路徑問題；邵賽[5]結合車輛行駛的實際環境，分別研究了考慮動態需求和動態行駛時間的電動汽車路徑優化問題；Zhang，等[6]對模糊電動汽車路徑優化問題展開了研究。

綜上所述，基于EVRP的研究現狀，結合實際的物流配送背景，考慮到很多時候企業只能通過殘缺的歷史數據了解客戶需求的大概范圍而無法得知其確切取值的情況，本文采用灰參數來描述客戶需求，研究了客戶具有灰色需求時的電動汽車路徑優化問題，以最小化配送成本為目標建立了電動汽車路徑優化模型，并設計了嵌套灰色模擬技術的蟻群算法進行求解。

2 問題描述及數學模型

2.1 問題描述與假設

本文以單個配送中心、多個客戶點和多個充電站組成的物流配送網絡為研究對象。電動物流車從配送中心出發，按照一定的順序將貨物配送給客戶，任務結束后返回配送中心。配送途中，考慮到電動汽車的行駛里程限制，若車輛剩余電量不足以訪問下一個客戶點或返回配送中心，電動物流車可以訪問附近的充電站進行充電。在滿足電動物流車電量約束、載貨量約束和客戶時間窗約束的條件下，確定電動物流車的最佳行駛路線，使得總配送成本最小。考慮到EVRP問題的復雜性，為了便于建模和求解，作出了如下假設：

假設1 配送中心、客戶點和充電站的位置均已知；

假設2 電動物流車從配送中心出發，依次服務各客戶點后返回配送中心，途中可以訪問充電站進行充電；

假設3 客戶的需求量是灰色的，采用灰數來描述客戶需求；

假設4 每個客戶都存在配送的時間窗要求，若車輛未能在約定的時間窗內到達，會產生相應的懲罰費用；

假設5 車輛離開配送中心和充電站時均為滿電狀態；

假設6 電動物流車的充電量與充電時間成正比，耗電量與行駛距離成正比。

2.2 符號與變量說明

0：配送中心；

N：客戶點集合；

R：充電站集合；

S={0}?N?R：所有節點的集合；

V：電動物流車集合；

f：每輛車的固定使用成本；

dij：節點i到節點j的行駛距離；

a：電動汽車單位距離行駛費用；

Q：車輛最大載重；

?qi：客戶點i的灰需求量；

B：電動物流車電池最大容量；

b1ik和b2ik：分別表示車輛k到達和離開節點i時的電量；

e：單位距離的電量消耗系數；

g：充電樁的充電速率；

ESik：車輛k在充電站i的充電量；

β：公共充電站的單位充電費用；

[E Ti,LTi]：客戶滿意時間窗；

α1、α2：分別為車輛早于和晚于客戶滿意時間窗到達時的單位時間懲罰成本；

tsik：車輛k在客戶點i的服務時間；

tcik：車輛k在充電站i的充電時間；

tijk：車輛k從節點i到節點j的行駛時間；

M：一個足夠大的實數；

2.3 數學模型

根據上述問題的假設和分析，建立了考慮灰需求的電動汽車路徑優化模型。

其中，式（1）為總成本目標函數，總成本包括車輛固定成本、運輸成本、違反客戶時間窗的懲罰成本和電動物流車充電成本；式（2）表示每個客戶點僅由一輛車服務一次；式（3）為各節點進出平衡約束；式（4）表示每輛車的實際載重不得超過車輛最大載重；式（5）表示電動汽車離開配送中心和充電站時均為滿電狀態；式（6）表示電動汽車在客戶點處進行服務時不額外消耗電量；式（7）表示車輛k離開節點i和到達下一個節點j的電量關系；式（8）表示電動汽車的剩余電量不超過電池容量；式（9）表示車輛k離開節點i和到達下一個節點j的時間關系；式（10）表示車輛k到達和離開節點i的時間關系；式（11）表示車輛的充電時間；式（12）和式（13）表明決策變量為0-1變量。

3 模型轉換與求解

3.1 模型轉換與處理

上述EVRP模型，車輛載重約束中含有客戶灰需求?qi，在到達客戶點之前，無法得知其確切取值，這導致該模型無法直接進行求解。因此，在進行求解之前，需要先將模型進行轉化。根據灰色機會約束規劃理論，將該模型轉化為可進行求解的灰色機會約束規劃模型[7-8]。

其中，f為總配送成本；Pr{·}表示事件{·}發生的概率，此處表示灰色約束條件成立的概率；α為置信水平；?q=[? q1,?q2,...,?qn]表示客戶的灰需求量，Cj(X)≤0表示除灰色約束之外的其他約束。

針對轉化后的模型，當且僅當Pr{gi(X ,?q)≤0,i=1,2,...,t}≥α，即車輛配送貨物的重量之和不超過車輛最大載重的概率大于等于α時，得到的方案才可行。

3.2 灰色模擬檢驗

對于轉化后的模型，可以采用灰色模擬技術[7]來實現灰色約束條件的檢驗。通過對灰數進行白化處理，得到客戶灰需求量的白化值矩陣，再通過白化值矩陣來檢驗灰色約束條件成立的概率。假設每個客戶點生成N個白化值進行N次實驗，N'為實驗過程中灰色約束條件成立的次數。若N'/N≥α，則灰色約束成立，否則不成立。具體步驟如下：

Step1 參數初始化，設置N'=0；

Step2 利用白化權函數生成各客戶點的白化值矩陣；

Step3 根據白化值矩陣，檢驗灰色機會約束條件成立的概率。若Pr{gi(X ,?q )≤0,i=1,2,...,t}≥α成立，則N'++；

Step4 重復Step2、Step3共N次；

Step5 若N'/N≥α則成立，否則不成立。

3.3 模型求解

帶充電站的電動汽車路徑優化問題是典型的NP-hard問題，同時考慮客戶的灰色不確定需求，進一步增加了求解的難度。蟻群算法采用分布式并行計算機制，利用信息正反饋來優化尋優過程，相較于其他啟發式算法，蟻群算法的求解速度較快、全局搜索能力也較強[9]。因此，本文擬采用蟻群算法求解電動汽車路徑優化問題，并在傳統蟻群算法的基礎上，設計了嵌套灰色模擬技術的蟻群算法進行求解。具體步驟如下：

Step1 初始化算法參數。包括螞蟻數量、初始信息素濃度、算法迭代次數、灰色模擬次數、置信水平等。

Step2 單只螞蟻從配送中心出發，根據狀態轉移策略選擇下一個要訪問的客戶節點。

Step3 利用灰色模擬技術進行檢驗，若灰色機會約束條件成立，將選中的客戶點加入到當前路線中并更新禁忌表；若灰色機會約束條件不成立，螞蟻返回配送中心并在禁忌表中加入0。

Step4 重復Step2、Step3直至單只螞蟻完成對所有客戶點的訪問。禁忌表中每兩個0之間的數字就代表每輛車訪問客戶點的順序。

Step5 判斷車輛在配送過程中是否需要充電。計算每條路徑上兩節點之間的電量消耗，判斷車輛到達各客戶點時的剩余電量。若剩余電量不足以支撐車輛訪問下一個客戶點，則需要在兩個節點之間插入充電站進行充電。

Step6 對m只螞蟻全部執行上述操作，計算每只螞蟻對應的總配送成本，選出所有螞蟻中總配送成本最小的螞蟻所對應的配送路線。

Step7 更新全局信息素，進行下一次迭代。

Step8 判斷是否達到終止條件。若未達到最大迭代次數，繼續進行循環；若達到最大迭代次數，輸出所有迭代中的最優配送方案，終止算法。

4 算例求解與結果分析

4.1 算例概述

本文研究的是考慮灰需求和充電站的電動汽車路徑優化問題，目前尚無標準測試算例。為驗證模型和算法的有效性，隨機選取了Solomon標準算例集RC2-2-5中的客戶點數據，結合本文的研究內容和實際物流公司城市配送的特點，對數據進行進一步的調整和擴展，得到1個配送中心、30個客戶點和10個公共充電站的測試數據（1D-30C-10P）。配送中心、客戶點和充電站的信息見表1和表2。

表1 配送中心、充電站坐標

表2 客戶點坐標及灰需求量

4.2 算例求解

本文應用MATLAB R2018a編程軟件進行仿真，通過多次試驗，選擇了一組較好的參數值，設定蟻群算法參數為α=1，β=4，ρ=0.7，螞蟻數量為45只，算法迭代次數為200次。在求解灰色機會約束規劃模型時，需要事先確定置信水平α，即灰色機會約束條件成立的概率。考慮到不同決策者風險偏好程度的不同，為研究決策者風險偏好對最優配送路徑的影響，改變置信水平α的取值，分別取α為0.6、0.8和0.95，并在不同的置信水平下分別進行10次仿真實驗，得到的最優結果見表3和表4。

表3 不同置信水平下的最小成本

表4 不同置信水平下的最優配送方案

從表3、表4可以看出，隨著置信水平α的增加，總配送成本也呈現出遞增的趨勢。置信水平越低，意味著配送過程中違反灰色機會約束的可能性越大，越可能出現無法滿足客戶配送需求的情況，企業在降低配送成本的同時，承擔著較大的客戶流失的風險；置信水平越高，總配送成本也越高，客戶的需求越能被滿足，企業承擔的風險相對較低。因此，在進行決策時，不同的企業可以根據自身的風險承受能力以及領導者的決策偏好選擇不同的置信水平，得到該置信水平下的最優配送方案。

5 結語

利用電動物流車進行城市配送，需要考慮到車輛中途訪問充電站進行充電的情況，因此區別于傳統的車輛路徑問題。本文在電動汽車城市配送問題中，考慮了客戶的灰色不確定需求，建立了考慮灰需求的電動汽車路徑優化模型，根據灰色機會約束規劃理論將其轉化為對應的灰色機會約束模型，并設計了嵌套灰色模擬技術的蟻群算法尋找最優配送方案。本文為決策者在灰色不確定的情況下進行決策提供了參考，決策者可以依據企業自身的情況及決策風險偏好選擇合適的置信水平，置信水平越高，總配送成本越高，企業承擔的風險越小。

由于交通狀況、電動汽車的充電及能耗等因素的影響，現實中的電動汽車配送網絡較為復雜，未來將進一步考慮配送時間窗、車輛充放電過程的不確定性，以更加貼合實際物流環境中的電動汽車配送問題。