基于混合人工蜂群算法的容量約束車輛路徑優(yōu)化

關鍵詞：組合優(yōu)化；車輛路徑問題；人工蜂群算法；變鄰域搜索算子；容量約束；路徑優(yōu)化

中圖分類號：F252 文獻標識碼：A 文章編號：2096-7934（2025）04-0097-16

一、引言

進入21世紀以來，我國互聯網行業(yè)蓬勃發(fā)展，移動互聯網行業(yè)實現了彎道超車，基于互聯網及移動互聯網的電商新業(yè)態(tài)和新模式極大促進了消費者的個性化需求。但電商物流長期存在的“最后一公里”、配送效率等問題尚未完全解決，面對當前業(yè)務及市場需求的快速擴張，其末端配送環(huán)節(jié)將面臨更大的壓力。

電商物流末端配送的核心問題是容量約束車輛路徑問題（Capacitated Vehicle Routing Problem， CVRP），CVRP是運籌學領域的經典問題，是NP-hard組合優(yōu)化問題，在當前電商物流配送實際作業(yè)環(huán)節(jié)中具有極為廣泛地應用背景［1］。CVRP研究多以服務所有客戶的總車輛行駛路徑最小為目標，在滿足最大車載量約束條件下，達到降低物流配送成本、減少配送時間的目的。對CVRP的研究能為作業(yè)環(huán)境日趨復雜的電商物流提供通用性強的基礎優(yōu)化框架，改進其路徑優(yōu)化方案，縮短配送距離，提升配送時效，滿足末端配送客戶的綜合服務需求，更穩(wěn)定和高效的CVRP求解方案也能為資源配置、業(yè)務調度等組合優(yōu)化問題提供解決思路和參考依據。

對CVRP的研究受到了諸多學者的廣泛關注，其重點主要集中于求解算法的研究及改進，主要包括精確算法、啟發(fā)式算法以及超啟發(fā)式算法等。在精確算法方面，劉（Liu）和羅（Luo）等［2］應用分支定界算法求解了具有分組約束的兩級容量車輛路徑問題，設計了五簇有效不等式強化0-1整數規(guī)劃模型，通過與CPLEX的對比驗證了模型及算法的有效性。動態(tài)規(guī)劃、分支定價算法等精確求解方法也多有應用［3-4］，但當客戶點規(guī)模較大時，精確算法求解效力會顯著下降，解的總體質量還有一定改進空間，尤其在面對多異質性的實際運用場景時，問題往往更加復雜，對算法求解的要求更高，多數學者采用啟發(fā)式及元啟發(fā)式算法進行優(yōu)化［5-6］。黃戈文和蔡延光等［7］設計自適應遺傳灰狼算法求解CVRP，算法中應用了灰狼空間整數編碼和先路由后分組的解方案生成策略，應用移動平均自適應灰狼更新策略和灰狼基因遺傳策略提高算法全局收斂能力。文森特（Vincent）等［8］設計了生物共棲搜索算法對CVRP展開優(yōu)化，基于算法特征設計了兩種解方案表征方式展開對比驗證，增加了兩種新的互動和競爭補償策略來強化生物共棲搜索。陳禹伊和陳璐［9］在電商物流的“最后一公里”配送中提出一種逆向優(yōu)化方法，通過學習專家的過往路徑決策將專家經驗應用于路徑規(guī)劃模型求解及決策算法，設計了乘性權重更新算法實現專家經驗的學習。超啟發(fā)式算法借助超啟發(fā)式框架、高層啟發(fā)式策略以及底層啟發(fā)式算子展開優(yōu)化求解，部分學者將其引入組合優(yōu)化問題求解［10］。為了更高效地求解有容量車輛路徑問題，減少陷入局部最優(yōu)的情況，張景玲和馮勤炳等［11］設計了具備高層啟發(fā)式策略、強化學習選擇機制、模擬退火接受準則等環(huán)節(jié)的超啟發(fā)式算法并展開相關求解驗證。冷（Leng）等［12］提出了一種基于位置路由問題的新低碳冷鏈優(yōu)化問題，設計了相應多目標超啟發(fā)式算法展開求解，算法中包含基于隨機、選擇函數以及適應度的三種選擇策略。

