陳希瓊，胡大偉，王 寧

(長(zhǎng)安大學(xué)運(yùn)輸工程學(xué)院，陜西西安 710064)

1 引言

選址-路徑問(wèn)題(location-routing problem，LRP)集成處理設(shè)施選址和車輛路徑兩個(gè)關(guān)鍵物流決策問(wèn)題.傳統(tǒng)LRP 研究的車輛路徑問(wèn)題(vehicle routing problem，VRP)中，客戶僅存在取貨或送貨單一需求，而現(xiàn)實(shí)物流系統(tǒng)中，通常存在需要同時(shí)提供送貨和取貨服務(wù)的客戶，且要求在訪問(wèn)中同時(shí)完成取送貨，如:需要回收空瓶的飲料、鮮奶及啤酒配送.

針對(duì)所有需求點(diǎn)均有取送兩層需求的物流配送問(wèn)題，Min[1]首次定義了考慮同時(shí)取送貨的VRP(VRP with simultaneous pickup and delivery，VRPSPD)，研究中心圖書館與地方圖書館之間圖書發(fā)送與回庫(kù)問(wèn)題.之后VRPSPD被廣泛研究:如多車場(chǎng)VRPSPD[2]、不同車型VRPSPD[3]、帶時(shí)間窗VRPSPD[4-5]、時(shí)間依賴型VRPSPD[6]等，以環(huán)保為出發(fā)點(diǎn)研究低碳約束[7-8]和最小化燃油消耗[9]的VRPSPD引起諸多學(xué)者的興趣.陳希瓊等[10]研究同時(shí)考慮車輛容量和距離約束的VRPSPD雙目標(biāo)模型，并采用蟻群算法進(jìn)行求解.

VRPSPD的廣泛研究表明考慮同時(shí)取送貨在物流決策中的重要性，然而考慮同時(shí)取送貨的LRP(LRP with simultaneous pickup and delivery，LRPSPD)近期才開始被少數(shù)學(xué)者關(guān)注.Karaoglan等[11-12]最早提出LRPSPD并進(jìn)行了持續(xù)研究，構(gòu)建了其初始模型，先后采用分支切面法、混合遺傳算法求解該模型;隨后，提出了基于節(jié)點(diǎn)和基于弧的混合整數(shù)規(guī)劃LRPSPD模型，構(gòu)造了LRPSPD測(cè)試算例集，并設(shè)計(jì)兩階段模擬退火算法[13]和模因算法[14]求解模型.Yu等[15]設(shè)計(jì)多起點(diǎn)模擬退火算法，基于文獻(xiàn)[13]構(gòu)造的算例，求解LRPSPD;在進(jìn)一步研究中[16]，額外生成了客戶數(shù)達(dá)318的4組算例，設(shè)計(jì)改進(jìn)的模擬退火算法進(jìn)行求解.孫青偉等[17]基于實(shí)際案例研究了多車型LRPSPD.Kartal等[18]研究單一指派p-中位轉(zhuǎn)運(yùn)站LRPSPD，Karimi[19]對(duì)樞紐選址VRPSPD 進(jìn)行研究，不同于傳統(tǒng)LRPSPD，文獻(xiàn)[18-19]允許樞紐間轉(zhuǎn)運(yùn).Fan等[20]基于構(gòu)造算法、局部搜索和變鄰域算法提出多起點(diǎn)混合啟發(fā)式算法求解兩階段LRPSPD;郭放等[21]研究前置倉(cāng)選址VRPSPD.

文獻(xiàn)中考慮同時(shí)取送貨的多目標(biāo)優(yōu)化研究主要針對(duì)VRPSPD，幾乎不能找到LRPSPD多目標(biāo)優(yōu)化研究.Garc′?a-N′ajera[22]對(duì)取送貨問(wèn)題的多目標(biāo)研究進(jìn)行調(diào)查，指出工作量平衡目標(biāo)應(yīng)被考慮，但在其提出的六目標(biāo)模型中并未包括工作量平衡目標(biāo).同時(shí)，多目標(biāo)優(yōu)化求解復(fù)雜，由于對(duì)多目標(biāo)進(jìn)行轉(zhuǎn)化處理具有不能兼顧多個(gè)目標(biāo)的局限性，但近年來(lái)同時(shí)兼顧多個(gè)目標(biāo)的Pareto解集成為研究重點(diǎn)，如Anderluh等[23].

