朱 顥 （湖州職業(yè)技術(shù)學(xué)院，浙江 湖州 313000）

0 引 言

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

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

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

針對(duì)VRPFD，張建勇等[18]考慮以客戶(hù)需求為模糊變量，運(yùn)用遺傳算法求解；郭伏等[19]研究了取貨量和行駛時(shí)間為模糊變量的取送貨混排問(wèn)題。Cao等[20]設(shè)計(jì)了隨機(jī)模擬算法來(lái)估算額外行駛里程；張曉楠等[21]針對(duì)模糊需求變?yōu)檎鎸?shí)值時(shí)出現(xiàn)的計(jì)劃“失敗”，提出了多種返回策略。通過(guò)梳理發(fā)現(xiàn)，現(xiàn)有VRPFD文獻(xiàn)對(duì)將與綠色低碳有關(guān)的碳排放成本作為優(yōu)化目標(biāo)的研究較少，很少考慮客戶(hù)存在同時(shí)取送貨需求的情形。

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

本文研究的FGVRPSPD，考慮客戶(hù)同時(shí)需要配送和取貨服務(wù)，且配送需求量和取貨需求量均為模糊變量，優(yōu)化的目標(biāo)值為碳排放成本。然后建立了相應(yīng)的模糊約束規(guī)劃模型，采用狼群算法進(jìn)行優(yōu)化，并進(jìn)行仿真，通過(guò)仿真驗(yàn)證算法的有效性，并分析了決策者主觀偏好值對(duì)目標(biāo)值的影響。

1 問(wèn)題描述及模型建立

1.1 問(wèn)題描述

在一個(gè)配送網(wǎng)絡(luò)中，包含一個(gè)配送中心和若干個(gè)客戶(hù)。每個(gè)客戶(hù)同時(shí)擁有送貨需求和取貨需求，且需求均為三角模糊數(shù)；配送中心擁有一定數(shù)量的同質(zhì)車(chē)輛，每輛車(chē)均從配送中心出發(fā)，完成服務(wù)后返回配送中心。問(wèn)題各符號(hào)含義如表1所示。

表1 問(wèn)題各符號(hào)所表示的含義

問(wèn)題的限制條件包括：每個(gè)客戶(hù)只能訪問(wèn)一次；當(dāng)車(chē)輛到達(dá)客戶(hù)處時(shí)，車(chē)輛的真實(shí)配送和取貨需求才能確定；車(chē)輛的總裝載量不能超過(guò)最大裝載能力。

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

1.2 碳排放計(jì)算

現(xiàn)實(shí)生活中，車(chē)輛的載重量、行駛距離、路況、車(chē)型、車(chē)速等都會(huì)影響車(chē)輛的碳排放量。本文采用文獻(xiàn)[25]中所提出的碳排放計(jì)算方法，碳排放主要包含：運(yùn)輸?shù)呢浳锂a(chǎn)生的二氧化碳和運(yùn)輸車(chē)輛在運(yùn)輸過(guò)程中自身產(chǎn)生的二氧化碳，由式（1）表示車(chē)輛碳排放成本Fc。

各參數(shù)取值具體如表2所示。

表2 碳排放成本參數(shù)

1.3 預(yù)安排路線

基于以上假設(shè)，建立極小化車(chē)輛碳排放成本的低碳取送貨問(wèn)題模型如下：

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

2 狼群算法

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

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

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

2.2 頭狼產(chǎn)生規(guī)則

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

2.3 游走行為

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

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

圖1 游走行為

2.4 召喚行為

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

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

圖2 召喚行為

2.5 圍攻行為

頭狼以外的其他人工狼執(zhí)行圍攻行為。本文對(duì)于人工狼的圍攻行為采取如下隨機(jī)策略。

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

2.6 狼群更新機(jī)制

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

3 算法流程

Step1：初始化種群規(guī)模popsize、步長(zhǎng)step_a、step_b和step_c、最大游走次數(shù)Tmax、比例因子α、β，隨機(jī)生成初始種群。

Step2：利用隨機(jī)模擬算法計(jì)算各人工狼的適應(yīng)度Yi，并記錄頭狼適應(yīng)度Yleader。

Step3：探狼執(zhí)行游走行為并計(jì)算其適應(yīng)度Yi，若Yi＜Yleader或游走達(dá)到最大次數(shù)Tmax，轉(zhuǎn)Step4，否則繼續(xù)執(zhí)行Step3。

Step4：猛狼執(zhí)行召喚行為并計(jì)算其適應(yīng)度Yi，若Yi＜Yleader，就由猛狼i代替頭狼并展開(kāi)新的召喚行為，若所有猛狼執(zhí)行召喚行為后，均未能代替頭狼，則轉(zhuǎn)Step5。

Step5：更新種群，轉(zhuǎn)Step2，直至達(dá)到最大迭代次數(shù)。

