夏小云,莊鶴林,楊火根,向 毅,陳澤豐

(1.嘉興學院 信息科學與工程學院，浙江 嘉興 314001；2.江西理工大學 理學院，江西 贛州 341000；3.華南理工大學 軟件學院，廣東 廣州 510006；4.中山大學 人工智能學院，廣東 珠海 519082)

0 引言

帶容量約束的車輛路徑問題是車輛路徑問題的一種變體，屬于NP-hard問題。該問題在交通運輸、物流分發(fā)等實際應用場景中廣泛存在，對其進行有效求解，將帶來巨大的經濟價值。

目前，已有許多學者對車輛路徑問題及其變體進行了大量研究，提出了一系列求解該問題的精確算法、傳統(tǒng)啟發(fā)式算法和元啟發(fā)式算法。精確算法中效果最好的是AUGERAT等[1]提出的分支定界法，該算法的思想是不斷地為每個節(jié)點選擇最好下限的孩子節(jié)點直至得到最終路徑，在可接受時間內最多只能解決100個客戶節(jié)點的問題。啟發(fā)式算法是目前求解該問題的主要方法[2]。傳統(tǒng)啟發(fā)式算法中用于求解該問題的算法有CLARKE等[3]提出的Savings算法、KATOH等[4]提出的生成樹法等，其主要思想為從最初的空解開始，迭代地添加解成分到解中，直到完全構建解，其對搜索空間進行了相對有限的探索，能在有限時間內產生良好的解。元啟發(fā)式算法是啟發(fā)式算法的改進，通常不借助于某種問題的特有條件，能夠在解空間中智能地搜索，產生的解的質量通常優(yōu)于傳統(tǒng)啟發(fā)式算法[5-7]。BLANTON等[8]將遺傳算法應用于求解車輛路徑問題、BULLNHEIMER等[9]提出使用蟻群算法求解車輛路徑問題、SALMEN等[10]研究使用粒子群算法求解車輛路徑問題，均在小規(guī)模數(shù)據(jù)集上取得了較好的結果。國內，蘇欣欣等[11]提出使用禁忌搜索算法求解帶時間窗和多配送人員的車輛路徑問題，在小規(guī)模算例中證實了算法的準確性，在標準規(guī)模算例中證實了算法的高效性；任騰等[12]提出使用改進蟻群算法求解考慮客戶滿意度的低碳冷鏈車輛路徑問題，在不同規(guī)模試驗場景下取得了良好的路徑優(yōu)化效果。最近，TEOH等[13]提出了一種基于局部搜索的改進差分演化算法，通過使用局部搜索輔助探索新的解空間，但僅在小規(guī)模測試集上得到了高質量的解；SBAI等[14]提出一種混合遺傳變鄰域搜索算法，將變鄰域搜索算法與遺傳算法結合，加速了遺傳算法的收斂能力，在數(shù)據(jù)集上搜索到了大量與已知最優(yōu)解質量相當?shù)慕猓陬A處理和變鄰域搜索上需要消耗較多時間；ALTABEEB等[15]提出一種改進螢火蟲算法，加入了兩種改進局部搜索策略，提高了算法的收斂速度，實驗表明該算法具有較高的性能，但其收斂至高質量解的能力稍有不足。

雖然部分啟發(fā)式算法已經能較好地解決數(shù)百客戶數(shù)的車輛路徑問題，能在實驗數(shù)據(jù)集上找到部分與已知最優(yōu)解質量相當?shù)慕?，但從結果上看，解的總體質量還有一定提升空間，且在實際場景下，問題規(guī)模往往更大，對算法的實時性要求更高。為此，本文提出使用基于大鄰域搜索的人工蜂群算法來求解該問題。

自適應大鄰域搜索[16]是大鄰域搜索的拓展，該方法具有易拓展、探索能力強等優(yōu)勢，在鄰域搜索時具有很強的適應能力，適合帶容量約束的車輛路徑問題(Capacitated Vehicle Routing Problem,CVRP)的鄰域搜索。雖然自適應大鄰域搜索已具備優(yōu)秀的搜索性能，但基于個體的特性使其搜索結果具有較大的方差，本文將其與人工蜂群算法結合，利用人工蜂群算法的群體特性彌補該不足。