LRPSPD研究通常以最小化總成本為目標(biāo)，然而現(xiàn)實(shí)運(yùn)作中決策者需要根據(jù)其他可能的情況進(jìn)行決策，如考慮客戶滿意度、碳排放、各車輛的工作量平衡等.本文在文獻(xiàn)[10]的基礎(chǔ)上，集成選址決策，考慮車輛容量和車輛行駛里程約束，建立以最小化總成本與最小化各路徑間最大長(zhǎng)度差為目標(biāo)的雙目標(biāo)模型，該模型為文獻(xiàn)中首次最小化總成本，同時(shí)以平衡各車輛的工作量為目標(biāo)的多目標(biāo)LRPSPD研究.鑒于變鄰域搜索算法在求解組合優(yōu)化問(wèn)題中較好的性能，本文構(gòu)造四類鄰域結(jié)構(gòu)設(shè)計(jì)多起點(diǎn)變鄰域搜索算法，并設(shè)計(jì)多蟻群構(gòu)造多個(gè)初始解作為變鄰域搜索的多起點(diǎn)，對(duì)文獻(xiàn)中的LRPSPD算例進(jìn)行求解分析.

2 問(wèn)題描述和數(shù)學(xué)模型構(gòu)建

2.1 問(wèn)題描述與符號(hào)說(shuō)明