針對容量約束車輛路徑問題，文章設計了混合人工蜂群算法（Hybrid Artificial Bee Colony Algorithm， HABC）進行求解。人工蜂群算法（Artificial Bee Colony Algorithm，ABC）是一種基于蜜蜂群智能行為的優(yōu)化算法，其主要通過三種蜂群間的分工協(xié)作來實現種群整體迭代尋優(yōu)，具有分布性、正負反饋等自組織特點，其算法參數相對較少。作為一種基于鄰域搜索的群智能啟發(fā)式算法，ABC與變鄰域搜索（Variable Neighborhood Search， VNS）有較高的契合度，在將變鄰域搜索嵌入后能有效增強混合算法整體尋優(yōu)能力。文中混合人工蜂群算法設計了基于節(jié)點、字符串及路徑操作的六種變鄰域算子參與尋優(yōu)，在分類基礎上通過對三類算子決策子集進行組合算例試驗，確定最終變鄰域算子子集組合設置。此外混合算法還應用鄰域半徑縮減策略控制搜索范圍，通過禁忌表設置來展開種群個體擾動，接受劣解，基于田口優(yōu)化法對HABC關鍵全局參數展開了數值分析，確定其默認參數設置。變鄰域搜索結合人工蜂群算法中引領蜂、跟隨蜂、偵察蜂種群迭代機制使得HABC具備較強的全局及局部搜索能力，能有效跳出局部最優(yōu)，滿足CVRP求解需要。

二、問題描述與模型構建

（一） 問題描述

本文研究的是容量約束車輛路徑問題（CVRP），CVRP中車輛具備容量約束，裝載量不能超過車輛最大容量，車輛從配送中心出發(fā)后按照優(yōu)化路徑對客戶點展開服務，服務完成后返回配送中心，CVRP的優(yōu)化目標是通過所設計混合算法迭代尋求整體的車輛服務次序方案，在滿足所有客戶需求基礎上使得方案總配送成本達到最低。對于CVRP，本文有如下假設：①配送網絡中所有節(jié)點信息已知，完全相互連通，配送線路起點和終點為配送中心；②客戶點需求不超過車輛最大容量，且應由配送車輛一次性滿足；③配送車輛均為同一型號；④配送中心容量充足，可派出多臺車輛滿足所有客戶點需求。

（二） 模型構建

針對CVRP問題特征，構建模型如下：

式（1）為目標函數，表示解方案最終路徑總成本最小化；式（2）為配送車輛容量約束，算法在路徑優(yōu)化環(huán)節(jié)應滿足車輛子路徑中總裝載量不大于配送車輛最大容量限制；式（3）為車輛進出平衡約束，保證每個客戶有且僅有一輛車對其進行服務；式（4）保證當車輛被啟用時僅有一條路徑且其起始點均為配送中心；式（5）保證了每個客戶必被某輛車服務；式（6）和式（7）將決策變量相關聯，保證客戶被服務時一定有路徑與其連接；式（8）為標準支路消除約束；式（9）為決策變量屬性。

三、混合變鄰域人工蜂群算法設計

CVRP所尋求的優(yōu)化目標是高效的車輛路徑方案，鑒于CVRP的NP-hard屬性，多數研究通過嘗試對路徑方案中子路徑節(jié)點序列展開變換進行尋優(yōu)。變鄰域搜索算法主要通過一系列系統(tǒng)性的鄰域結構變化展開迭代求解，以當前解為中心依據變鄰域算子進行持續(xù)性的范圍搜索，通過漸進的接受改進解來逐步提高解方案質量，具備深度搜索優(yōu)勢［12］。在組合優(yōu)化問題分析中，變鄰域搜索適宜與局部搜索算法相結合，通過局部搜索循環(huán)往復式的邏輯結構變換，展開簡潔高效的尋優(yōu)。人工蜂群算法［13］是仿生蜂群覓食原理所設計的群智能優(yōu)化算法，ABC算法控制參數少，具有分布性、正負反饋等自組織特點，主要通過蜜蜂個體分工協(xié)作來實現種群迭代尋優(yōu)，將變鄰域搜索嵌入人工蜂群算法中能擴大蜂群搜索范圍，發(fā)揮其廣度搜索優(yōu)勢，提高搜索精度，有效增強HABC算法整體尋優(yōu)能力。因此，考慮到CVRP方案路徑節(jié)點序列變換操作的需求，本文結合變鄰域搜索的深度搜索優(yōu)勢和人工蜂群算法的廣度搜索優(yōu)勢，設計了基于變鄰域搜索的混合人工蜂群算法，契合CVRP路徑尋優(yōu)。

（一） 人工蜂群算法框架