人工蜂群算法是一種模擬蜜蜂行為的優(yōu)化方法[17-18]，在旅行商問題(Traveling Salesman Problem, TSP)[19]、函數(shù)優(yōu)化[20]、流水線調度[21]等優(yōu)化問題中獲得了廣泛的應用。其作為一種基于鄰域搜索的啟發(fā)式算法，與自適應大鄰域搜索有較高的契合度，且有參數(shù)相對較少、易于實現(xiàn)、探索能力強、融入反饋思想等優(yōu)點，適合CVRP的優(yōu)化。

本文針對問題特點建立適合啟發(fā)式算法求解的問題模型，充分結合自適應大鄰域搜索的搜索深度優(yōu)勢和人工蜂群算法的搜索廣度優(yōu)勢，提出能進行有效的CVRP高質量解搜索的基于大鄰域搜索的人工蜂群算法。

1 CVRP模型

CVRP的普通模型用于精確算法時較為合適，但不利于啟發(fā)式算法對其求解，也掩蓋了CVRP屬于組合優(yōu)化問題的本質特征[22]。為此，針對本文所述算法對CVRP模型進行重新描述。

CVRP定義在全連接圖G=(V,A)上。其中，節(jié)點集V={vi|i∈I={0,1,…,n}}包含倉庫v0和n個客戶節(jié)點，邊集A={(vi,vj)|i,j∈I,i≠j}連接這些節(jié)點。問題中節(jié)點間距離C={ci1,i2|i1,i2∈I}、客戶需求D={di|i∈I,d0=0}、車輛數(shù)為m以及車輛最大載重為B。其中ci1,i2表示vi1和vi2間的距離、di表示節(jié)點vi需求的貨物重量。

為了更加清晰地描述問題模型，給出以下符號：①V′={v1,v2,…,vn}表示客戶節(jié)點集；②li為由車輛i配送的客戶節(jié)點數(shù)；③vij為車輛i經過的第j+1個節(jié)點。CVRP的目標為尋找一個車輛路線集R={ri={vi0,vi1,…,vili,vili+1}|i∈M={0,1,…,m-1}}，使R中的m條路線距離和(代價)最小，該路線集滿足下列條件：①車輛路線均以倉庫為起點和終點；②每輛車載重均不超過最大載重；③每個客戶節(jié)點有且僅有一輛車服務一次。該問題的數(shù)學模型如下：

(1)

s.t.

vi0=vili+1=v0,?i∈M;

(2)

(3)

(4)

(5)

其中，r′i為第i條路線的客戶順序集，式(1)為目標函數(shù)，表示m輛車的行車路程取最小；式(2)約束每輛車的起點和終點均為倉庫；式(3)約束每輛車的載重不超過最大載重；式(4)和式(5)約束每個客戶節(jié)點均被服務且僅被服務1次。

滿足式(2)、式(4)和式(5)的解稱為預備解，滿足式(3)的預備解稱為可行解。一個解是否為預備解，從其本身的信息即可判斷，但是否為可行解，還需結合客戶需求D和車輛最大載重B經過計算才能得出。本文所述的解空間為可行解集。

2 基于自適應大鄰域搜索的人工蜂群算法設計

2.1 自適應大鄰域搜索(ALNS)

自適應大鄰域搜索(Adaptive Large Neighborhood Search, ALNS)通過一組移除和插入算子動態(tài)競爭鄰域搜索的機會，擁有良好的適應能力[16]。其核心為高效的鄰域搜索算子。移除和插入算子可針對問題特性靈活設計，可擴展度高。

ALNS搜索鄰域的主要過程為通過適應策略選擇移除算子和插入算子，對待操作解應用移除算子移除部分節(jié)點得到待插入解和移除的節(jié)點集，再將移除的節(jié)點集中的節(jié)點通過插入算子插入到待插入解中得到一個新解，稱其為原解的鄰域解，最后通過更新策略更新待操作解。

2.2 關于CVRP的ALNS

ALNS的算子可靈活設計，針對第2章所述數(shù)學模型，設計了5個移除算子和2個插入算子。移除算子每次移除一個解中nr個客戶節(jié)點，nr由式(6)計算得出:

(6)

移除算子分別如下：

(1)隨機移除算子 從解中隨機移除nr個客戶節(jié)點。

(2)最大貢獻移除算子 優(yōu)先移除路程貢獻大的客戶節(jié)點。某個客戶節(jié)點vij的路程貢獻gij由式(7)計算得出。采用輪盤賭的方式從解中選擇nr個客戶節(jié)點移除，某個客戶節(jié)點vij的權重qij=gij,

