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

中圖分類號：F252 文獻(xiàn)標(biāo)識碼：A 文章編號：2096-7934（2025）04-0097-16

一、引言

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

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

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

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

二、問題描述與模型構(gòu)建

（一） 問題描述

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

（二） 模型構(gòu)建

針對CVRP問題特征，構(gòu)建模型如下：

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

三、混合變鄰域人工蜂群算法設(shè)計(jì)

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

（一） 人工蜂群算法框架

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

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

（二） 變鄰域搜索算子

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

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

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

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

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

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

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

（三） 混合算法步驟

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

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

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

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

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

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

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

四、算例驗(yàn)證與結(jié)果分析

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

（一） HABC參數(shù)試驗(yàn)與分析

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

表1 HABC參數(shù)及水平分布

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

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

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

表3 nf、D1和D2信噪比在不同參數(shù)下響應(yīng)值

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

（二） HABC變鄰域算子試驗(yàn)與分析

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

①決策子集單獨(dú)應(yīng)用；

②雙決策子集組合應(yīng)用；

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

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

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

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

（三）算例對比試驗(yàn)與分析

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

表5 CVRP Set A算例集結(jié)果比較

由表5可知，對比文獻(xiàn)中算法AGGWOA和H3均能求得13個算例最優(yōu)解，求解成功概率為48.14%，LNS-ACO能求得17個算例最優(yōu)解，求解成功概率為62.96%，本文算法HABC能求得18個算例最優(yōu)解，求解成功概率為66.67%，較AGGWOA和H3提升幅度達(dá)18.53%，求解成功概率優(yōu)勢較為明顯，相較于LNS-ACO提升4.67%，具備一定優(yōu)勢。從算法所求得最優(yōu)解的平均最小偏差統(tǒng)計(jì)來看，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)定性方面表現(xià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%以內(nèi)，在不同規(guī)模算例測試中求解性能穩(wěn)定。由表5結(jié)果及分析可得，HABC在算例最優(yōu)解及求解平均值偏差方面較優(yōu)，其StdDev（0.37%）及%Dev（0.23%）的差值僅為0.14%，在部分算例能獲得最優(yōu)解基礎(chǔ)上可同時保證其求解穩(wěn)定性和準(zhǔn)確性。

表6給出算例集Set P的24個算例計(jì)算結(jié)果，包括文獻(xiàn)［7］［16-17］和本文算法，對比算法中部分對應(yīng)算例未給出求解結(jié)果，表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)解求得個數(shù)分析，除AGGWOA外，H3、LNS-ACO和HABC求解成功概率差別較小。在文獻(xiàn)所列算法求得最優(yōu)解的平均最小偏差統(tǒng)計(jì)方面，針對各文獻(xiàn)所列計(jì)算數(shù)據(jù)分析，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)定性方面算法性能相當(dāng)。

表6 CVRP Set P算例集結(jié)果比較

表7給出文獻(xiàn)［16］［18-19］及本文算法對算例集Set B的23個算例計(jì)算結(jié)果，算法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)計(jì)來看，CVRP-FA（0.24%）、HABC（0.30%）優(yōu)于H3（0.69%）以及MAS-SA-PR（0.36%）。在算法所求得算例平均值方面，MAS-SA-PR算法沒有給出其平均值偏差數(shù)據(jù)，算法H3不能穩(wěn)定求得Set B算例集最優(yōu)解，其平均算例平均值偏差達(dá)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算例集結(jié)果比較

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

五、結(jié)論

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

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

參考文獻(xiàn)：

［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］范厚明，劉鵬程，劉浩，等.多中心聯(lián)合配送模式下集貨需求隨機(jī)的VRPSDP問題［J］.自動化學(xué)報(bào)，2021，47（7）：1646-1660.

［7］黃戈文，蔡延光，戚遠(yuǎn)航，等.自適應(yīng)遺傳灰狼優(yōu)化算法求解帶容量約束的車輛路徑問題［J］.電子學(xué)報(bào)，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］.上海交通大學(xué)學(xué)報(bào)，2022，56（1）：81-88.

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

［11］張景玲， 馮勤炳， 趙燕偉， 等."基于強(qiáng)化學(xué)習(xí)的超啟發(fā)算法求解有容量車輛路徑問題［J］. 計(jì)算機(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