基于狼群算法的同時取送貨模糊綠色車輛路徑問題

朱 顥 （湖州職業技術學院，浙江 湖州 313000）

0 引 言

同時取送貨模糊綠色車輛路徑問題（Fuzzy Green Vehicle Routing Problem with Simultaneous Pick-up and Delivery，FGVRPSPD）是同時取送貨車輛路徑問題（VRPSPD）、模糊需求車輛路徑問題（VRPFD）和綠色車輛路徑問題（GVRP）的集成問題。其中VRPSPD要求在給客戶提供配送服務的同時，還要提供取件服務，例如隨著電子商務的快速發展，消費者在網購的同時，存在其他快遞退貨的可能。VRPFD是一類考慮了客戶需求具有模糊性的VRP問題，現實生活中促銷、政策變化、價格變動等因素的存在導致客戶在收貨時可能會臨時增減訂單中貨品數量，這具有典型的模型特性。GVRP是以降低能耗、減少碳排放為目的的VRP問題，隨著雙碳政策的逐步落實，物流企業有必要考慮優化配送路線，進一步降低碳排放。因此，研究FGVRPSPD具有重要的現實意義。

針對VRPSPD的研究主要集中在VRPSPD的變種、優化目標及優化算法等方面。Min等[1]較早地研究了VRPSPD，并利用公共圖書館分發系統進行了實例驗證。Gajpal等[2]和Subramanian等[3]分別利用蟻群算法、由可變鄰域下降和隨機鄰域排序組成的并行算法對VRPSPD問題進行求解。Cai等[4]和Avci等[5]依次對含異質車隊的VRPSPD進行研究，運用改進的遺傳算法和基于禁忌搜索的混合局部搜索算法進行求解。Qin等[6]以碳排放成本作為優化目標，運用自適應遺傳爬山算法求解。吳騰宇等[7]考慮了O2O模式下的VRPSPD，當客戶需求實時出現時，配送車輛需返回原點取貨。陳希瓊等[8]以運輸成本和車輛行駛里程的均衡為目標，設計了一種多目標蟻群優化算法。吳廷映等[9]研究了“卡車+無人機”模式下的帶時間窗的VRPSPD，運用自適應大鄰域搜索算法求解。通過梳理以上文獻可知，當前關于VRPSPD的研究主要集中在確定性的環境下，對以客戶需求量為模糊變量的VRPSPD可知。

針對GVRP的研究，Hsu等[10]研究了易逝品的VRPTW，考慮了包括能源消耗成本等在內的總成本。Demir等[11]提出了六種綜合燃油消耗模型。Kuo等[12]構建了基于距離、車速和重量的燃油消耗計算模型。Xiao等[13]設計了基于負載的燃油消耗因子。Bektas等[14]提出污染路徑問題（PRP），運用綜合燃油消耗模型計算燃油消耗。狄衛民等[15]考慮道路擁堵狀態下的多車型GVRP，建立以極小化碳排放成本等為優化目標的模型。周果等[16]研究了多對多越庫配送VRP，考慮了包括碳排放成本、油耗成本在內的總成本。胡蓉等[17]研究了帶二維裝箱約束的綠色開放式VRP，以最小化燃油消耗量為優化目標。通過梳理發現，GVRP的研究也主要集中在確定性的環境上，關于模糊環境下的GVRP研究較少。

針對VRPFD，張建勇等[18]考慮以客戶需求為模糊變量，運用遺傳算法求解；郭伏等[19]研究了取貨量和行駛時間為模糊變量的取送貨混排問題。Cao等[20]設計了隨機模擬算法來估算額外行駛里程；張曉楠等[21]針對模糊需求變為真實值時出現的計劃“失敗”，提出了多種返回策略。通過梳理發現，現有VRPFD文獻對將與綠色低碳有關的碳排放成本作為優化目標的研究較少，很少考慮客戶存在同時取送貨需求的情形。

由于VRP是NP難問題，VRP又可以歸約為FGVRPSPD，故而FGVRPSPD也是NP難問題，因此啟發式算法在VRP問題上的應用較多，如遺傳算法（如文獻[4]等）、蟻群算法（如文獻[2][8]等）、禁忌搜索算法（如文獻[5]）、大鄰域搜索算法（如文獻[9]）。狼群算法作為一種新的群體智能算法[22]，在VRP問題上的應用不多，僅葉勇等[23]應用于多配送中心VRP問題，黃戈文等[24]應用于CVRP，尚未見狼群算法在GVRP和VRPSPD上的應用。

本文研究的FGVRPSPD，考慮客戶同時需要配送和取貨服務，且配送需求量和取貨需求量均為模糊變量，優化的目標值為碳排放成本。然后建立了相應的模糊約束規劃模型，采用狼群算法進行優化，并進行仿真，通過仿真驗證算法的有效性，并分析了決策者主觀偏好值對目標值的影響。