gij=cij-1,ij+cij,ij+1。

(7)

(3)需求相近移除算子 優(yōu)先移除與選中節(jié)點所處路線不同但需求相近的節(jié)點。若nr=1,退化為隨機移除算子；若nr>1,由賭盤選擇一條路線，在其中隨機選擇一個節(jié)點作為標準節(jié)點vb,車輛i的路線的權重fi由式(8)計算得出：

(8)

式中ε為一個極小的正數(shù)，避免賭盤總權重為0的特殊情況。

從剩余路線的客戶節(jié)點中賭盤選擇nr-1個節(jié)點移除，某個客戶節(jié)點vij的權重qij由式(9)計算得出：

(9)

(4)單路線移除算子 集中移除一條路線上的客戶節(jié)點。從經過客戶節(jié)點數(shù)l≥nr的路線中隨機選擇一條路線，隨機移除該路線上nr個節(jié)點。若無符合條件的路線，則退化為隨機移除算子。

(5)相關度移除算子 優(yōu)先移除相關度低的客戶節(jié)點。解中每個客戶節(jié)點對應一個相關度eij,初值均為1。若某次移除和插入得到的新解不被更新策略接收，則由此次移除算子移除的客戶節(jié)點對應的相關度增加eΔ。從解中賭盤選擇nr個客戶節(jié)點移除，某個客戶節(jié)點vij的權重qij由式(10)計算得出:

qij=1/eij。

(10)

隨機移除算子與單路線移除算子為純隨機算子，而其他移除算子均需要遍歷一遍解中各個節(jié)點的屬性，故移除算子(1)～(5)的時間復雜度分別為：O(1)、O(n)、O(n)、O(1)和O(n)。

各移除算子的示意圖如圖1所示。

隨機移除算子隨機性強，跳出局部能力較強，但容易移除在正確位置上的節(jié)點，產生無效操作；最大貢獻移除算子會優(yōu)先考慮路程貢獻最大的節(jié)點，而這些節(jié)點往往正是需要優(yōu)化的節(jié)點，缺點是容易陷入局部最優(yōu)；需求相近移除算子在解陷入一輛或多輛車輛接近滿載的局部最優(yōu)時能起到跳出局部的作用，但在車輛剩余容量充裕時無顯著作用；單路線移除算子會集中移除一條路線上的節(jié)點，策略簡單且具有良好的局部收斂能力；相關度移除算子會根據(jù)以往插入移除的經驗，降低那些曾被移除但未被更新策略接收的節(jié)點的移除優(yōu)先級，跳出局部能力最強，但對于頻繁改進的低質量解，沒有過多以往移除插入的經驗可以參考，效果與隨機移除算子相當，且選擇策略更復雜，時間代價比隨機移除算子高。

插入算子分別如下：

(1)貪婪順序插入算子 每個節(jié)點由貪婪法得到插入位置，即選擇使本次插入增加路程最小的位置插入。將待插入節(jié)點隨機亂序后依次以貪婪法插入。

依據(jù)待插入節(jié)點需要試點的位置數(shù)和，貪婪順序插入算子與兩點遍歷插入算子的時間復雜度均為O(n2),是算法的主要耗時部分之一。因移除算子的時間復雜度均小于O(n2),故ALNS每次選擇一個移除算子和一個插入算子執(zhí)行的時間復雜度仍為O(n2)。

各插入算子的示意圖如圖2所示。

由于CVRP本身的復雜性，貪婪順序插入算子存在易陷入局部最優(yōu)的缺點，而兩點遍歷插入在很大程度上彌補了這種局限。

每個算子在每個解中對應一個權重w,權重的更新流程如圖3所示。

算子權重初值wi相同。若某次移除和插入得到的新解被更新策略接收，則此次選用的算子在該解中的權重重置回初值，否則下降一個固定值wd。算子的權重存在一個大于0的下界wl,當該解的所有移除或插入算子的權重均下降到該下界，則重置該解的所有移除或插入算子的權重。

2.3 人工蜂群智能算法(ABC)

人工蜂群算法(Artificial Bee Colony algorithm, ABC)是一個由蜂群行為啟發(fā)的算法，由KARABOGA[17]為優(yōu)化函數(shù)問題而提出。