ABC由三種不同功能屬性蜜蜂（引領蜂、跟隨蜂和偵察蜂）構成蜂群，其搜索主要由蜜源尋覓、蜜源評價、蜜蜂行為構成。ABC尋優(yōu)時首先由引領蜂發(fā)現蜜源，初始蜜源信息代表CVRP初始解方案，依據改進節(jié)約算法原理隨機插入生成蜜源，設置隨機插入成本以增強初始蜜源多樣性，所有解方案均滿足模型容量約束，引領蜂將先對蜜源鄰域尋優(yōu)，新蜜源質量較優(yōu)時原蜜源將會被替代。隨后跟隨蜂選擇蜜源展開局部搜索，設置輪盤賭選擇機制對引領蜂中質量較高蜜源進行鄰域搜索，CVRP解方案總路徑越小，被選中概率越大。

在經過引領蜂和跟隨蜂的搜索后，算法會依次判斷所有CVRP解方案是否滿足相應禁忌設置，禁忌檢驗中包含擾動禁忌值D1和擾動禁忌值D2判斷，D1和D2決定當前CVRP解方案的擾動操作強度。當CVRP某解方案經多輪迭代其路徑成本仍無改進時，該蜜源所屬引領蜂將轉變?yōu)閭刹旆鋽_動搜索新蜜源，新蜜源方案將增加種群多樣性，實現廣度搜索，通過原蜜源的深入搜索和新蜜源的持續(xù)更新，ABC能在較大范圍內實現CVRP解方案尋優(yōu)。所設計的HABC將VNS嵌入到ABC蜂群局部搜索環(huán)節(jié)，對蜜源方案部分節(jié)點及字符串展開系統(tǒng)性鄰域結構變化，擴大ABC蜜蜂搜索范圍，實現蜂群對高質量蜜源的持續(xù)性搜索，通過接受劣解及偵察蜂的擾動搜索來跳出局部最優(yōu)，強化ABC尋優(yōu)能力，使整體蜜源質量持續(xù)提升，HABC流程如圖1所示。

（二） 變鄰域搜索算子

HABC中主要設置了6種變鄰域搜索算子，對CVRP方案路徑節(jié)點序列展開系統(tǒng)性變換，強化引領蜂和跟隨蜂蜜源尋覓階段的局部搜索能力?；诠?jié)點操作設置了點重置算子（Insert）和點交換算子（Exchange），基于方案子路徑變換設置了2-Opt算子（2-Opt）和路徑交換算子（Route-Exchange），基于字符串操作設置了字符串重置算子（Or-Opt）和字符串交換算子（String-Exchange），通過對節(jié)點、字符串及路徑的系統(tǒng)性結構變換，多變鄰域搜索算子能實現連續(xù)漸進的尋優(yōu)，提高HABC搜索效率。對算子具體分析如下。

（1）點重置算子（Insert）。Insert先選中方案中隨機兩點i、j（i為客戶節(jié)點，j為任意節(jié)點），隨后將i從原路徑中刪除，i可重置于j節(jié)點任一側，與其直接相鄰。

（2）點交換算子（Exchange）。Exchange先選中方案中隨機客戶節(jié)點i、j，隨后交換其節(jié)點位置即可。

（3）2-Opt算子（2-Opt）。2-Opt包括方案同子路徑和兩子路徑操作2種，先選中客戶節(jié)點i、j，當i、j在同一子路徑內且不相鄰時，直接逆序i、j間路徑使其組合形成新路徑。當i、j分屬不同子路徑時，將兩點所在子路徑分離，對i、j所在子路徑執(zhí)行順序交叉和逆序交叉，通過2-Opt操作重新組合子路徑生成新方案。

（4）路徑交換算子（Route-Exchange）。Route-Exchange選中方案中分屬兩子路徑的客戶節(jié)點i、j，通過交換兩子路徑節(jié)點i和j后的剩余路徑生成新方案。

（5）字符串重置算子（Or-Opt）。Or-Opt操作時先選中方案中隨機兩點i、j（i為客戶節(jié)點，j為任意節(jié)點），將i所在子路徑中i點及其后相鄰接的部分連續(xù)字符串分離，該字符串可重置于j點兩側，可實現部分字符串在方案中的重置。

（6）字符串交換算子（String-Exchange）。String-Exchange先選中方案不同子路徑隨機客戶節(jié)點i、j，與Or-Opt類似，分別將與i、j相鄰接的部分連續(xù)字符串分離，隨后交換兩個字符串即可。

