饒 舜，張玉州

（安慶師范大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 安慶 246133）

隨著科技不斷發(fā)展，人們生活半徑也在不斷擴(kuò)張。為了更好地符合實(shí)際優(yōu)化車輛路徑規(guī)劃，大規(guī)模帶容量限制車輛路由問題（LSCVRP）逐漸成為車輛路由問題的研究熱點(diǎn)。Li等為了應(yīng)對(duì)LSCVRP實(shí)際需要，于2005年設(shè)計(jì)了生成大規(guī)模標(biāo)準(zhǔn)測試樣例的方法，構(gòu)造了包含12個(gè)測試樣例的測試集（記為Li），客戶數(shù)由先前的500增至1 200，成為近年來LSCVRP解決方法有效性驗(yàn)證的重要測試對(duì)象[1]。鑒于CVRP屬于NP-hard，由問題知識(shí)或搜索結(jié)果作為啟發(fā)信息而形成的啟發(fā)式算法成為求解CVRP的主流方法[2-7]，其中鄰域探索是發(fā)現(xiàn)更優(yōu)解的一種有效途徑[3,6-7]。

隨著問題規(guī)模的增大，如何引導(dǎo)算法在更有效的解空間進(jìn)行搜索成為處理大規(guī)模問題的關(guān)鍵。文獻(xiàn)[1]、[8]均以LSCVRP為對(duì)象，進(jìn)行了求解方法的設(shè)計(jì)，尤其是文獻(xiàn)[1]生成了規(guī)模達(dá)1 200的標(biāo)準(zhǔn)測試集。然而，這些方法對(duì)如何降低問題搜索復(fù)雜性欠考慮。Kyt?ejoki等就LSCVRP提出了幾種問題求解算法，并利用鄰域搜索（NS）機(jī)制對(duì)現(xiàn)有解進(jìn)行了局部探索，從而獲取更優(yōu)的問題解[3,8-9]。

Taillard針對(duì)問題結(jié)構(gòu)的不同，設(shè)計(jì)了兩種不同的基于分治（DC）策略的分解方法[10]，Reimann則依據(jù)客戶的地理位置，將問題轉(zhuǎn)換為若干較小的問題進(jìn)行處理[11]。Feng于2015年提出了一種VRP與CARP求解方法的轉(zhuǎn)換方法[12]。2017年，Tang提出了層次分解（HD）策略，并以虛擬任務(wù)的形式簡化問題，設(shè)計(jì)了基于HD的大規(guī)模CARP求解算法（SAHiD），在更大規(guī)模上對(duì)CARP進(jìn)行了求解，并顯示了卓越的性能[13]。Zhang發(fā)現(xiàn)文獻(xiàn)[13]以隨意截?cái)嗪蟮穆窂綖榫垲悓?duì)象過于粗糙，提出了一種基于任務(wù)等級(jí)的路徑切割方法（RCO）[14]并用于文獻(xiàn)[13]的路徑聚類，明顯提高了算法的問題求解效果[14]。

鑒于SAHiD在大規(guī)模CARP上的良好問題處理能力，該研究嘗試將層次分解（HD）策略引入至LSCVRP的求解，以變鄰域搜索（VNS）對(duì)當(dāng)前解進(jìn)行局部搜索，結(jié)合Zhang提出的路徑切割技術(shù)[14]，所設(shè)計(jì)的方法記為HD-VNS，并過對(duì)兩個(gè)測試集、32個(gè)測試樣進(jìn)行計(jì)算。

1 問題描述及模型建立

LSCVRP與普通CVRP場景描述類似：區(qū)域內(nèi)一倉庫配套有車隊(duì)，服務(wù)于一定范圍內(nèi)客戶的所需物資配送。每輛車均由倉庫出發(fā)，沿途對(duì)客戶提供服務(wù)，最后返回倉庫。車輛受最大載重量Q約束。目標(biāo)為尋找最優(yōu)的車輛路徑，滿足所有客戶的配送要求，并使車輛的行駛距離最短（成本最低）。