蜜蜂是一種群居昆蟲，雖然單個昆蟲的行為極其簡單，但是由單個簡單的個體所組成的群體卻表現(xiàn)出極其復雜的行為。真實的蜜蜂種群能夠在各種環(huán)境下以極高的效率從食物源中采集花蜜,同時，它們能適應環(huán)境的改變。

人工蜂群算法的主要組成部分包括：食物源、雇傭蜂、跟隨蜂和偵查蜂。兩種最基本的行為模式為蜜源招募蜜蜂和蜜蜂放棄蜜源。食物源對應問題的一個解，食物源的好壞對應于算法中的適應值。每只雇傭蜂對應一個食物源，依概率與跟隨蜂分享蜜源信息，食物源越好，招募到跟隨蜂的概率越大。跟隨蜂在食物源附近搜索新的潛在食物源，偵查蜂搜索新的食物源。

該算法的每次迭代主要分以下3個階段。

(1)雇傭蜂階段 一個雇傭蜂與一個食物源對應。雇傭蜂在鄰域搜索并依據(jù)貪婪法更新。

(2)跟隨蜂階段 跟隨蜂依概率選擇雇傭蜂帶回的食物源信息對應的食物源，搜索其鄰域并依據(jù)貪婪法更新。

(3)偵查蜂階段 當某個解迭代nl次沒有改進，認為該食物源不好，此時對應雇傭蜂轉化為偵查蜂，放棄該食物源，同時隨機生成一個新的食物源。其中nl為解的適應值未改進的最大存在輪數(shù)。

2.4 適應值函數(shù)

根據(jù)目標函數(shù)式(1)，解的適應值的主要參考依據(jù)為該解對應的行車路程，行車路程越小，適應值越高。據(jù)此，給出適應值函數(shù)：

(11)

式中：min(A,B)表示取A和B中的較小者；s為該解的路程；smin為上一輪迭代后路程最短的解的路程；smax為上一輪迭代后路程最長的解的路程；ks為一個大于0的系數(shù)。指定1為適應值下限。比起直接使用路程的倒數(shù)作為適應值，該適應值函數(shù)以上一輪迭代的結果為基準，通過歸一化區(qū)分各解的層級，能層次分明地反映出各解的質量。

2.5 ABC優(yōu)化

針對CVRP和ALNS的特性，對ABC加入了3處優(yōu)化機制:

(3)更新策略寬松機制 對于較優(yōu)解，僅允許用適應值更高的鄰域解更新；而對于非較優(yōu)解，允許適應值適當降低，超過原解適應值的kt倍即可，但只有適應值比該解更新歷史中的最優(yōu)解更高才會將其存在輪數(shù)清0。其中kt為接近1的系數(shù)。該機制既保障了算法的收斂能力，也增強了其跳出局部的能力。

2.6 基于ALNS的ABC優(yōu)化(ABC-ALNS)求解CVRP

雖然ABC本身為一個優(yōu)秀的通用群體智能算法，但CVRP的復雜性使得普通的鄰域搜索策略難以達到滿意的效果。將ALNS引入ABC作為其鄰域搜索策略能夠充分發(fā)揮兩者的優(yōu)勢，達到高效求解CVRP的效果。

算法初始蜜源由亂序的包含所有客戶節(jié)點序列以貪婪法插入得到。由于節(jié)點插入順序不同，即使插入方式相同，也能得到質量尚可的不盡相同的解。接著經過雇傭蜂、跟隨蜂、偵查蜂3個階段不斷迭代，最終得到高質量的可行解。

鄰域搜索策略：以解的算子分數(shù)為權重在其移除算子集中賭盤選擇一個移除算子，應用該移除算子得到待插入解和移除的節(jié)點集，再應用插入算子得到鄰域解，通過引入寬松機制的更新策略更新該解。流程如圖4所示。

基于ALNS的ABC優(yōu)化算法如下：

算法1ABC-ALNS。

輸入：節(jié)點間距離C，客戶需求D，車輛最大承重B；

輸出：搜索到的路程最短的可行解。

1：由貪婪插入法隨機生成初始食物源xi(i=1,2,…,nf);

2：while 搜索到目標適應值的食物源或達到運行時間上限

3： for each雇傭蜂

4： ALNS(xi); /*對xi進行自適應鄰域搜索*/

5： end for

6： for each跟隨蜂

7：xj=Roulette_Selection(x); /*按賭盤算法選擇一個食物源*/

8： ALNS(xj); /*對選中食物源進行鄰域搜索*/

9： end for

10： for eachxi