（三） 混合算法步驟

如圖2所示，HABC采用整數編碼方式構造蜜源解方案，優(yōu)化算法如下。

具體算法執(zhí)行步驟如下。

步驟1：算法初始化。初始化算法參數，引領蜂和跟隨蜂數目nf相同，設置蜜蜂種群個體數為2×nf；混合算法設置固定迭代次數作為終止條件，失敗路徑懲罰費用與總成本直接相關。

步驟2：引領蜂蜜源尋覓。依據改進節(jié)約算法原理設計插入法生成引領蜂初始種群，通過隨機設置保證其多樣性，確定初始蜜源，隨后通過多變鄰域算子對初始蜜源展開局部搜索。

步驟3：跟隨蜂蜜源尋優(yōu)。跟隨蜂依據輪盤賭設置選擇質量較高的引領蜂蜜源展開多算子變鄰域搜索，選擇概率與CVRP解方案總成本線性相關，跟隨蜂擇優(yōu)迭代能增加局部最優(yōu)解的搜索強度。

步驟4：偵察蜂檢驗與擾動。每次迭代后蜜源均需進行禁忌檢驗，判斷該解方案是否有所改進，禁忌檢驗中設置了擾動禁忌值D1和D2。當某蜜源迭代次數達到擾動禁忌值D1仍無改進時，該蜜源將由偵察蜂進行擾動，通過大鄰域搜索算子執(zhí)行操作，在保留大部分當前解方案路徑序列基礎上跳出當前局部最優(yōu)，當蜜源經過第一次擾動后迭代次數達到擾動禁忌值D2仍無改進時，調用引領蜂重新生成新蜜源，擴大CVRP解方案搜索空間。

步驟5：HABC檢驗。HABC設置迭代次數作為算法終止條件，迭代超過1500次時，HABC停止運行，輸出當前最優(yōu)解。

四、算例驗證與結果分析

選取經典CVRP算例集對HABC進行檢驗，算例集包括Set A（27個）、Set B（23個）、Set P（24個）三部分。Set A算例集客戶點橫縱坐標隨機分布于［1，110］網格，其需求量服從均勻分布U（1，30）；Set B算例集客戶點橫縱坐標同樣分布于［1，100］網格，具有集聚的均勻離散分布特征，需求量分布特征與Set A算例集相同；Set P中算例集成Set A、Set B和Set E算例信息，對相關客戶點需求量及車輛容量進行了修改，圖3給出了異質分布特征下客戶位置及其需求量信息示意（圖中圓圈代表客戶點，大小與需求量相關，方塊為配送中心）。Set A、Set B和Set P中算例包含了隨機及集聚分布特征的客戶分布，算例集節(jié)點規(guī)模從18到101不等，通過其對HABC性能進行檢驗能取得較好的效果，每個算例重復計算10次。文中算法采用MATLAB R2014a進行編程操作，操作系統(tǒng)為Window10，電腦內存為16.00GB，CPU為酷睿i7-10875H，主頻為2.3GHz。

（一） HABC參數試驗與分析

田口優(yōu)化是一種主要基于魯棒性來確定算法重要參數適宜值的模擬分析方法，基于田口優(yōu)化法，本文首先應用Minitab對HABC的關鍵參數展開數值分析，通過對HABC不同參數設置下的CVRP算例求解分析，確定其較優(yōu)的默認參數設置［14］。ABC算法控制參數少，試驗中發(fā)現引領蜂數目nf、擾動禁忌值D1和D2對HABC性能影響較大，文中選取上述3 個關鍵全局參數展開規(guī)模為L9（33）的正交試驗。選取的HABC參數及水平分布如表1所示，L9（33）的設置能均衡正交指標、參數以及其水平，可識別出有效參數及其水平值，其正交表如表2所示。

表1 HABC參數及水平分布

測試時在算例集Set A、Set P和Set B中各選取一個中等規(guī)模測試算例（A-n55-k9/P-n50-k7/B-n57-k9），檢驗在相對短時間內不同參數水平設置下HABC算例求解最優(yōu)值及其平均值與已知算例的最優(yōu)解偏差。BK為已知算例最優(yōu)解，Best、Average為算法所得最優(yōu)值、平均值，%Dev表示最優(yōu)值與BK偏差［%Dev=（Best－BK）/BK］，StdDev表示算例試驗求解平均值與BK偏差［StdDev=（Average－BK）/BK］，每次試驗算例均重復計算10次，計算結果如表2所示。