1 問題描述及模型建立

1.1 問題描述

在一個配送網絡中，包含一個配送中心和若干個客戶。每個客戶同時擁有送貨需求和取貨需求，且需求均為三角模糊數；配送中心擁有一定數量的同質車輛，每輛車均從配送中心出發，完成服務后返回配送中心。問題各符號含義如表1所示。

表1 問題各符號所表示的含義

問題的限制條件包括：每個客戶只能訪問一次；當車輛到達客戶處時，車輛的真實配送和取貨需求才能確定；車輛的總裝載量不能超過最大裝載能力。

主要任務：尋找最佳的客戶分派和車輛路線，極小化總的碳排放成本。

1.2 碳排放計算

現實生活中，車輛的載重量、行駛距離、路況、車型、車速等都會影響車輛的碳排放量。本文采用文獻[25]中所提出的碳排放計算方法，碳排放主要包含：運輸的貨物產生的二氧化碳和運輸車輛在運輸過程中自身產生的二氧化碳，由式（1）表示車輛碳排放成本Fc。

各參數取值具體如表2所示。

表2 碳排放成本參數

1.3 預安排路線

基于以上假設，建立極小化車輛碳排放成本的低碳取送貨問題模型如下：

式（8）表示極小化碳排放成本；式（9）表示配送總需求小于可配送總量Q的可信性大于給定的主觀偏好值Cr*；式（10）表示車輛途中載重量小于裝載能力Q的可信性大于給定的主觀偏好值Cr*；式（11）和式（12）表示每個客戶只能被訪問一次；式（13）表示車輛從配送中心出發，完成任務后返回配送中心；式（14）是為了消除子回路而設計的，其中S為車輛所服務的客戶集合。

2 狼群算法

狼群算法是一種基于狼群群體智能、模擬狼群捕食行為及其獵物分配方式的智能優化算法[22]，該算法模擬狼群的游走、召喚、圍攻等三種智能行為以及“勝者為王”的頭狼產生規則和“強者生存”的狼群更新機制。

2.1 人工狼的位置表示及距離

對于人工狼i和j的位置Xi={xi1，xi2，xi3，...，xiNc}和Xj={xj1，xj2，xj3，...，xjNc}，從左邊開始依次檢測對應客戶編號是否相同，若相同，則ek=0，否則ek=1，那么兩匹人工狼的距離表示為式（15）。

2.2 頭狼產生規則

針對每一匹初始人工狼i，令其適應度Yi=Fc（參考文獻[18]中的“隨機模擬算法”，隨機運行10次，取目標函數值的平均值），選擇Yi最小的人工狼為頭狼，并令其適應度為Yleader=（Yi）min；頭狼不執行三種智能行為Yleader，直接進入下次迭代，直到被更強的人工狼代替。

2.3 游走行為

將狼群中除頭狼外最佳的S_num匹人工狼視為探狼（S_num取[popsize/（α+1），popsize/α]中的整數，α為探狼比例因子）。計算探狼i的適應度Yi，若Yi＜Yleader，令Yleader=Yi，由探狼i替代頭狼并發起召喚行為；否則探狼i先向Tmax個方向分別前進一步（游走步長為step_a），并記錄每前進一步后的適應度，直至產生更優位置或者達到最大游走次數Tmax。

本文對于探狼i的游走，采取在i的編碼序列Xi={xi1，xi2，xi3，...，xin}中隨機選取長度為step_a的子序列，進行逆序操作，如圖1所示，此時人工狼游走行為的步長為4。

圖1 游走行為

2.4 召喚行為

將除頭狼以外的人工狼均視為猛狼，展開召喚行為。若猛狼i的適應度Yi＜Yleader，就由猛狼i代替頭狼并展開新的召喚行為，否則猛狼i停止召喚行為后轉入圍攻行為。

本文考慮從頭狼的編碼首部序列中，隨機選取長度為step_b的子序列，將其插入猛狼編碼序列的首部，然后將多余的客戶進行刪除，這樣既體現了狼群的信息傳遞與共享機制，也保留了頭狼的經驗。如圖2所示。

圖2 召喚行為

2.5 圍攻行為

頭狼以外的其他人工狼執行圍攻行為。本文對于人工狼的圍攻行為采取如下隨機策略。

2-opt操作：隨機選擇某線路中長度為step_c的子客戶序列，將其逆序。此操作不同于游走行為中的逆序，游走行為中逆序的子序列客戶可能出現在兩條以上的線路中，對解空間的搜索范圍更大；而2-opt操作中的逆序只涉及一條線路，是對解空間的精細搜索。Insert操作：隨機選擇某路徑中的兩個客戶i和j，將i插到j的前面。Swap操作：隨機選擇某路徑中的兩個客戶i和j，交換其位置。