定義圖G(N，A)，其中NN0∪NC，N0，NC分別表示車場(chǎng)集合、需求點(diǎn)集合.每個(gè)潛在車場(chǎng)k ∈N0有固定的開放與營(yíng)運(yùn)成本fk，容量為Ck，每個(gè)客戶i的取送貨需求分別為pi，di.假定車場(chǎng)有足夠可供派遣的完全相同的車隊(duì)，每輛車最大容量為Q、最大行駛距離為L(zhǎng)，派遣每輛車的固定成本F.每輛車從車場(chǎng)出發(fā)，通過(guò)恰當(dāng)?shù)男旭偮肪€有序訪問(wèn)該線路上的所有客戶，然后回到車場(chǎng)，每輛車最多執(zhí)行一條路徑的服務(wù).A{(i，j):為邊集，每條邊(i，j)∈A的行駛成本即距離為cij.本文研究的LRPSPD可描述為:從一系列潛在車場(chǎng)中選擇開放的車場(chǎng)，并從開放的車場(chǎng)派出車輛，在不超過(guò)車輛容量和最大行駛里程的約束下，找到服務(wù)所有客戶后回到原車場(chǎng)的路徑，使成本最小化，同時(shí)最大可能地平衡各路徑的總長(zhǎng)度(即最小化最長(zhǎng)路徑與最短路徑的里程差).雙目標(biāo)LRPSPD模型中的變量定義如下.

決策變量:xij1表示先后連續(xù)訪問(wèn)客戶i，j，否則xij0;yk1表示備選車場(chǎng)k被選中開放，否則yk0;zik1表示節(jié)點(diǎn)i分配給車場(chǎng)k，否則zik0.

其他變量:Yij表示在(i，j)上時(shí)裝載的送貨量;Zij表示在(i，j)上時(shí)裝載的取貨量;li表示訪問(wèn)客戶i時(shí)的累積行駛里程;tLmax(min)表示最長(zhǎng)(最短)的被派遣車輛行駛路徑長(zhǎng)度.

2.2 模型構(gòu)建

基于以上問(wèn)題描述與符號(hào)，構(gòu)建以下雙目標(biāo)LRPSPD數(shù)學(xué)模型:

目標(biāo)函數(shù)(1)使總成本最小，包括路徑成本、車場(chǎng)的開放與運(yùn)營(yíng)固定成本和派遣車輛的成本，目標(biāo)式(2)最小化車輛的最大行駛里程差，以平衡各車輛的工作量.式(3)-(4)規(guī)定所有客戶均被分配給開放的車場(chǎng)且僅被訪問(wèn)一次，約束(5)保證進(jìn)入某客戶的弧總數(shù)等于從該客戶出來(lái)的弧總數(shù)，約束(6)-(8)消除了未始于車場(chǎng)或止于車場(chǎng)的子路徑，且當(dāng)且僅當(dāng)分配給相同的車場(chǎng)時(shí)，才有可能被連續(xù)訪問(wèn)，式(9)-(10)為車場(chǎng)容量約束，式(11)-(12)為訪問(wèn)客戶點(diǎn)前后的流量平衡約束，同時(shí)表明客戶的需求在一次訪問(wèn)中全部滿足，約束(13)保證從某開放車場(chǎng)運(yùn)出的裝載量等于分配給該車場(chǎng)的所有客戶的送貨總需求，約束(14)保證在任意弧上的裝載量均不超過(guò)車輛容量，約束式(15)-(18)是對(duì)上下界進(jìn)行限定，約束(19)-(21)保證車輛運(yùn)送距離不超出最大可行駛距離，且當(dāng)且僅當(dāng)車被派遣時(shí)才存在累積行駛距離;式(22)-(23)界定了車輛行駛路徑的長(zhǎng)度，式(24)-(27)為各變量的取值約束.

通常，有效不等式的加入可縮緊模型約束，從而消除模型解空間的無(wú)效片段.式(28)為式(14)的有效替換，其中M為極大常數(shù)，該式表示當(dāng)且僅當(dāng)客戶被連續(xù)訪問(wèn)時(shí)，弧上存在流量，且不超過(guò)車輛的最大容量.

3 多起點(diǎn)變鄰域搜索算法

由于雙目標(biāo)模型并不存在絕對(duì)的最優(yōu)解，因此本文設(shè)計(jì)優(yōu)化算法求解模型Pareto解.變鄰域搜索(variable neighborhood search，VNS)作為一種元啟發(fā)式方法已被成功應(yīng)用于解決多種優(yōu)化問(wèn)題，尤其對(duì)于大規(guī)模組合優(yōu)化問(wèn)題效果較好.VNS求解性能受初始解影響較大，因此本文構(gòu)造有一定關(guān)聯(lián)的多個(gè)初始解，并基于各初始解進(jìn)行變鄰域搜索，稱為多起點(diǎn)變鄰域搜索算法(multi-start VNS)，算法流程如圖1所示.分步說(shuō)明如下:

圖1 多起點(diǎn)變鄰域搜索算法流程圖Fig.1 Flow chart of mmulti-start VNS

步驟1初始化VNS產(chǎn)生可行解及不可行解的次數(shù)nF0，nINF0及多起點(diǎn)數(shù)nMS0，并分別設(shè)定其最大值;

步驟2分別基于選址蟻群、分配蟻群及車輛路徑安排蟻群構(gòu)造初始解;

步驟3從初始解的多個(gè)鄰域中隨機(jī)選擇一個(gè)鄰域結(jié)構(gòu)進(jìn)行搜索;

步驟4檢查產(chǎn)生的鄰域解是否為可行解.

若不可行:則nINFnINF+1并判斷生成不可行解的次數(shù)是否達(dá)到最大，否則回到步驟3，是則跳到步驟5;

若可行:則判斷該可行解是否為Pareto解，若是則產(chǎn)生了多目標(biāo)問(wèn)題的新解，本輪搜索結(jié)束，初始化nF0，nINF0，開始新一輪搜索，回到步驟3;

若不是Pareto解，則nFnF+1并判斷是否滿足達(dá)到最大可生成可行解次數(shù)，回到步驟3或轉(zhuǎn)步驟5;

步驟5判斷是否達(dá)到最大起點(diǎn)數(shù):若nMSnMS+1否則同時(shí)更新各蟻群信息素矩陣，回到步驟2;若是則輸出并結(jié)束程序.

根據(jù)以上步驟說(shuō)明，變鄰域搜索的每一個(gè)初始解(起點(diǎn))，均在每一次迭代開始時(shí)，基于此前迭代產(chǎn)生的解以及更新后的信息素由多蟻群算法產(chǎn)生，從而使變鄰域搜索的多個(gè)起點(diǎn)間相互關(guān)聯(lián)，且隨迭代發(fā)生變鄰域搜索的起點(diǎn)對(duì)應(yīng)的解更優(yōu).

3.1 多蟻群構(gòu)造算法初始解

蟻群算法最初被Dorigo等[24]應(yīng)用于旅行商問(wèn)題(travelling salesman problem，TSP)，取得了很好的應(yīng)用效果.本文將LRPSPD分解為選址、分配、路徑選擇3個(gè)子問(wèn)題，采用多蟻群算法思想，設(shè)計(jì)對(duì)應(yīng)的3個(gè)蟻群，以構(gòu)造LRPSPD變鄰域搜索初始解.

3.1.1 選址

第s次構(gòu)造初始解時(shí)，ps為開放車場(chǎng)的數(shù)量，表示車場(chǎng)k上的信息素強(qiáng)度，Us為還未被螞蟻選中的車場(chǎng)集合，ηk為表達(dá)車場(chǎng)k特性的效用函數(shù).首先根據(jù)式(29)確定需開放的車場(chǎng)數(shù)，后根據(jù)式(30)-(31)所示準(zhǔn)則依次選出合適的車場(chǎng)，q為[0，1]的隨機(jī)數(shù)，q0為[0，1]間預(yù)先設(shè)定數(shù)，參數(shù)α表示ηk相對(duì)于信息素對(duì)轉(zhuǎn)移概率的影響程度.

3.1.2 分配

第s個(gè)初始解構(gòu)造過(guò)程中，開放的車場(chǎng)k與客戶i之間的信息素為，對(duì)當(dāng)前還未分配的任意客戶i，根據(jù)以下準(zhǔn)則從開放的車場(chǎng)Os中選擇車場(chǎng)k，并將客戶i分配給車場(chǎng)k.

其中:φik為行駛成本的倒數(shù)，表示將當(dāng)前客戶分配給行駛成本較小的車場(chǎng);φik為Φik的倒數(shù)，Φik表示為包含當(dāng)前需分配的客戶的條件下，當(dāng)前已分配給車場(chǎng)的所有客戶總?cè)∷拓浀钠胶?，為包含?dāng)前客戶的所有已分配給車場(chǎng)的客戶集合，q′為[0，1]的隨機(jī)數(shù)，為[0，1]間預(yù)先設(shè)定數(shù)，參數(shù)β和γ分別表示φik與φik相對(duì)于信息素對(duì)轉(zhuǎn)移概率的影響程度