表2 L9（33）正交表及算例結果統(tǒng)計

通過Minitab對上述參數試驗結果展開分析，將表2中3個算例不同參數設置下試驗所得求解平均值轉為田口優(yōu)化下信噪比（S/N）進行評估。引領蜂數目nf、擾動禁忌值D1和D2信噪比在不同參數下響應值如表3所示，各參數及水平值對均值及信噪比的主效應如圖3所示。表3中Delta是參數不同水平下信噪比響應值最大值與最小值間的差異，鑒于模型目標函數為總成本最小化，Minitab算例結果信噪比響應值計算時所采用的為望小準則。

表3 nf、D1和D2信噪比在不同參數下響應值

從表3排序結果中可知，對各算例計算結果影響最大的參數是引領蜂數目nf，其次是擾動禁忌值D1和D2。此外，對于最小化目標函數而言，信噪比響應值取得最大時的參數水平值是最優(yōu)取值［15］。因此由圖4可知，引領蜂數目nf、擾動禁忌值D1和D2的水平值設置為2（25）、1（30）、2（30）較為合適，該水平值設置下圖4均值主效應圖中數據均值的均值指標效果較優(yōu)。上述參數2/1/2取值即表2中試驗4設置，由表2算例求解最優(yōu)值及平均值結果可知，在該參數設置下A-n55-k9/P-n50-k7/B-n57-k9計算能取得較優(yōu)的解，在尋優(yōu)及均值求解方面有一定優(yōu)勢，算法后續(xù)計算時參數水平值將采取以上設置。

（二） HABC變鄰域算子試驗與分析

考慮到CVRP解方案優(yōu)化對路徑節(jié)點序列變換操作的需求，HABC將變鄰域搜索算子嵌入ABC局部搜索環(huán)節(jié)，通過節(jié)點序列系統(tǒng)性變換來強化ABC整體搜索能力。依據變鄰域搜索算子操作對象區(qū)別將其分為節(jié)點策略DS1、字符串策略DS2以及子路徑變換策略DS3三類決策子集，DS1包含點重置算子（Insert）和點交換算子（Exchange），DS2包含字符串重置算子（Or-Opt）和字符串交換算子（String-Exchange），DS3包含2-Opt算子（2-Opt）和路徑交換算子（Route-Exchange）。為了驗證HABC中變鄰域搜索算子的有效性，本文對算子不同決策子集進行組合展開算例試驗，決策子集組合分為三類：

①決策子集單獨應用；

②雙決策子集組合應用；

③三決策子集組合應用。測試時選取前面的三個中等規(guī)模測試算例（A-n55-k9/P-n50-k7/B-n57-k9），對其%Dev及StdDev進行對比分析，檢驗在相對短時間內決策子集組合有效性，算例重復計算10次，決策子集組合下HABC蜂群種群個體每次迭代均調用6次變鄰域搜索算子，計算結果如表4所示。

表4 變鄰域算子決策子集組合及算例結果統(tǒng)計

由表4中%Dev及StdDev結果可知，在算法應用三類不同決策子集組合分別展開測試算例求解時，在求解平均值方面：①三子集組合應用，算法尋優(yōu)能力及求解穩(wěn)定性優(yōu)于雙子集及單子集組合應用；②雙子集組合應用算法求解性能優(yōu)于單子集。應用單子集測試時，節(jié)點策略DS1求解性能較字符串策略DS2以及子路徑變換策略DS3更好，尤其DS3單獨應用時效果不佳。在算例尋優(yōu)方面：①三子集組合應用HABC尋優(yōu)能力最強，算例求解相對簡單時，雙子集組合應用也能求得滿意解；②應用雙子集隨機組合測試時，DS1/DS3組合應用下算法性能最佳，其求解更穩(wěn)定，總體而言，雙子集DS1/DS2、DS1/DS3和DS2/DS3之間求解性能差別相對較小，在各算例求解時整體效果優(yōu)于單子集算法尋優(yōu)。

圖5是各子集組合下算例均值偏差趨勢，基于表4結果給出了HABC在應用不同子集組合下求解平均值偏差。對于HABC而言：①針對CVRP解方案序列的節(jié)點鄰域搜索設置能提高局部搜索效率，尤其當問題規(guī)模不大時，能快速尋得最優(yōu)；②子路徑鄰域搜索單獨應用時效果較差，其由于缺乏節(jié)點操作尋優(yōu)較難實現，但當子路徑結合節(jié)點、字符串鄰域展開局部搜索時，算法性能能得到有效提升；③當問題規(guī)模變大后，字符串和子路徑鄰域算子的設置能起到擾動效果，避免節(jié)點鄰域算子操作陷入局部最優(yōu)。HABC中節(jié)點、字符串以及子路徑三類鄰域變換操作結合能有效提升算法整體尋優(yōu)能力，增強其求解穩(wěn)定性，后續(xù)測試HABC將采取三決策子集組合的設置。