模型相關(guān)符號(hào)定義：客戶集C={ }c0,c1,c2,…,c n，n為客戶數(shù)，每個(gè)客戶c i(1≤i≤n)均存在一定的服務(wù)需求量di，c0為駐扎了m輛車的中心點(diǎn)，可被認(rèn)為無服務(wù)需求的特殊客戶；位于c0處的m輛車構(gòu)成車隊(duì)集合V(k∈V)，其中每輛車的最大負(fù)載量為Q，最長行駛距離為L；χki,j為二值變量，1表示車輛k(k=1,2,3,…,m)由客戶ci行駛到客戶c j(i≠j)，否則為0；γki為二值變量，1表示客戶ci由車輛k服務(wù)，否則為0；δi,j為客戶ci、cj之間的距離，采用歐氏距離計(jì)算形式。

基于上述符號(hào)定義，LSCVRP的數(shù)學(xué)模型描述如下，

上述模型中，式（1）為問題的目標(biāo)函數(shù)，即所有車輛完成服務(wù)的總行駛距離最?。皇剑?）和（3）分別表示車輛從中心點(diǎn)出發(fā)，完成服務(wù)后返回中心點(diǎn)；式（4）～（6）確保每個(gè)客戶被服務(wù)有且僅有一次；式（7）和（8）確保車輛的最大載重約束條件以及最長行程距離。

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

2.1 算法步驟

為了能夠?qū)Υ笠?guī)模CVRP進(jìn)行有效處理，該研究以SAHiD中的HD為問題聚類方法，采用類似于該算法的框架結(jié)構(gòu)，并使用RCO對(duì)路徑進(jìn)行切割，以變鄰域搜索（VNS）對(duì)解進(jìn)行局部搜索。因?yàn)閱栴}結(jié)構(gòu)不同，如CARP中路徑通常是由需求任務(wù)的邊組成，而CVRP中路徑是由客戶節(jié)點(diǎn)組成，所以需要將SAHiD的任務(wù)轉(zhuǎn)換為CVRP客戶，且客戶間采用歐式距離直接計(jì)算?；贖D分治算法的HD-VNS基本步驟如下。

步驟1設(shè)置最大迭代次數(shù)g、最大無進(jìn)展迭代次數(shù)n；

步驟2生成初始解s；

步驟3初始化參數(shù)，迭代次數(shù)i=0，無進(jìn)展迭代次數(shù)m=0；

步驟4構(gòu)建臨時(shí)變量s′，記錄解s′=s；

步驟5使用文獻(xiàn)[14]的路徑切割方法RCO對(duì)s′的路徑進(jìn)行切割，得到路徑集合R；

步驟6使用文獻(xiàn)[13]的層次分解策略HD對(duì)R分解，獲得一個(gè)包含所有客戶的虛擬客戶C′，分割C′得到滿足車輛載重約束的解s″；

步驟7對(duì)s″實(shí)施VNS鄰域搜索；

步驟8若s″對(duì)應(yīng)總行車距離少于s，則進(jìn)行替換，即s=s″，m=0，否則m=m+1；

步驟9i=i+1；

步驟10當(dāng)i≤g且m≤n時(shí)，轉(zhuǎn)步驟4進(jìn)行后續(xù)迭代過程，否則算法結(jié)束，返回s。

步驟2的初始化解生成過程參照SAHiD，初始解的路徑實(shí)際由單個(gè)客戶構(gòu)成。因此，步驟6中，當(dāng)i=0時(shí)，層次分解策略HD的最底層聚類對(duì)象是單個(gè)客戶，而當(dāng)i＞0時(shí)，HD的最底層聚類對(duì)象是由RCO分割的前一迭代過程得到的路徑集合。

2.2 分解策略

上述算法步驟5和6分別為對(duì)現(xiàn)有解的路徑進(jìn)行RCO切割，繼而對(duì)所得路徑采用HD策略聚類與分解。這里可以將RCO和HD合并，從而形成更完整的分解方法，大致步驟如下。