分配結(jié)束后，檢查分配給各車場(chǎng)的所有需求點(diǎn)總需求是否超出車場(chǎng)容量，并對(duì)分配給容量超出的車場(chǎng)的需求點(diǎn)進(jìn)行調(diào)整，調(diào)整方案?jìng)未a如下.

算法1:

3.1.3 路徑選擇

選址、分配確定后，LRPSPD可視為多個(gè)單車場(chǎng)的VRPSPD，該節(jié)分別確定分配給同一車場(chǎng)的需求點(diǎn)的訪問(wèn)路徑.為構(gòu)造第s個(gè)初始解時(shí)弧(i，j)上的信息素強(qiáng)度，螞蟻根據(jù)各條路徑上的信息量和反映網(wǎng)絡(luò)本身特性的效用函數(shù)決定下一步要轉(zhuǎn)移的點(diǎn)，Pij表示螞蟻由節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率.其中q′′為均勻分布在[0，1]上的隨機(jī)數(shù)，為預(yù)先設(shè)定的值，當(dāng)q≤q0時(shí)，螞蟻直接移動(dòng)到使效用函數(shù)取最大值的點(diǎn)j如式(35)，否則按式(36)所示概率進(jìn)行輪盤賭選擇轉(zhuǎn)移到j(luò)點(diǎn)，越大表明螞蟻隨機(jī)性越小，Zis表示第s次初始解螞蟻到達(dá)節(jié)點(diǎn)i上時(shí)未訪問(wèn)的節(jié)點(diǎn)集合，當(dāng)達(dá)到行駛距離約束或容量約束條件時(shí)，返回車場(chǎng)，并再次從該車場(chǎng)開始構(gòu)建新的路徑，直到所有節(jié)點(diǎn)都被訪問(wèn)，即

式(38)中當(dāng)點(diǎn)的凈裝載量等于點(diǎn)的凈卸載量時(shí)ζij1.ψij與ζij體現(xiàn)網(wǎng)絡(luò)本身特征，結(jié)合螞蟻轉(zhuǎn)移規(guī)則反應(yīng)出螞蟻具有偏好以最大節(jié)約距離服務(wù)取送貨需求差最小的客戶的特性.參數(shù)β′和γ′分別表示ψij與ζij相對(duì)于信息素對(duì)轉(zhuǎn)移概率的影響程度.