（三）算例對比試驗與分析

通過對HABC參數及變鄰域算子組合的試驗分析，確定了所構建模型的正確性以及相關算法參數的設置，在此基礎上應用HABC對不同客戶分布特征下的經典CVRP算例集進行求解分析。表5給出算例集Set A的27個算例計算結果，其中包括文獻［7］［16-17］和本文算法的計算結果，BK為已知算例最優(yōu)解，Best、Worst、Average分別表示算法最優(yōu)值、最差值和平均值，%Dev表示與BK偏差（%Dev=（Best－BK）/BK），StdDev表示算例求解平均值與BK偏差［StdDev=（Average－BK）/BK］。

表5 CVRP Set A算例集結果比較

由表5可知，對比文獻中算法AGGWOA和H3均能求得13個算例最優(yōu)解，求解成功概率為48.14%，LNS-ACO能求得17個算例最優(yōu)解，求解成功概率為62.96%，本文算法HABC能求得18個算例最優(yōu)解，求解成功概率為66.67%，較AGGWOA和H3提升幅度達18.53%，求解成功概率優(yōu)勢較為明顯，相較于LNS-ACO提升4.67%，具備一定優(yōu)勢。從算法所求得最優(yōu)解的平均最小偏差統(tǒng)計來看，HABC（0.23%）優(yōu)于H3（1.51%）、LNS-ACO（0.60%）以及AGGWOA（0.30%），除H3算法最優(yōu)解求解偏差相對略大外，HABC、AGGWOA和LNS-ACO算法在求解算例最優(yōu)解方面性能差異較小。從算法所求得算例平均值方面分析，算法AGGWOA和H3均沒有算例能穩(wěn)定求得其最優(yōu)解，其平均算例平均值偏差分別為AGGWOA（1.57%）、H3（13.95%），其中H3算法在求解穩(wěn)定性方面表現較差，算例求解平均值偏離最優(yōu)值較多；LNS-ACO能穩(wěn)定求得9個算例最優(yōu)解，平均算例平均值偏差為1.05%，HABC能穩(wěn)定求得9個算例最優(yōu)解，平均算例平均值偏差為0.37%，HABC在求解穩(wěn)定性方面優(yōu)勢明顯，除A-n80-k10算例外，算例求解平均值與算力最優(yōu)解偏差均在1.5%以內，在不同規(guī)模算例測試中求解性能穩(wěn)定。由表5結果及分析可得，HABC在算例最優(yōu)解及求解平均值偏差方面較優(yōu)，其StdDev（0.37%）及%Dev（0.23%）的差值僅為0.14%，在部分算例能獲得最優(yōu)解基礎上可同時保證其求解穩(wěn)定性和準確性。

表6給出算例集Set P的24個算例計算結果，包括文獻［7］［16-17］和本文算法，對比算法中部分對應算例未給出求解結果，表6中符號含義同表5。由表6可得，AGGWOA在給出的18個算例中能求得11個最優(yōu)解，H3能求得22個算例中17個最優(yōu)解，LNS-ACO能求得23個算例中15個最優(yōu)解，HABC能求得24個算例中16個最優(yōu)解，從最優(yōu)解求得個數分析，除AGGWOA外，H3、LNS-ACO和HABC求解成功概率差別較小。在文獻所列算法求得最優(yōu)解的平均最小偏差統(tǒng)計方面，針對各文獻所列計算數據分析，AGGWOA（0.24%）最優(yōu)，LNS-ACO（0.41%）以及HABC（0.46%）次之，H3（0.98%）一般，各算法在所給出的Set P算例最優(yōu)求解時性能良好。在算法所求得算例平均值方面，算法AGGWOA和 H3求解性能一般，其平均算例平均值偏差分別為1.41%、5.13%，H3算法雖然能求得較多算例最優(yōu)解，但無論算例規(guī)模大小，均未能穩(wěn)定求得最優(yōu)解；LNS-ACO和HABC均能穩(wěn)定求得11個算例最優(yōu)解，平均算例平均值偏差分別為0.84%、0.89%，求解穩(wěn)定性方面算法性能相當。