步驟1確定客戶連接優(yōu)劣的參照值L；

步驟2針對(duì)當(dāng)前解sol′的每條路徑，將客戶連接按照L劃分，分別為差連接集合P和好連接集合G；

步驟3分別從P和G各隨機(jī)地選取一條連接，按照一定概率進(jìn)行截?cái)?，P連接以高概率截?cái)啵鳪以低概率截?cái)?，以保留好的路徑結(jié)構(gòu)；

步驟4步驟3截?cái)嗪蟮穆窂綐?gòu)成集合R，R的每條路徑可視為一個(gè)虛擬任務(wù)；

步驟5隨機(jī)地在[1,β·|R|]產(chǎn)生一整數(shù)K，并以K為聚類數(shù)，對(duì)R的路徑使用K方法進(jìn)行聚類；

步驟6對(duì)步驟5所得每個(gè)類別的路徑采用BIH方法進(jìn)行排列；

步驟7將步驟6每個(gè)類別排列后的路徑視作一個(gè)虛擬客戶，將所有虛擬客戶匯集，重新構(gòu)成虛擬任務(wù)集R；

步驟8若|R|＞1，則轉(zhuǎn)步驟5繼續(xù)分解，否則結(jié)束。

上述步驟中，|R|為R的虛擬客戶數(shù)，β為壓縮系數(shù)，設(shè)置為0.1。HD的具體過程參見文獻(xiàn)[13]，而RCO參見文獻(xiàn)[14]。

2.3 變鄰域搜索

變鄰域搜索（VNS）是一種非常有效的局部搜索，在VRP的各種擴(kuò)展問題中廣泛應(yīng)用。VNS基本思想是首先構(gòu)造局部搜索算子集合，然后按照一定順序選取集合中的算子對(duì)現(xiàn)有解進(jìn)行鄰域搜索。當(dāng)搜索陷入局部最優(yōu)時(shí)，采用擾動(dòng)策略，以跳出局部最優(yōu)陷阱。鑒于文獻(xiàn)[15-16]中鄰域搜索的良好特性，本文參照其進(jìn)行VNS設(shè)計(jì)，主要包括如下部分。

（1）局部搜索算子集合。路徑內(nèi)的局部搜索：單點(diǎn)插入（SI）、交換算子（Swap）以及2-OPT；路徑間的局部搜索SI、2-OPT以及兩條路徑的交叉算子。

（2）擾動(dòng)算子集合。擾動(dòng)算子實(shí)際為局部搜索算子，包括算子SI、雙點(diǎn)插入（DI）以及Swap，每個(gè)算子分單條路徑和兩條路徑，可認(rèn)為有6種擾動(dòng)算子。每次隨機(jī)地選取其一進(jìn)行解結(jié)構(gòu)的重組，以在更大范圍內(nèi)搜索更優(yōu)解。

（3）信息存儲(chǔ)結(jié)構(gòu)。對(duì)當(dāng)前解的相關(guān)信息以及搜索記錄進(jìn)行存儲(chǔ)，可以顯著提高后續(xù)搜索速度。本文的VNS中亦對(duì)搜索信息進(jìn)行存儲(chǔ)，如每條路徑中客戶的最小需求量、最大需求量以及兩個(gè)連續(xù)客戶的最小和最大需求量，如此可以對(duì)SI、DI以及Swap等不滿足容量約束的操作進(jìn)行過濾。如有兩條路徑r1和r2，其中r1上客戶最小需求量為6，r2上所有客戶的總需求量為122，車容量Q為125，則路徑r1的客戶對(duì)于r2而言，所有的SI、DI都無法進(jìn)行，故而可以直接將SI、DI過濾。

3 實(shí)驗(yàn)及分析