3.2 多目標(biāo)變鄰域搜索

本文變鄰域搜索采用四類鄰域結(jié)構(gòu):路徑內(nèi)點(diǎn)序列操作、路徑間點(diǎn)序列操作、從不同車場(chǎng)出發(fā)的兩條路徑交換、開放車場(chǎng)與未開放車場(chǎng)交換.每次鄰域操作均在隨機(jī)選擇的擾動(dòng)機(jī)制下被執(zhí)行，且均以找到Pareto解為目標(biāo)，變鄰域搜索過(guò)程定義了最大無(wú)效操作次數(shù)(產(chǎn)生不可行解次數(shù)nINF-max、產(chǎn)生可行但為支配解的次數(shù)nF-max)，即若產(chǎn)生nINF-max個(gè)不可行解或nF-max)個(gè)支配解后，仍未找到新的Pareto解，則搜索結(jié)束;若找到新的Pareto解，則初始化nINF0，nF0，繼續(xù)執(zhí)行變鄰域操作.以下為第s次迭代中多目標(biāo)變鄰域搜索操作偽代碼.

算法2:

3.2.1 路徑內(nèi)操作

1) 插入:隨機(jī)選擇路徑上的需求點(diǎn)子序列σ，從當(dāng)前位置刪除，插入到該路徑的其他位置，|σ|小于該路徑上總需求點(diǎn)個(gè)數(shù).如圖2中a所示.

2) 交換:隨機(jī)選擇路徑上兩個(gè)不重疊的子序列(σ1，σ2)，交換兩個(gè)序列的位置，子序列上需求點(diǎn)個(gè)數(shù)根據(jù)該路徑上總需求點(diǎn)個(gè)數(shù)隨機(jī)選擇，|σ1|+|σ2|不超過(guò)該路徑上總需求點(diǎn)個(gè)數(shù).如圖2中b所示.

3) 翻轉(zhuǎn):隨機(jī)選擇路徑上的需求點(diǎn)子序列σ，在原位置進(jìn)行翻轉(zhuǎn)，|σ|小于該路徑上總需求點(diǎn)個(gè)數(shù).如圖2中c所示.

圖2 路徑內(nèi)局部搜索操作示意圖Fig.2 Procedure of Intra-route local search

3.2.2 路徑間操作

1) 插入:隨機(jī)選擇一條路徑r1，并隨機(jī)選擇子序列σ從當(dāng)前位置刪除，隨機(jī)選擇另一條路徑r2，將σ插入該路徑中的任意位置，|σ|不超過(guò)該路徑上總需求點(diǎn)個(gè)數(shù)，若|σ|等于r1上總需求點(diǎn)個(gè)數(shù)，則r1整條路徑被插入其他路徑中，刪除路徑r1.如圖3中a所示.

2) 交換:隨機(jī)選擇兩條路徑r1，r2，分別選取子序列(σ1，σ2)，交換兩個(gè)序列的位置.如圖3中b所示.

3) 翻轉(zhuǎn)交換:隨機(jī)選擇兩條路徑r1，r2，分別選取子序列(σ1，σ2)，交換兩個(gè)序列的位置同時(shí)分別將子序列進(jìn)行翻轉(zhuǎn).如圖3中c所示.

圖3 路徑間局部搜索操作示意圖Fig.3 Procedure of Inter-route local search

|σ1|，|σ2|均不超過(guò)路徑r1，r2上總需求點(diǎn)個(gè)數(shù).

3.2.3 路徑操作

隨機(jī)選擇從不同車場(chǎng)出發(fā)的兩條路徑，整條路徑進(jìn)行交換，即交換兩條路徑的出發(fā)車場(chǎng).

3.2.4 車場(chǎng)操作

若存在未開放的車場(chǎng)，隨機(jī)選擇一個(gè)開放車場(chǎng)D1與一個(gè)未開放車場(chǎng)D2，交換兩個(gè)車場(chǎng)，即開放車場(chǎng)D2，將從原開放車場(chǎng)D1出發(fā)的所有路徑，全部調(diào)整為從D2出發(fā)，關(guān)閉車場(chǎng)D1.