表6 CVRP Set P算例集結果比較

表7給出文獻［16］［18-19］及本文算法對算例集Set B的23個算例計算結果，算法H3、CVRP-FA、MAS-SA-PR和HABC分別能求得15個、11個、13個和13個算例最優(yōu)解，除所求得的Set B算例集最優(yōu)解外，HABC有8個算例求解Best值優(yōu)于H3算法，有6個算例求解Best值優(yōu)于CVRP-FA算法，有7個算例求解Best值優(yōu)于MAS-SA-PR算法。從算法所求得最優(yōu)解的平均最小偏差統(tǒng)計來看，CVRP-FA（0.24%）、HABC（0.30%）優(yōu)于H3（0.69%）以及MAS-SA-PR（0.36%）。在算法所求得算例平均值方面，MAS-SA-PR算法沒有給出其平均值偏差數據，算法H3不能穩(wěn)定求得Set B算例集最優(yōu)解，其平均算例平均值偏差達16%，有7個算例求解平均值偏離最優(yōu)值20%以上，求解穩(wěn)定性較差；CVRP-FA能穩(wěn)定求得2個算例最優(yōu)解，平均算例平均值偏差為1.04%，HABC能穩(wěn)定求得5個算例最優(yōu)解，平均算例平均值偏差為0.53%。

表7 CVRP Set B算例集結果比較

圖6中（a）、（b）、（c）分別為A-n55-k9、B-n57-k7、P-n50-k7算例客戶點分布示意，子圖（d）、（e）、（f）則給出了其對應CVRP算例最優(yōu)路徑方案及成本。由圖可見所設計混合算法迭代的最終解能兼顧客戶點地理分布特征、服務序列及需求量大小等要求，子路徑節(jié)點序列銜接合理，能滿足所構建模型對于車輛服務路徑及容量方面的相關約束要求?；谒憷疭et A/B/P的系列求解對比分析，總體而言，本文算法HABC在CVRP問題中小規(guī)模算例求解時具備良好的性能，在最優(yōu)解及求解平均值方面優(yōu)于一系列對比文獻算法，在求解穩(wěn)定性方面表現較優(yōu)，是優(yōu)化容量約束車輛路徑問題的有效方法。

五、結論

對容量約束車輛路徑問題，建立經典車輛路徑問題模型展開分析，結合模型及問題設計了混合人工蜂群算法對其進行求解，依據田口優(yōu)化對混合算法參數設置進行了試驗與分析，基于問題特征設計了包含節(jié)點、字符串及路徑變換的6種變鄰域算子參與算法求解。變鄰域搜索算法結構簡單，易于與其他啟發(fā)式算法嵌套展開迭代，算例集驗證及文獻對比分析表明，本文混合變鄰域人工蜂群算法在最優(yōu)解獲取以及求解穩(wěn)定性方面表現良好，求解精度高，全局搜索能力強。隨著問題規(guī)模的增加，算法效力會逐漸降低，大規(guī)模車輛路徑問題的有效求解仍需要進一步的研究。

基金項目：2020年教育部人文社會科學研究青年基金項目“共享經濟下眾包物流的動態(tài)協(xié)同配送機制研究”（20YJC630070）；2019年遼寧省教育廳科學研究經費項目“O2O新零售環(huán)境下電商同城配送的合單協(xié)同及即時優(yōu)化研究”（L2019050）；2022年遼寧省社會科學規(guī)劃基金一般項目“動態(tài)訂單即時匹配下的電商物流配送優(yōu)化研究”（L22BGL034）

參考文獻：

［1］ALCARAZ J J， CABALLERO L， VALES-ALONSO J."Rich vehicle routing problem with last-mile outsourcing decisions［J］. Transportation research part e： logistics and transportation review， 2019， 129（9）：263-286.

［2］LIU T， LUO Z X， QIN H， et al."A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints［J］. European journal of operational research， 2018，266（2）：487-497.

［3］YU Y， WANG S， WANG J， et al."A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows［J］. Transportation research part b： methodological， 2019， 122（4）：511-527.

［4］ TOLGA B， LUIS G， ANTONIO M S， et al."Balanced vehicle routing： polyhedral analysis and branch-and-cut algorithm［J］. European journal of operational research， 2019， 273（2）：452-463.

［5］ RUIZ E， SOTO-MENDOZA V， BARBOSA A R， et al."Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm［J］. Computers amp; industrial engineering， 2019， 133（7）：207-219.