2.6 狼群更新機制

為了避免算法陷入早熟，在算法中去除適應度最差的R匹人工狼，同時隨機產生R匹人工狼。R取[popsize/（2·β），popsize/β]之間的隨機整數，β為群體更新比例因子 。

3 算法流程

Step1：初始化種群規模popsize、步長step_a、step_b和step_c、最大游走次數Tmax、比例因子α、β，隨機生成初始種群。

Step2：利用隨機模擬算法計算各人工狼的適應度Yi，并記錄頭狼適應度Yleader。

Step3：探狼執行游走行為并計算其適應度Yi，若Yi＜Yleader或游走達到最大次數Tmax，轉Step4，否則繼續執行Step3。

Step4：猛狼執行召喚行為并計算其適應度Yi，若Yi＜Yleader，就由猛狼i代替頭狼并展開新的召喚行為，若所有猛狼執行召喚行為后，均未能代替頭狼，則轉Step5。

Step5：更新種群，轉Step2，直至達到最大迭代次數。

4 實驗分析

由于目前尚無帶模糊需求的VRPSPD標準測試案例，因此本文擬以solomn測試庫中的c202樣例為例，取前40個客戶，對該測試數據進行相應調整：客戶配送需求量di=（d2i-10，d2i，d2i+10）（其中d2i為原c202測試庫中的需求量），原樣例庫中無取貨需求量，對pi=（p1i，p2i，p3i）中的p3i按[0，d2i-10]區間隨機生成，且p1i=p3i/3，p2i=2·p3i/3。算法基于Matlab2016編程，運行環境為64位操作系統、Intel（R）Core（TM）i5-5200 CPU、4G內存。算法參數經過多次試驗，并考慮運行時間，計算人工狼適應度時，隨機模擬次數為10，其他參數取值見表3。

4.1 算法有效性分析

以Cr*=0.6為例，算法共隨機運行10次，得到的碳排放成本和使用的車輛數如表4所示，總目標的平均值為140.13，標準差為1.42，變異系數為0.010 1。

表4 Cr*為0.6 時運行10 次結果

以最優運行結果為例，其最優客戶路線安排見表5。

表5 Cr*為0.6 時運行最優路線

對應的最優路徑圖如圖3所示。

圖3 Cr*為0.6 時最優路徑圖

4.2 算法性能分析

在Cr*=0.6，種群規模popsize=50，最大迭代次數itermax=100，隨機模擬次數10不變的情況下，將本文算法與文獻[18]遺傳算法、標準蟻群算法、文獻[8]改進蟻群算法進行對比分析。各算法均分別運行10次，所得目標值的平均值、最優值、標準差等信息見表6所示。

表6 四種算法運行10 次的結果對比分析

其中文獻[18]中遺傳算法的交叉概率為0.3，變異概率0.03；蟻群算法中信息素權重為1，啟發式信息權重為1，信息素的持久性為0.9。

通過對比發現，本文所提算法的3個指標要優于文獻[18]遺傳算法和標準蟻群算法，稍弱于文獻[8]算法，幾種算法的迭代過程見圖4所示。

圖4 四種算法最優解的迭代過程

從迭代過程來看，在搜索初期，本文算法能較快地搜索到次優解，這得益于狼群的信息傳遞與共享機制，特別是召喚行為中，兩頭完全一樣的人工狼，通過召喚行為，也能產生新的位置，有效擴大了搜索范圍；在搜索后期，三種圍攻行為，能夠幫助人工狼在解空間周圍進行精細化搜索。

4.3 決策者主觀偏好值對目標的影響分析

在其他參數不變的情況下，將Cr*從0.1變化至0.9，分別運行10次，得到碳排放成本、所使用車輛數的平均值和標準差，見表7。

表7 變化時碳排放成本和使用車輛數變化

根據表7數據可以得出如下結論：當Cr*值較小時，雖然所使用的車輛數比較少，但由于預安排路線“失敗”現象比較多，所以碳排放成本比較高，隨著Cr*逐漸增大，“失敗”現象逐漸減少，碳排放成本反而逐步降低；隨著Cr*的進一步增大，派遣的車輛數增大，碳排放成本出現回升。

5 結 論

本文針對同時取送貨的車輛路徑問題，既考慮了客戶需求的模糊特性，也考慮了將碳排放成本作為優化的目標值，建立了相應的模糊約束規劃模型，并利用狼群算法進行優化。通過仿真實驗，驗證了算法的有效性，并與其他算法進行了對比，進一步分析了決策者主觀偏好值對目標值的影響。仿真實驗證明，本文所研究的問題拓展了VRP的研究領域，具有相應的理論和實際意義。