3.3 信息素更新準(zhǔn)則

基于一個(gè)初始解達(dá)到最大變鄰域搜索次數(shù)后，輸出產(chǎn)生的Pareto解集.基于第3.1節(jié)中描述的多蟻群構(gòu)造初始解的方法，以及Pareto解集對(duì)多蟻群信息素矩陣的影響，構(gòu)造新的初始解，本文設(shè)計(jì)選址、分配和路徑選址蟻群信息素更新主要受Pareto解集中總成本最小(各車輛行駛旅程差最大)及各車輛行駛旅程差最小(總成本最大)兩個(gè)特殊的Pareto解的影響.令該兩個(gè)Pareto解為X1，X2，任意Pareto解對(duì)應(yīng)的兩個(gè)目標(biāo)函數(shù)值分別為f1(·)，f2(·)，各蟻群的信息素更新準(zhǔn)則如式(39)-(44)，式中ρ，ρ′，ρ′′為各蟻群信息素?fù)]發(fā)系數(shù)，nk為分配給車場(chǎng)的需求點(diǎn)數(shù)量，tL(·)為對(duì)應(yīng)解的總車輛行駛路徑長(zhǎng).設(shè)選址、分配和路徑選址蟻群初始信息素水平為1/fk、極小的數(shù)和1/dij，

4 算例求解與結(jié)果分析

根據(jù)以往文獻(xiàn)，對(duì)蟻群算法中的參數(shù)范圍進(jìn)行經(jīng)驗(yàn)性設(shè)置:信息素?fù)]發(fā)系數(shù)ρ，ρ′，ρ′′ ∈[0.2，0.8]，啟發(fā)式因子α ∈[2，5]，β，β′ ∈[0，5]，γ，γ′ ∈[0，5]，隨機(jī)因子q0，∈[0.2，0.8].初次分配結(jié)束后，對(duì)車場(chǎng)容量進(jìn)行檢查，若容量超出對(duì)需求點(diǎn)的分配進(jìn)行調(diào)整以確定是否需要額外開放一個(gè)車場(chǎng)，分配調(diào)整的最大次數(shù)nA-max∈[0.5，1，1.52]×|NC|.MSVNS中起點(diǎn)數(shù)nMS∈[0.5，1，1.52]×|N|，每一次VNS允許連續(xù)產(chǎn)生可行且為支配解的最大次數(shù)nF-max∈[0.5，1，1.52]×|N|，允許連續(xù)產(chǎn)生不可行解的最大次數(shù)為nINF-maxnF-max.基于以上參數(shù)范圍，從本文采用的Karaoglan等[13]中隨機(jī)選擇4組不同規(guī)模的算例進(jìn)行多組參數(shù)組合試驗(yàn)，獲得最佳解的參數(shù)組合為:ρ，ρ′，ρ′′0.2，0.2，0.2，α2，β，β′3，3，γ，γ′1，2，q0，0.7，0.7，0.8，nA-max|NC|，nMS|N|，nF-max2×|N|.

4.1 算例求解結(jié)果

Karaoglan等[13]根據(jù)兩種不同的需求拆分策略(demand separate strategy，DSS)基于兩組LRP算例構(gòu)造了4組測(cè)試算例:BAM，BSN，PAM，PSN，分別簡(jiǎn)稱B，P系列，應(yīng)用文獻(xiàn)[13]中的算例，并設(shè)置最大行駛里程為一個(gè)較大的常數(shù).運(yùn)用MATLAB(R2014b)編寫代碼，在Windows 7操作系統(tǒng)，處理器為Intel(R)Core(TM)i5-4460(3.20 Ghz)，8 GB內(nèi)存的個(gè)人電腦上運(yùn)行程序，每組算例運(yùn)行10次，不同次運(yùn)行產(chǎn)生的Pareto解存在相互支配，因此綜合10次運(yùn)行結(jié)果得到最優(yōu)Pareto前沿.基于綜合后的最優(yōu)Pareto前沿，決策者可根據(jù)實(shí)際偏好進(jìn)行決策.

4.1.1 邊界Pareto解分析