［6］范厚明，劉鵬程，劉浩，等.多中心聯合配送模式下集貨需求隨機的VRPSDP問題［J］.自動化學報，2021，47（7）：1646-1660.

［7］黃戈文，蔡延光，戚遠航，等.自適應遺傳灰狼優(yōu)化算法求解帶容量約束的車輛路徑問題［J］.電子學報，2019，47（12）：2602-2610.

［8］VINCENT F Y， REDI A A N P， YANG C L， et al."Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem［J］. Applied soft computing， 2017， 52（3）：657-672.

［9］陳禹伊，陳璐.車輛路徑規(guī)劃問題的逆向優(yōu)化方法［J］.上海交通大學學報，2022，56（1）：81-88.

［10］郭寧，錢斌，申秋義，等.超啟發(fā)蟻群優(yōu)化算法求解帶柔性時間窗的綠色兩級多周期車輛路徑問題[J].控制與決策，2025，40（03）：745-754.

［11］張景玲， 馮勤炳， 趙燕偉， 等."基于強化學習的超啟發(fā)算法求解有容量車輛路徑問題［J］. 計算機集成制造系統(tǒng)， 2020， 26（4）：1118-1129.

［12］ LENG L， ZHANG J， ZHANG C， et al."Decomposition-based hyperheuristic approaches for the bi-objective cold chain considering environmental effects［J］. Computers amp; operations research， 2020， 123（11）：118-133.

［13］ SADATI M， ATAY B， AKSEN D."An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems［J］. Computers amp; operations research， 2021，133（9）：231-244.

［14］ ZHOU J J， YAO X F， CHAN F T S， et al."An individual dependent multi-colony artificial bee colony algorithm［J］. Information sciences， 2019， 485（6）：114-140.

［15］ TSAI P W， PAN J S， CHEN S M， et al."Enhanced parallel cat swarm optimization based on the Taguchi method［J］. Expert systems with applications， 2012， 39（7）：6309-6319.

［16］ AL-TABEEB A， MOHSEN A M， GHALLAB A S."An improved hybrid firefly algorithm for capacitated vehicle routing problem［J］. Applied soft computing， 2019， 84（11）：1-9.

［17］ YILDIRIM U， KUVVETLI Y."Solution of capacitated vehicle routing problem with invasive weed and hybrid algorithms ［J］. International journal of industrial engineering computations， 2021， 12（4）：441-456.

［18］ AKPINAR S."Hybrid large neighborhood search algorithm for capacitated vehicle routing problem［J］. Expert systems with applications， 2016， 61（11）：28-38.

［19］ ASMA M A， ABDULQADER M M， ABDULLATIF G."An improved hybrid firefly algorithm for capacitated vehicle routing problem［J］. Applied soft computing， 2019， 84（11）： 10572-10581.

［20］ ARIT T， PETCHARAT R."Hybrid modified ant system with sweep algorithm and path relinking for the capacitated vehicle routing problem［J］. Heliyon， 2021， 9（7）：1-15.

Optimization of Capacitated Vehicle Routing Based on

Hybrid Artificial Bee Colony Algorithm

LI Yang，GU Wen-wen

（School of Economics and Management， Liaoning Petrochemical University， Fushun，Liaoning 113001）

Abstract： Aiming at the capacitated vehicle routing problem， a hybrid integer programming model with the goal of lowest path cost is constructed， and a hybrid artificial bee colony algorithm based on the model and the characteristics of the CVRP problem is proposed to solve the problem."The hybrid algorithm integrates the artificial bee colony algorithm and the variable neighborhood search algorithm， embeds a multi-variable neighborhood operator in the local search link of the artificial bee colony to carry out iteration."And the operator contains targeted transformation operations on path nodes， strings， and sub paths to ensure the diversity of the bee population."In addition， a variable neighborhood perturbation strategy is used to strengthen the algorithms ability to escape from local optima."The comparative analysis of the literature study sets and its algorithm solution shows that the designed hybrid artificial bee colony algorithm has strong global search ability and high solution accuracy， especially in solution stability."HABC can obtain 47 optimal solutions in 74 examples."The average minimum deviation of the optimal solution is 0.34%， and the average deviation of the average CVRP set is 0.57%."The overall performance is better than the algorithm in the comparative literature.

Keywords： combination optimization; vehicle routing problem; artificial bee colony; variable neighborhood search; capacity constraint; path optimization