4 實(shí)驗(yàn)分析

由于目前尚無(wú)帶模糊需求的VRPSPD標(biāo)準(zhǔn)測(cè)試案例，因此本文擬以solomn測(cè)試庫(kù)中的c202樣例為例，取前40個(gè)客戶(hù)，對(duì)該測(cè)試數(shù)據(jù)進(jìn)行相應(yīng)調(diào)整：客戶(hù)配送需求量di=（d2i-10，d2i，d2i+10）（其中d2i為原c202測(cè)試庫(kù)中的需求量），原樣例庫(kù)中無(wú)取貨需求量，對(duì)pi=（p1i，p2i，p3i）中的p3i按[0，d2i-10]區(qū)間隨機(jī)生成，且p1i=p3i/3，p2i=2·p3i/3。算法基于Matlab2016編程，運(yùn)行環(huán)境為64位操作系統(tǒng)、Intel（R）Core（TM）i5-5200 CPU、4G內(nèi)存。算法參數(shù)經(jīng)過(guò)多次試驗(yàn)，并考慮運(yùn)行時(shí)間，計(jì)算人工狼適應(yīng)度時(shí)，隨機(jī)模擬次數(shù)為10，其他參數(shù)取值見(jiàn)表3。

4.1 算法有效性分析

以Cr*=0.6為例，算法共隨機(jī)運(yùn)行10次，得到的碳排放成本和使用的車(chē)輛數(shù)如表4所示，總目標(biāo)的平均值為140.13，標(biāo)準(zhǔn)差為1.42，變異系數(shù)為0.010 1。

表4 Cr*為0.6 時(shí)運(yùn)行10 次結(jié)果

以最優(yōu)運(yùn)行結(jié)果為例，其最優(yōu)客戶(hù)路線安排見(jiàn)表5。

表5 Cr*為0.6 時(shí)運(yùn)行最優(yōu)路線

對(duì)應(yīng)的最優(yōu)路徑圖如圖3所示。

圖3 Cr*為0.6 時(shí)最優(yōu)路徑圖

4.2 算法性能分析

在Cr*=0.6，種群規(guī)模popsize=50，最大迭代次數(shù)itermax=100，隨機(jī)模擬次數(shù)10不變的情況下，將本文算法與文獻(xiàn)[18]遺傳算法、標(biāo)準(zhǔn)蟻群算法、文獻(xiàn)[8]改進(jìn)蟻群算法進(jìn)行對(duì)比分析。各算法均分別運(yùn)行10次，所得目標(biāo)值的平均值、最優(yōu)值、標(biāo)準(zhǔn)差等信息見(jiàn)表6所示。

表6 四種算法運(yùn)行10 次的結(jié)果對(duì)比分析

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

通過(guò)對(duì)比發(fā)現(xiàn)，本文所提算法的3個(gè)指標(biāo)要優(yōu)于文獻(xiàn)[18]遺傳算法和標(biāo)準(zhǔn)蟻群算法，稍弱于文獻(xiàn)[8]算法，幾種算法的迭代過(guò)程見(jiàn)圖4所示。

圖4 四種算法最優(yōu)解的迭代過(guò)程

從迭代過(guò)程來(lái)看，在搜索初期，本文算法能較快地搜索到次優(yōu)解，這得益于狼群的信息傳遞與共享機(jī)制，特別是召喚行為中，兩頭完全一樣的人工狼，通過(guò)召喚行為，也能產(chǎn)生新的位置，有效擴(kuò)大了搜索范圍；在搜索后期，三種圍攻行為，能夠幫助人工狼在解空間周?chē)M(jìn)行精細(xì)化搜索。

4.3 決策者主觀偏好值對(duì)目標(biāo)的影響分析

在其他參數(shù)不變的情況下，將Cr*從0.1變化至0.9，分別運(yùn)行10次，得到碳排放成本、所使用車(chē)輛數(shù)的平均值和標(biāo)準(zhǔn)差，見(jiàn)表7。

表7 變化時(shí)碳排放成本和使用車(chē)輛數(shù)變化

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

5 結(jié) 論

本文針對(duì)同時(shí)取送貨的車(chē)輛路徑問(wèn)題，既考慮了客戶(hù)需求的模糊特性，也考慮了將碳排放成本作為優(yōu)化的目標(biāo)值，建立了相應(yīng)的模糊約束規(guī)劃模型，并利用狼群算法進(jìn)行優(yōu)化。通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證了算法的有效性，并與其他算法進(jìn)行了對(duì)比，進(jìn)一步分析了決策者主觀偏好值對(duì)目標(biāo)值的影響。仿真實(shí)驗(yàn)證明，本文所研究的問(wèn)題拓展了VRP的研究領(lǐng)域，具有相應(yīng)的理論和實(shí)際意義。