11： Iteration_Add(xi); /*迭代輪數(shù)計數(shù)加1*/

12： if Iteration_Count(xi)>nl

13：xi=New_Solution(); /*拋棄該食物源并生成新食物源替代*/

14： end if

15： end for

16：end while

其中：ALNS(xi)表示對xi進行自適應鄰域搜索；Roulette_Selection(x)表示按賭盤算法選擇一個食物源；Iteration_Add(xi)表示將xi的迭代輪數(shù)計數(shù)加1；Iteration_Count(xi)表示xi的迭代輪數(shù)計數(shù)；xi=New_Solution()表示生成新食物源替代xi。雇傭蜂固定搜索自己對應的蜜源的鄰域，以保證每輪迭代中每個蜜源有至少一次鄰域搜索；跟隨蜂則是讓適應值更好的蜜源有更多的鄰域搜索機會，以形成正反饋；偵查蜂及時拋棄改進可能性低的食物源，以探索更多的解空間。

3 實驗分析

3.1 算法參數(shù)設置

算法涉及大量參數(shù)，表1給出了一種性能較優(yōu)的默認參數(shù)設置方案。

表1 默認參數(shù)設置

此外，跟隨蜂數(shù)設置為2×nf。實驗發(fā)現(xiàn)，除了krmin與krmax,其他參數(shù)在合理范圍內浮動不會顯著影響算法的性能，而krmin與krmax增大雖會顯著增強單輪迭代的搜索能力，但也會極大地增加耗時。對算法的3個關鍵全局參數(shù)nf、krmin和krmax進行規(guī)模為L25(53)的正交試驗，選取AUGERAT 等[1]instances.Set A中規(guī)模中等的算例A-n55-k9，測驗在較短的單位時間內不同參數(shù)設置下算法求得解的平均路程。算例以“數(shù)據(jù)來源字母縮寫-n節(jié)點數(shù)-k車輛數(shù)”格式命名。參數(shù)水平分布如表2所示，正交表和結果統(tǒng)計如表3所示。

表2 參數(shù)水平分布

表3 正交表和結果統(tǒng)計

根據(jù)表3，計算得到各參數(shù)的響應值，如表4所示。

表4 各參數(shù)的響應值

由表4分析得，對于算例A-n55-k9，這3個參數(shù)均在水平3左右比較合適，對于其他規(guī)模的算例，最佳參數(shù)設置會有所浮動。

3.2 算法性能分析

在實驗時，將路程不超過已知最優(yōu)解路程1.05倍的解視為可接受解。

為探究2.5節(jié)所述優(yōu)化機制的具體改進效果，進行算法搜索可接受解的獨立對比實驗，數(shù)據(jù)集采用AUGERAT 等[1]instances.Set A，結果如表5所示。

表5 3種優(yōu)化機制的改進效果對比

未具體給出的參數(shù)均設置為默認值；kf=0即使算子區(qū)別應用機制失效、kd=0即使仔細偵查蜂機制失效、kt=1即使更新策略寬松機制失效。

表5表明ABC-ALNS能快速搜索到數(shù)據(jù)集AUGERAT等[1]instances.Set A中大部分算例的可接受解，且3種優(yōu)化機制均有不同程度的改進效果，其中任意優(yōu)化機制失效均會使搜索到可接受解的所需平均迭代輪數(shù)增加，但仔細偵查蜂機制在迭代輪數(shù)大于等于nl時才生效。同時，搜索到可接受解平均所需迭代輪數(shù)與節(jié)點數(shù)并非完全正相關，車輛載荷過高、節(jié)點分布復雜等特殊情況使得一些算例需要更多的迭代以收斂。

表5以可接受解為標準反映了ABC-ALNS的基本性能，為進一步分析ABC-ALNS搜索到的解的質量，分別選用AUGERAT等[1]、CHRISTOFIDES等[23]給出的數(shù)據(jù)集進行實驗，將結果與SBAI等[14]提出的混合遺傳變鄰域搜索算法(HGA-VNS)、ALTABEEB等[15]提出的求解CVRP的改進螢火蟲算法(CVRP-FA)以及ALNS比較，如表6～表9所示。

表6 CVRP-FA、HGA-VNS、ALNS和ABC-ALNS在AUGERAT等[1] instances.Set A上的求解質量對比

表7 CVRP-FA、HGA-VNS、ALNS和ABC-ALNS在Augerat 等[1] instances.Set B上的求解質量對比