圖4(a)(b)分別為BAM，PAM系列中隨機(jī)算例的所有解集，最優(yōu)Pareto前沿如菱形所示.圖4(a)中不同解的最大行駛里程差波動(dòng)較大，即不同的選址-路徑?jīng)Q策會(huì)導(dǎo)致不同車輛的工作量相差較大，而圖4(b)中不同決策下車輛的工作負(fù)荷相對(duì)平均.設(shè)近似Pareto解集中100%偏向最小化總成本時(shí)對(duì)應(yīng)的兩個(gè)目標(biāo)函數(shù)值分別為與;100%偏向最小化車輛間最大行駛里程差時(shí)為與則

圖4 不同系列隨機(jī)兩算例10次運(yùn)行近似Pareto解集Fig.4 Pareto solutions of 10 runs for 2 random instances from different series

反映了車輛間最大行駛里程差隨成本變化的最大波動(dòng)率.

表1-2列出各算例的ΔG/C值，B系列算例車輛間最大行駛里程差隨成本變化的最大波動(dòng)率最大值分別達(dá)178.24，235.34，平均值為58.59，86.5，表明B系列算例不同Pareto解對(duì)應(yīng)的選址-車輛路徑方案，在總成本變化不大時(shí)車輛間工作量相差較大，體現(xiàn)出決策時(shí)考慮車輛間工作量平衡目標(biāo)的重要性.而表2中P系列算例的ΔG/C值較小，平均值分別為4.48，14.39，即:在不同決策下，各車輛間工作量均相對(duì)平均.

表1 B系列算例邊界Pareto解Table 1 Pareto with extreme OFVs for instances sets B

表2 P系列算例邊界Pareto解Table 2 Pareto with extreme OFVs for instances sets P

4.1.2 鄰域結(jié)構(gòu)性能分析

為了分析四類鄰域結(jié)構(gòu)對(duì)算法性能的影響，隨機(jī)選取不同規(guī)模的算例，逐一刪除四類鄰域中的某一類鄰域進(jìn)行測(cè)試，獲得成本最小的解，如表3所示，其中Gap%表示刪除鄰域后獲得的解與使用全四類鄰域的解的偏差，如第4列:

由于算法包含多蟻群、多起點(diǎn)和變鄰域搜索3種機(jī)制，在3種機(jī)制的組合下算法達(dá)到較好的性能，而非僅由鄰域結(jié)構(gòu)確定;另外，對(duì)于不同的算例，某一種鄰域操作產(chǎn)生的多樣化具有較大的隨機(jī)性，即某一種鄰域結(jié)構(gòu)操作對(duì)某一算例可能產(chǎn)生更優(yōu)的解、同時(shí)也未可能產(chǎn)生更優(yōu)的解，這解釋了表3中刪除單一鄰域結(jié)構(gòu)后對(duì)解的影響不甚明顯的原因.

表3 鄰域結(jié)構(gòu)性能分析Table 3 Performance analysis of neighborhoods

4.1.3 算法性能分析

本文以100%偏向總成本最小函數(shù)選取近似Pareto解集中成本最小的解與文獻(xiàn)中以最小化總成本為目標(biāo)求得的解進(jìn)行對(duì)比，提取10次運(yùn)行求得解集中成本最小的解，分別以最優(yōu)解和平均解與上界進(jìn)行比較，得到最小偏差(Gap%min)和平均偏差(Gap%Avg).

B系列算例的解與Karaoglan等[11]獲得的上界、B&C算法求得的解、以及模因算法(MA)[16]進(jìn)行對(duì)比，見(jiàn)表4-5，結(jié)果顯示本文提出的MSVNS可在極短的時(shí)間內(nèi)(平均分別為4.3 s，6.12 s)求解BAM，BSN系列所有算例包含成本近似最優(yōu)的Pareto解，與上界相比最優(yōu)解的平均偏差分別為17.57%，17.39%，平均解的平均偏差為17.94%，17.78%，最優(yōu)解與平均解相差小于0.5%表明了算法的穩(wěn)定性.盡管整體上解與上界的偏差相較于B&C有一定的差距，但在求解速度上有明顯優(yōu)勢(shì)，并且部分算例(Perl83-55×15及Perl83-85×7)的解比B&C更優(yōu).