本文利用兩個(gè)標(biāo)準(zhǔn)測試集Golden[17]與Li[1]對(duì)HD-VNS進(jìn)行實(shí)驗(yàn)測試，以檢測其問題求解能力，尤其是在大規(guī)模問題上的表現(xiàn)，并將實(shí)驗(yàn)結(jié)果與代表性的優(yōu)秀算法結(jié)果進(jìn)行了對(duì)比。

3.1 實(shí)驗(yàn)參數(shù)

測試集Golden與Li共包含32個(gè)測試樣例，其中Golden的20個(gè)測試樣例客戶數(shù)由240升至483，屬于中等規(guī)模測試集；Li的12個(gè)測試樣例客戶數(shù)由560升至1 200，為大規(guī)模測試集。目前，作為大規(guī)模CVRP測試集，Li已成為算法性能驗(yàn)證的標(biāo)準(zhǔn)數(shù)據(jù)。

本文的算法HD-VNS采用C++編程，運(yùn)行環(huán)境為Intel（R）Xeon（R）E5-2650 v2，主頻為2.6 GHz，RAM大小為64 GB，最大迭代次數(shù)g設(shè)置為3 000，最大無進(jìn)展迭代數(shù)m設(shè)置為120。每個(gè)測試算例獨(dú)立運(yùn)行10次。為更好地說明算法HD-VNS的有效性，本文引用較近的工作進(jìn)行比較，包括算法VNSA[7]、AVNS[3]及FJ-QACVRP[9]。

3.2 實(shí)驗(yàn)結(jié)果與分析

HD-VNS與比較算法VNSA、AVNS在測試集Golden與Li上的最優(yōu)結(jié)果如表1和2所示。對(duì)于表1中Golden測試集，算例G9～G20的L為無窮大，即此12個(gè)算例沒有最大行程距離約束，只有容量Q限制。4個(gè)比較算法的某結(jié)果若最小，則以“*”標(biāo)識(shí)，表中NBS（Number of the Best Solutions）統(tǒng)計(jì)了各算法在相應(yīng)測試集上解的最優(yōu)數(shù)目。

表1 測試集Golden上的實(shí)驗(yàn)結(jié)果

續(xù)表1

由表1可知，基于測試集Golden，F(xiàn)J-QACVRP在18個(gè)算例中取得了最好值，算法HD-VNS、VNSA以及AVNS取得最好值的算例數(shù)分別為5、6和3。因此，在中等規(guī)模測試集Golden上，F(xiàn)J-QACVRP具有明顯優(yōu)于其他算法的問題求解能力。

由表2可知，在測試集Li的12個(gè)測試算例上，算法HD-VNS總共取得了9個(gè)最好值，而FJ-QA‐CVRP、VNSA和AVNS取得最好值的算例數(shù)分別為7、2和1，少于HD-VNS，尤其是VNSA和AVNS僅在極少數(shù)算例上獲得最好值。對(duì)于12個(gè)算例的平均值而言，HD-VNS的最小，為24 027.03，而FJ-QA‐CVRP、VNSA和AVNS的平均值分別為24 037.72、24 037.98和24 055.30。因此，HD-VNS在大規(guī)模CVRP上顯示了良好的性能。由上述實(shí)驗(yàn)結(jié)果及分析可知，隨著問題規(guī)模增大，算法HD-VNS求解能力趨于明顯。

表2 測試集Li上的實(shí)驗(yàn)結(jié)果

4 結(jié)論

CVRP是容量受約束的一種車輛路由問題，在實(shí)際生活中，具有眾多應(yīng)用背景。本文針對(duì)熱點(diǎn)問題——大規(guī)模場景下的CVRP分析，回顧了該問題的相關(guān)求解算法。將Tang提出的用于解決大規(guī)模CARP的層次分解策略引入本文，從而設(shè)計(jì)了基于分治策略的LSCVRP求解算法HD-VNS。通過對(duì)標(biāo)準(zhǔn)測試集的計(jì)算可知，HD-VNS在大規(guī)模測試集上具有良好的問題求解性能。