表8 CVRP-FA、HGA-VNS、ALNS和ABC-ALNS在AUGERAT等[1]instances.Set P上的求解質量對比

表9 CVRP-FA、HGA-VNS、ALNS和ABC-ALNS在Christofides等[23]instances上的求解質量對比

表中：BK表示已知最優(yōu)解的路程、Best表示各個算法搜索到的最優(yōu)解路程，Avg.表示各個算法搜索到的解的平均路程，/表示未給出數(shù)據(jù)。為直觀比較3種算法的總體性能，統(tǒng)計3種算法搜索到與已知最優(yōu)解質量相當?shù)乃憷齻€數(shù)、在各算例搜索到的最優(yōu)解的平均路程和在各算例搜索到的解的平均路程，結果如表10所示。

表10 CVRP-FA、HGA-VNS、ALNS和ABC-ALNS的性能比較

表中：BN表示搜索到與已知最優(yōu)解質量相當?shù)乃憷齻€數(shù)；BA表示在各算例搜索到的最優(yōu)解的平均路程;AA表示在各算例搜索到的解的平均路程。統(tǒng)計過程忽略CVRP-FA或HGA-VNS未給出數(shù)據(jù)的算例。由表10可知，HGA-VNS和ABC-ALNS的整體性能均高于CVRP-FA；ABC-ALNS求解高質量解的能力略高于HGA-VNS，但搜索到解的總體質量略低于HGA-VNS。ALNS依靠大鄰域搜索的優(yōu)勢在小規(guī)模算例上有較好的表現(xiàn)，實驗中發(fā)現(xiàn)其在小規(guī)模算例上能以更小的平均計算消耗搜索到近優(yōu)解。但CVRP的解空間大小隨客戶規(guī)模階乘級增長，在中等及以上客戶規(guī)模下，ALNS的“大鄰域”相比CVRP的解空間十分有限，探索能力不足的缺點使其需要更高的平均計算消耗以搜索到近優(yōu)解。故對于小規(guī)模算例，ALNS能滿足性能需求且計算消耗較小，而對于中等及以上規(guī)模的算例，還需要結合ABC的探索優(yōu)勢以及相關策略改進。

在處理以上數(shù)據(jù)集時，默認將每段路程四舍五入取整，而TEOH等[13]進行了更精準的浮點計算，且在AUGERAT等[1]、CHRISTOFIDES等[23]提出的數(shù)據(jù)集搜索到了數(shù)個精準計算情況下比已知最優(yōu)解更優(yōu)的解。在其基礎上，ABC-ALNS搜索到了5個新最優(yōu)精準解，如表11所示。

表11 ABC-ALNS搜索到的新最優(yōu)精準解

表中：OABR表示原已知最優(yōu)精準解的路程，NABR表示新已知最優(yōu)精準解的路程；算例A-n34-k5的原最優(yōu)精準解由TEOH等[13]給出，而ABC-ALNS找到了更優(yōu)的精準解。

4 結束語

本文將ALNS引入ABC以求解CVRP。由于CVRP的解空間的復雜性，要求算法同時具備良好的探索大解空間的能力和局部搜索能力。本文基于ABC和ALNS，采用算子區(qū)別應用機制、仔細偵查蜂機制、更新策略寬松機制優(yōu)化算法，充分發(fā)揮了ALNS的局部搜索能力和ABC的探索能力。實驗結果表明，3種優(yōu)化機制均能有效提升算法性能、算法整體具有優(yōu)秀的高質量解搜索能力和良好的解空間探索能力。

對于CVRP，不同的優(yōu)秀的算法雖然都能找到一些與已知最優(yōu)解質量相當?shù)慕?，但還未有一個算法各個算例中都能有卓越的表現(xiàn)，且搜索的解的平均質量也參差不齊。ALNS具有良好的擴展能力，本文所述的算子僅開發(fā)了其部分性能。此外，ALNS各算子涉及大量的參數(shù)，暫未有系統(tǒng)的參數(shù)調優(yōu)方法，本文僅憑經驗設置了大部分參數(shù)的默認值。因此，擴展優(yōu)化ALNS與參數(shù)調優(yōu)可能是更高效求解CVRP的關鍵。

車輛路徑問題及其變體的算法間具有一定程度的通用性，除了算法本身的性能，建立與實際場景更加貼近的模型[24-25]也是該領域的關鍵研究方向。