表4 BAM算例MSVNS算法與B&C結(jié)果比較Table 4 Results comparison by MSVNS against B&C for BAM instances

表5 BSN算例MSVNS算法與B&C結(jié)果比較Table 5 Results comparison by MSVNS against B&C for BSN instances

P系列算例的解與文獻(xiàn)[11]上界及B&C獲得的解、以及混合遺傳算法(hybrid genetic algorithm，HGA)[14]求得的解進(jìn)行對(duì)比，如表6-7，結(jié)果表明MSVNS對(duì)P系列算例極好的適應(yīng)性，72個(gè)算例中共46個(gè)算例獲得了比上界更好的解，最好解的平均偏差分別為-1.7，-2.08，平均解的平均偏差分別為-1.59，-1.92，表明算法穩(wěn)定性，同時(shí)說(shuō)明本文提出的MSVNS求得的平均解的結(jié)果優(yōu)于文獻(xiàn)中其他的算法，且求解時(shí)間同樣具有明顯優(yōu)勢(shì).

表6 PAM算例MSVNS算法與文獻(xiàn)中已有結(jié)果比較Table 6 Results comparison by MSVNS against existing results in literature for PAM instances

表7 PSN算例MSVNS算法與文獻(xiàn)中已有結(jié)果比較Table 7 Results comparison by MSVNS against existing results in literature for PSN instances

為進(jìn)一步比較MSVNS求解性能，表8從獲得新最優(yōu)解的數(shù)量及平均求解時(shí)間與文獻(xiàn)[15]中兩種模擬退火(simulated annealing，SA1，SA2)及多起點(diǎn)模擬退火算法(multi-start SA，MSA)進(jìn)行比較.對(duì)比P系列不同規(guī)模算例的求解結(jié)果，MSVNS 僅在50×5規(guī)模算例上獲得的新最優(yōu)解略少于SA，MSA，在其他規(guī)模算例上均獲得了更多最優(yōu)解，解的精度和平均求解時(shí)間均體現(xiàn)出MSVNS求解性能更優(yōu).

表8 不同方法獲得新最優(yōu)解的數(shù)量及平均求解時(shí)間比較Table 8 Number of new best solutions obtained and computational time required by each approach

5 結(jié)論

本文考慮車輛容量和最大行駛里程限制，構(gòu)建了最小化總成本和最小化不同車輛行駛距離最大差以平衡各車輛的工作負(fù)荷的雙目標(biāo)LRPSPD模型.提出一種多起點(diǎn)變鄰域搜索算法(MSVNS)進(jìn)行求解，首先基于多蟻群算法構(gòu)建初始解，基于初始解設(shè)計(jì)四類鄰域結(jié)構(gòu)進(jìn)行隨機(jī)變鄰域多目標(biāo)搜索，根據(jù)所得Pareto鄰域解更新信息素，而后產(chǎn)生新的初始解作為變鄰域搜索起點(diǎn).本文用MSVNS算法求解文獻(xiàn)中的算例，解得Pareto前沿的分布情況說(shuō)明了考慮最小化路徑間最大長(zhǎng)度差目標(biāo)的重要意義.與其他求解LRPSPD方法求解結(jié)果的比較表明了算法在求解速度上的絕對(duì)優(yōu)勢(shì);尤其對(duì)于P系列算例，MSVNS在求解精度和求解時(shí)間均表現(xiàn)出更優(yōu)性能，說(shuō)明MSVNS算法可求得權(quán)衡各目標(biāo)的Pareto解，并使得最小總成本目標(biāo)近似最優(yōu).

文中算法對(duì)B系列與P系列求解結(jié)果精度差異較大，一方面，算法對(duì)于不同算例的普適性需進(jìn)一步提高，另一方面，不同系列算例與不同算法匹配規(guī)律有待進(jìn)一步分析研究.采用容量較小的車輛并派遣其訪問(wèn)偏遠(yuǎn)節(jié)點(diǎn)，對(duì)于平衡車輛的行駛距離，充分利用車輛的裝載空間有重要的意義，因此多車型的LRPSPD為未來(lái)研究的重要方向之一.基于現(xiàn)實(shí)物流情形，同時(shí)考慮如時(shí)間窗約束、隨機(jī)行駛時(shí)間等其他因素的LRPSPD將是非常值得研究的領(lǐng)域.