基于改進變鄰域搜索的多隔室車輛路徑優化算法

姚冠新，范雪茹，張冬梅

(1.江蘇大學 管理學院，江蘇 鎮江 212013；2.揚州大學 江蘇現代物流研究基地，江蘇 揚州 225009)

1 問題的提出

隨著人們生活品質的提高，多品種、小批量、定制化的產品需求逐漸增加，越來越多的物流企業和配送中心采用多隔室車輛(Multi-Compartment Vehicles, MCVs)代替單隔室車輛(Single-Compartment Vehicles, SCVs)來實現不同種類(或特性)產品的聯合交付[1]，既降低了配送總成本[1-2]，又滿足了消費者需求。SCVs的整個車廂是一個獨立的空間[3]，僅能運輸一種特性的產品，如冷凍產品；MCVs的車廂被分割成多個相對獨立的空間[3]，能夠裝載并共同運輸不同種類的、不相容的、具有嚴格分裝要求的產品[4-5]，如冷藏和冷凍產品。多隔室車輛路徑優化問題(Multi-Compartment Vehicle Routing Problem, MCVRP)是具有容量限制的車輛路徑優化問題(Capacitated Vehicle Routing Problem, CVRP)的擴展。CVRP即SCVs從配送中心出發，為需求節點配送一種特性產品，當所裝載產品配送完畢后返回配送中心，其中每個節點僅能被訪問一次，最終實現配送距離最短或配送成本最低[6]；MCVRP則是采用MCVs，設計運輸線路以滿足一組節點對多種特性產品的需求[4]，產品需裝載在同一車輛的不同隔室內進行共同運輸[2,7]，從配送中心出發依次抵達需求節點進行配送，配送完畢后返回配送中心，最小化配送距離或配送成本。以1個配送中心和3個需求節點片段為例，在總負載上限和節點總需求相同、車輛類型和產品細分需求不同、任意整車和隔室不超載且分裝要求嚴格的前提下，一輛SCV即可滿足CVRP中節點ai-1、ai、ai+1的配送需求(如圖1a)，但卻需要兩輛MCVs才能滿足MCVRP中節點bj-1、bj、bj+1的配送需求(如圖1b)。由此可見，CVRP和MCVRP存在差異性，且由于條件嚴苛，MCVs的路徑規劃變得更加困難。

實際生產和生活中MCVs的應用逐漸增加。零售商的雜貨分銷中[1,5]，不同產品需儲存在不同溫度環境下運送[1]；廢物和垃圾收集中[8-9]，不同顏色的玻璃、不同種類的垃圾需被嚴格分裝在不同的隔室內進行聯合運輸；橄欖油收集[10]、成品油配送[4]、奶制品收集[11]、燃料分配或補給[11-12]、冷鏈配送[11,13]、動物飼料及牲畜集配[14]均會用到MCVs，其應用廣泛且前景良好。此外，基于MCVs應用背景的MCVRP的理論研究熱度也逐漸提升。近年來，關于MCVRP的相關研究主要集中在以下3方面：①基于不同情境的MCVRP模型創新和擴展，豐富了相關研究理論體系，如基于MCVRP的車輛選擇[5]、多車庫的MCVRP[11]、帶時間窗的MCVRP[13]等；②求解MCVRP的元啟發式算法的創新設計及改進，降低了配送距離(成本)，提供了有效的路徑規劃手段，如混合蟻群算法[2]、改進粒子群算法[3]等；③具有實際約束的MCVRP的案例研究，為生產、生活實踐提供了科學的理論依據，如不同型號的成品油配送、分類垃圾收集等(如表1)。

表1 多隔室車輛路徑優化相關問題及算法設計

續表1

續表1

綜合來看，MCVRP優化研究以及相應的算法創新設計兼具理論價值和實際意義。然而，MCVRP中多種特性產品不能混裝的特質以及相應隔室的增加、隔室容量的限制造成了研究的差異性及困難性，且MCVRP的平均解決方案質量不如CVRP[6]。因此，為優化MCVRP解決方案，本文基于變鄰域搜索算法(Variable Neighborhood Search, VNS)框架，針對MCVRP的特點設計了一種改進變鄰域搜索算法(Improved Variable Neighborhood Search, IVNS)。首先，設計多起點尋優機制，采用掃描法構造歷次迭代的初始解，增加解的多樣性；其次，細分主程序下子程序1和子程序2，子程序1中設計Shaking過程，以實現小范圍解空間的探索，子程序2中設計全局擾動過程，以實現大范圍解空間的探索，并設計一種還原及再分配策略處理不可行解，探尋解空間中的不可行區域；再次，結合使用貪婪算法和多種混合算子來設計Local Search過程，以實現局部搜索和優化，提升求解質量和計算效率；然后，應用最大迭代次數停止準則結束主循環并保留最優解；最后，采用改編算例進行實驗及結果對比分析，驗證了IVNS算法的有效性、優越性及收斂性。

2 問題描述及模型構建

2.1 問題描述

多隔室車輛路徑優化問題(MCVRP)可以描述為一個配送中心服務于多個需求節點，每個需求節點具有不同種類產品需求，任意一類產品需求不可拆分配送，不同種類產品需嚴格分裝、聯合配送交付，且僅接受一次車輛訪問；需采用車型相同的、每個隔室的容量固定不變、具有容量限制的多隔室車輛進行配送，其中每個隔室僅能裝載一種產品，每輛車負責線路中所有需求節點對某種產品的需求已知且不超過對應隔室的負載上限、對某種產品的需求總量不超過對應隔室的負載上限、對所有種類產品的需求總量不超過整車的負載上限；配送中心的庫存最大容量、多隔室車輛的臺數均能夠滿足所覆蓋需求節點的所有種類產品需求；多隔室車輛從配送中心出發，沿規劃路徑配送完畢后，返回配送中心，最終實現總的配送距離最小化。

(1)相關符號G=(N,E)，N={0}∪N′={0,1,2,…,n}。其中：G表示配送系統;N表示物流節點集合;{0}表示配送中心;N′表示需求節點集合;E={(i,j)|i,j∈N}，E表示無向邊集合，i,j表示物流節點，i,j∈N。dij表示物流節點i到j的距離，其中dij=dji，即兩節點往返距離相同。V={1,2,3,…,k}，V表示多隔室車輛集合，k表示多隔室車輛，k∈V。M={1,2,3,…,m}，M表示車輛隔室集合。P={1,2,3,…,p}，P表示產品種類集合，其中m=p，即產品種類數與隔室數量相同。Qp表示某隔室所能夠負載對應種類產品p的最大載重量，Qmax表示多隔室車輛的總的最大載重量。qjp表示需求節點j對產品p的需求量。

2.2 模型構建

MCVRP的數學模型如下：

(1)

s.t.

(2)

(3)

(4)

?k∈V,?p∈P；

(5)

?k∈V,?p∈P,i≠j；

(6)

?j∈N,?k∈V,?p∈P,i≠j。

(7)

其中：式(1)為目標函數，表示最小化多隔室車輛總配送距離；式(2)表示一個需求節點只接受一輛多隔室車的服務且僅能被訪問一次；式(3)表示路徑具有連續性；式(4)表示多隔室車輛配送過程中的任意種類產品需求之和不超過對應的隔室負載上限；式(5)表示任意需求節點的任意種類產品需求量不超過相應隔室的負載上限；式(6)表示多隔室車輛返回配送中心時，某種產品的荷載量等于該多隔室車輛本次配送路線中各需求節點的該種產品的需求量之和；式(7)表示配送車輛在任意節點的某種產品的荷載量滿足在該點需求量的遞推關系。

3 算法設計

VNS算法是MLADENOVIC等[29]和HANSEN等[30]提出的一種優化算法，被廣泛用于解決組合優化問題，其基本思想是在搜索過程中系統地改變鄰域結構集以拓展搜索范圍，通過局部搜索流程以獲得局部最優解，再基于此局部最優解重復上述過程獲得另一個局部最優解，如此不斷迭代最終獲得收斂，達到優化目的[21,31-32]。VNS算法的基本環節包括初始解構造、Shaking過程、Local Search過程及停止準則，具有環節少、參數少、易于操作和改進等優勢。為了在合適的求解時間內獲得MCVRP的高質量解決方案，本文基于VNS算法，針對MCVRP的特點，提出改進變鄰域搜索算法(IVNS)，具體流程如圖2所示。下面將詳細介紹IVNS算法的初始解構造、Shaking過程、全局擾動過程、還原及再分配策略、Local Search過程及停止準則等重要組成部分。

3.1 初始解構造

VNS算法是基于單個解向量展開的尋優過程[31]，即從單點出發進行尋優，遍歷所有鄰域結構后保留最優解，求解的時效性較好，但是解的多樣性較差。鑒于此，設計一種多起點尋優機制[8]，采用經典的掃描法構造每次迭代過程的初始解，基于MCVRP不同種類產品需求以及不同隔室的負載上限進行容量及路徑可行性判定，具體步驟如下：

步驟1坐標系轉換。將配送中心{0}和所有需求節點{1,2,3,…,n}所在的笛卡爾坐標系轉換成以配送中心為極點、以任選1個需求節點和配送中心的連線為極軸的極坐標系，其他需求節點基于極軸轉換為極坐標角度。

步驟2將需求節點分組。最小角度的需求節點作為起始點，按照逆時針方向，將需求節點逐一納入組Group1中，直到該組中所有需求節點的某特性產品的需求總量超過該隔室負載上限，然后以本組最后1個需求節點作為下一組起始點建立新組Group2，繼續掃描剩余需求節點并逐一添加到新組內。

步驟3重復步驟2，直至所有需求節點都被分組為止。此時，任意一組內所有需求節點的任意種類產品的需求總量未超過當前隔室的負載上限，且組內所有需求節點的所有種類產品需求總量未超過多隔室車輛整車負載上限；

步驟4形成初始解。分別將各組內的第1個需求節點、最后1個需求節點與配送中心連接，組內的第i個點與第i+1個點連接(i=1,…,j-1，其中j為當前組內需求節點總數)，每組各形成一條子路徑，所有子路徑共同構成初始解。

以1個配送中心和10個需求節點為例，初始解構造流程如圖3所示。需注意，IVNS算法中可能出現較少點構成的子路徑或較少條子路徑構成的解，甚至出現極端情況，如1個點構成的子路徑或1條子路徑構成的解。若某段程序中需具備2個及以上需求節點構成的子路徑或2條及以上子路徑構成的解才能繼續執行時，通過設計并執行特定程序來重新選擇子路徑或跳出循環，確保算法運行暢通。

3.2 Shaking過程

Shaking過程即系統地改變鄰域結構集以拓展當前解的搜索范圍，避免陷入局部最優解，從而獲得更優解。鑒于此，基于MCVRP的子路徑形式初始解設計子程序1中的Shaking過程，從子路徑轉換的角度構造鄰域結構集合，小范圍擴展當前解搜索空間，具體步驟如下：

步驟1定義鄰域結構集合Nk(k=1,…,kmax)，其中kmax=9，即設計了9個鄰域結構。

步驟2選取鄰域結構。按照預先設定順序，選取鄰域結構集合中的一個鄰域結構Nk。

步驟3選取兩條子路徑。確定當前解s包含的子路徑的數量m，先選取當前解s的一條隨機子路徑Subpathi，其中i=1,2,…,m，若i不等于m，則再選取子路徑Subpathi+1；若i等于m，則再選取子路徑Subpath1。

步驟4獲得兩條(或一條)新子路徑。根據Nk的定義，采用當前定義下的特定算子對所選擇的兩條子路徑進行節點以及節點的不同種類產品需求轉換操作，獲得兩條新子路徑，若因節點變化導致僅剩一條子路徑，則刪除空子路徑以不影響后續算法執行。

步驟5形成新解。通過保留當前解s的大部分特征，改變小部分特征，形成新解s′，加快算法收斂速度[32]。

單一的鄰域結構可能造成當前解的較大波動[21]，而多個鄰域結構可廣泛探索解空間[8]，進而提高算法的求解效率和穩定性[32]。因此，基于插入、交換、2-opt*等經典算子來設計鄰域結構集合，并按照固定順序逐一實現鄰域拓展動作。

首先，基于插入算子設計鄰域結構N1～N4：1-插入、2-插入、3-插入、4-插入，即分別基于1～4個(連續)節點的插入動作。插入算子(如圖4)的基本原理即指定兩條子路徑SubpathK(k1,…,ki-1,ki,ki+1,…,km)和SubpathT(t1,…,tj-1,tj,tj+1,…,tn)，提取SubpathK中ki插入到SubpathT中tj的后置位，形成兩條新的子路徑newSubpathK(k1,…,ki-1,ki+1,…,km)和newSubpathT(t1,…,tj-1,tj,ki,tj+1,…,tn)，然后判斷是否demandQ(newSubpathK)≤vehiclecompartmentcapacityQ且demandQ(newSubpathT)≤vehiclecompartmentcapacityQ(Q=1,2,…,q，q為MCVs隔室的數量)，即判斷每個隔室的負載是否合規，若否，則重新進行選擇；若是，則進一步判斷是否distance(newSubpathK)+distance(newSubpathT)

其次，基于交換算子設計鄰域結構N5～N8：1-交換、2-交換、3-交換、4-交換，即分別基于1～4個(連續)節點的交換動作。交換算子的基本原理即指定兩條子路徑，提取并交換SubpathK中的ki和SubpathT中的tj，形成兩條新的子路徑newSubpathK(k1,…,ki-1,tj,ki+1,…,km)和newSubpathT(t1,…,tj-1,ki,tj+1,…,tn)，之后的判斷、選擇動作也需要結合還原及再分配策略并進行每個隔室的負載判斷和每條子路徑的可行性判斷。此外，引入Cross-Exchange和iCross-Exchange兩種算子，假設交換SubpathK中的(ki-1,ki,ki+1)與SubpathT中的(tj-1,tj,tj+1)，Cross-Exchange算子(如圖5a)即將兩個連續點片段分別在對方子路徑中進行正向放置，形成newSubpathK(k1,…,ki-2,tj-1,tj,tj+1,ki+2,…,km)和newSubpathT(t1,…,ti-2,ki-1,ki,ki+1,ti+2,…,tn)；iCross-Exchange算子(如圖5b)即將兩個連續點片段在對方子路徑中進行反向放置，形成newSubpathK(k1,…,ki-2,tj+1,tj,tj-1,ki+2,…,km)和newSubpathT(t1,…,ti-2,ki+1,ki,ki-1,ti+2,…,tn)。因此，出于對連續點片段的方向性以及解的可行性考慮[21]，設置基準概率P=0.8，隨機生成0-1的隨機數p，當pP時，應用iCross-Exchange算子。

最后，基于2-opt*算子設計鄰域結構N9：2-opt*。2-opt*算子的基本原理即指定兩條子路徑，分別截斷任意連續兩點間線路(ki-1,ki)和(tj,tj+1)，獲得SubpathK1(k1,…,ki-1)、SubpathK2(ki,ki+1,…,km)、SubpathT1(t1,…,tj-1,tj)以及SubpathT2(tj+1,…,tn)4個片段，將兩條子路徑的片段重新連接形成兩種組合情形：情形1是newSubpathK(k1,…,ki-1,tj+1,…,tn)(K1和T2)和newSubpathT(t1,…,tj-1,tj,ki,ki+1,…,km)(K2和T1)(如圖6a)；情形2是SubpathK(k1,…,ki-1,tj,tj-1,…,t1)(K1和T1)和newSubpathT(km,…,ki+1,ki,tj+1,…,tn)(K2和T2)(如圖6b)，之后的判斷、選擇動作也需要結合還原及再分配策略并進行每個隔室的負載判斷和每條子路徑的可行性判斷。此外，可設計一定概率獲得不同組合情形以增加解的多樣性，因此，設置基準概率T=0.5，隨機生成0～1的隨機數t，當tT時，采用情形2。

3.3 全局擾動過程

上述Shaking過程是基于子路徑展開的小范圍解空間的探索，為了進一步擴大解空間的搜索范圍，通過有效的鄰域變換保證多樣化的探索，并最終實現全局的優化[20]，借鑒擾動方法設計思想[8]，基于總路徑形式解設計子程序2中的全局擾動過程，從總路徑轉換的角度構造鄰域結構集合，大范圍擴展當前解搜索空間。具體地，任選總路徑形式當前解的兩點執行置換、轉置、插入動作：置換即將原總路徑Rout(r1,…,ri-1,ri,ri+1,…,rj-1,rj,rj+1,…,rn)中的ri和rj交換，獲得新的總路徑newRout(r1,…,ri-1,rj,ri+1,…,rj-1,ri,rj+1,…,rn)；轉置即將ri和rj節點及之間節點順序顛倒，獲得新的總路徑newRout(r1,…,ri-1,rj,rj-1,…,ri+1,ri,rj+1,…,rn)；插入即將ri插入到rj的后置位，獲得新的總路徑newRout(r1,…,ri-1,ri+1,…,rj-1,rj,ri,rj+1,…,rn)。需要注意的是，全局擾動過程也要結合還原及再分配策略進行之后的判斷和選擇，而且，MCVs每個隔室的負載判斷及每條子路徑的可行性判斷均不可或缺，具體步驟如下：

步驟1輸入當前解w的總路徑形式解x，設置最大循環次數Maxl=9，i=0。

步驟2令i=i+1，結合判斷、選擇動作重復以下步驟，直至i>Maxl。

步驟3從x中任選兩點xi和xj，產生1～3的偽隨機整數m，進行以下操作以形成新排列順序，記為x′。

(1)當m=1時，對xi和xj兩節點執行置換操作(如圖7a)；

(2)當m=2時，對xi和xj兩節點及之間執行轉置操作(如圖7b)；

(3)當m=3時，對xi和xj兩節點執行插入操作(如圖7c)。

步驟4將x′的子路徑形式解記為w′，實現了解空間較大范圍拓展搜索。

3.4 還原及再分配策略

一般算法設計中，相應動作的執行以新解負載合規、配送距離變小為前提[6]，導致部分解被過于嚴苛的約束條件剔除，此時可采用一些特殊的策略和機制保留并處理不可行解以探索解空間中的不可行區域[6,8,21,23]，從而對解空間進行更大范圍的探索，增加解的多樣性的同時，提升獲得更優解的可能性[26]。IVNS算法中，經過Shaking過程和全局擾動過程可能獲得不可行新解，即子路徑中某種產品總需求超過當前隔室的負載上限(隔室超載)或所有產品的總需求超過MCVs整車的負載上限(整車超載)，實際運輸中不可行。因此，設計一種還原策略和再分配策略，保留并處理不可行解，將其還原成總路徑形式解并再度分配成子路徑形式的可行新解。

還原策略的具體步驟如下：

步驟1輸入子路徑形式的不可行當前解r，計算其子路徑的數量o，即為分組數量o。

步驟2對第1組到第o組執行以下操作：去掉節點與節點、節點與配送中心之間的所有路徑，并保存所有分組內的未去掉路徑之前的節點順序，即獲得總路徑形式的解y(如圖8a)。

再分配策略的具體步驟如下：

步驟1基于總路徑形式的當前解y，從第1組的第1個需求節點開始按照原順序進行重新分組，假設分成j組，任意組內的負載判斷均合規，隔室和整車均未超載。

步驟2第1組到第j組重新形成子路徑，形成子路徑形式的可行新解r′(如圖8b)。

此外，由于Shaking過程和全局擾動過程基于的MCVRP解形式不同，還原及再分配策略在子程序1和2中的順序也不同：子程序1中，基于子路徑形式解執行Shaking過程，隨后采用還原策略和再分配策略，最后進行局部搜索和優化(如圖9a)；子程序2中，先執行還原策略獲得總路徑形式解，為全局擾動過程做準備，隨后執行再分配策略，最后進行局部搜索和優化(如圖9b)?？梢?，還原及再分配策略的使用使得不止兩條子路徑上的節點數量、順序、總需求等發生變化。

3.5 Local Search過程

Local Search過程即通過局部搜索流程求得局部最優解，決定著最終的求解質量和計算效率[32]。為了對子程序1和子程序2產生的鄰域解進行局部搜索以獲得優化，借鑒文獻[6,17-18]的思想，設計基于子路徑內和子路徑間搜索優化機制的Local Search過程。

基于經典2-opt算子和貪婪算法設計子路徑內搜索優化機制。2-opt算子(如圖10)即針對當前子路徑SubpathK(k1,…,ki-1,ki,ki+1,…,kj-1,kj,kj+1,…,km)，選擇兩個需求節點ki和kj，將兩需求節點及之間節點順序顛倒，獲得新子路徑newSubpathK(k1,…,ki-1,kj,kj-1,…,ki+1,ki,kj+1,…,km)；貪婪算法即針對當前子路徑，每次只選擇距離當前節點最近的節點作為下一個配送節點，直至遍歷當前子路徑中所有節點。需注意，兩者均是基于子路徑內部節點的動作，每個隔室及整車負載均未變化，僅需要判斷是否distance(newSubpathK)

基于2-opt*、插入、交換等經典算子(基本原理見3.2節)設計子路徑間搜索優化機制。需注意，算例分析及實際應用中，互為近鄰的子路徑更容易產生無效交叉部分，消除部分交叉能夠減少配送距離，而任意選擇兩條子路徑進行優化時，獲得較優解的概率較小，且會大幅增加計算時間。因此，擴展文獻[6,22]的思想，以加快搜索速度、減少計算量為目的，設計一種子路徑近鄰優先選取原則，即先后選取相鄰和相隔子路徑進行局部搜索，相鄰子路徑即Subpathi和Subpathi+1(如圖11a)，相隔子路徑即Subpathi和Subpathi+2(如圖11b)。此外，還采用best改進策略來實現求解質量和運行時間的最佳平衡[33]，即遍歷并計算當前解的所有鄰居解并保留最優解。特別地，子路徑間搜索優化機制伴隨著節點及節點需求轉換，因此，MCVs的每個隔室都要重新進行負載判斷。

據此，設計Local Search過程包含兩個組成部分：①基于2-opt算子、貪婪算法交替使用的子路徑內搜索優化機制;②基于近鄰優先選取原則的、多種混合算子的子路徑間搜索優化機制。其中，子路徑間搜索優化機制包含相鄰子路徑2-opt*、相隔子路徑2-opt*、相鄰子路徑1-插入、相隔子路徑1-插入、相鄰子路徑1-交換、相隔子路徑1-交換6個搜索流程。需注意，IVNS算法部分過程基于相同的經典算子原理，但是都進行了一定程度的結合創新和改進設計，因而具有差異性。

3.6 停止準則

與IVNS算法主程序的多起點尋優機制相對應，采用最大迭代次數停止準則，迭代一定次數后結束循環，在歷次迭代的較優解中保留最優解。其中，子程序1停止準則即遍歷Shaking過程的9種鄰域結構后，結束循環并保留最優解；子程序2停止準則即對全局擾動過程循環9次后，結束循環并保留最優解。

4 算例分析

MCVRP缺乏國際標準算例，本文基于REED等[9]的改編辦法對14個CVRP國際標準算例(http://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances/)進行改編，獲得28個MCVRP算例。具體改編辦法：①坐標：配送中心和需求節點的坐標不變；②車輛：原單隔室車輛容量按照3∶1的比例拆分成兩個隔室容量；③節點需求：當需求節點的位置,x,y∈(0,35)時，其需求量按照3∶1的比例分割成兩種特性產品需求量，其他需求節點的需求量按照2∶1的比例(S2改編方式)或4∶1的比例(S3改編方式)分割成兩種特性產品的需求量。本文采用MATLAB R2016a進行計算，運行環境是Windows10專業版、Intel(R)Core(TM)i5-4210H CPU @ 2.90 GHz處理器、4 G內存、64位操作系統。通過改編算例的實驗以及結果對比，分析并驗證算法的有效性、優越性及收斂性。

4.1 算法的有效性分析

基于vrpnc2-S2算例，在其他程序不變的情況下，僅測試當前動作對結果的影響，每個變換下均運行5次、迭代500次，獲得最好解、最差解、平均解及標準方差，所有表格中加粗數據為對比之下的最優解；此外，由于最好解、最差解、平均解等指標能夠反映算法的尋優能力，極差(最差解—最好解)、標準方差、極差百分比(極差/最好解)等指標能夠反映算法的求解穩定性[34]，故再計算極差和極差百分比來繪制尋優能力和求解穩定性統計分析圖并進行統計學分析。

4.1.1 初始解策略的有效性

分別采用貪婪算法、隨機策略、掃描算法產生初始解。結果顯示，基于掃描法的IVNS的最好解、最差解、平均解均最小，隨機策略次之，貪婪算法最大。相對于貪婪算法和隨機策略，基于掃描算法的IVNS的平均解分別減少了10.902 8和7.482 2，減少百分比分別是1.23%和0.85%?；趻呙杷惴ǖ腎VNS的結果標準方差最小，求解穩定性最好(如表2)。此外，觀察不同構造策略的初始解和最好解的折線圖(其中：G為貪婪算法，R為隨機策略，S為掃描算法；I為初始解，O為最好解)，5次運行中隨機策略的初始解的波動最大，極差達到84.351 4，掃描法的初始解的波動最小，極差僅有22.824 7，說明掃描法能夠更穩定地獲得更優初始解(如圖12)?？梢?，以掃描法構造初始解的IVNS算法更有效。

表2 不同初始解構造策略對結果的影響

4.1.2 Shaking過程算子的有效性

Shaking過程中依次疊加使用插入、交換、2-opt*算子。結果顯示，相比于未采用任何算子，基于插入、交換、2-opt*算子的平均解減少了8.895 4，減少百分比為1.01%，結果質量更好，標準方差減少了0.90，求解穩定性更強。其中插入算子對解質量的提升最大，平均解減少值為6.566 5，為總減少值的73.82%(如表3)。此外，觀察Shaking過程不同算子設計的尋優能力和穩定性相關指標的變化趨勢，最好解、最差解及平均解均逐漸降低，而極差、標準方差和極差百分比變化有波動，但整體呈下降趨勢，說明所設計Shaking過程算子的尋優能力更強、穩定性更高(如圖13a和圖13b)?？梢?，Shaking過程使用插入、交換、2-opt*算子使IVNS算法更有效。

表3 Shaking過程算子對結果的影響

4.1.3 全局擾動過程的有效性

在Shaking過程后增加全局擾動過程。結果顯示，相比于僅有Shaking過程，結合了全局擾動過程的IVNS算法減小了最好解、最差解、平均解，略增加了標準方差。其中，平均解減少了0.525 4，提升了求解質量，跳出了局部最優，標準方差增加了0.36，降低了穩定性(如表4)。此外，觀察全局擾動過程的尋優能力和求解穩定性的相關指標變化趨勢，最好解、最差解、平均解均呈下降趨勢，但是極差、標準方差、極差百分比均呈上升趨勢，說明全局擾動過程的設計使得IVNS算法的尋優能力變強，雖然導致求解穩定性變差，但與全局擾動過程的大范圍解空間探索的設計初衷吻合(如圖13c和圖13d)?？梢?，全局擾動過程的設計和應用使得IVNS算法更有效。

表4 全局擾動過程對結果的影響

4.1.4 Local Search過程優化機制及算子的有效性

Local Search過程中依次疊加使用子路徑內和子路徑間搜索優化機制。結果顯示，子路徑內及子路徑間搜索優化機制均有效降低了最好解、最差解、平均解及標準方差，兩者導致平均解分別減少了250.775 6和47.143 5，減少百分比分別是21.37%和4.02%，標準方差減少了19.41和1.27，提升了求解質量及穩定性(如表5)。此外，觀察不同搜索優化機制的尋優能力及求解穩定性相關指標變化趨勢，最好解、最差解、平均解以及極差、標準方差、極差百分比均呈較大幅度下降趨勢，說明所設計搜索優化機制的尋優能力和求解穩定性均實現較大幅度提升(如圖14a和圖14b)?？梢?，Local Search過程中子路徑內及子路徑間搜索優化機制的設計提升了IVNS算法的有效性。

表5 Local Search過程子路徑內及子路徑間搜索優化機制對結果的影響

進一步地，子路徑間搜索優化機制中依次疊加使用2-opt*、插入、交換算子。結果顯示，2-opt*、插入、交換算子導致平均解分別減少了33.990 8、7.391 8及5.760 9，優化效果2-opt*最大，插入算子次之，交換算子最小(如表6)。此外，觀察子路徑間搜索優化機制中不同算子設計的尋優能力和求解穩定性相關指標變化趨勢，最好解、最差解、平均解均呈下降趨勢，且最好解和最差解的差距始終較小，而極差、極差百分比呈“先上升、后下降”趨勢，但整體上極差、極差百分比和標準方差是下降的，說明所設計的子路徑間搜索優化機制中的算子尋優能力和求解穩定性均加強(如圖14c和圖14d)?？梢?，Local Search過程中子路徑間搜索優化機制2-opt*、插入、交換算子的采用使得IVNS算法更有效。

表6 Local Search過程子路徑間搜索優化機制中算子對結果的影響

4.2 與已有文獻結果對比

4.2.1 配送路徑規劃合理性比較

梳理現有MCVRP研究文獻，REED等[9]和陳久梅等[3]的研究中繪制了vrpnc1-S2和vrpnc1-S3算例的結果網絡結構圖(配送路徑規劃圖)，其中REED、陳久梅以及本文的最好結果如表7所示，相應算例目前最好的，以及本文最好結果的網絡結構如圖15～圖18所示。相比于IPSO結果，IVNS算法所獲得的vrpnc1-S2、vrpnc1-S3算例的最好解分別減少了1.494 2和1.729 2，減少百分比分別為0.27%和0.31%，結果質量有所提升，且IVNS算法所獲得的網絡結構圖減少了無效交叉路徑，降低了配送距離，均優于ACO和IPSO求解結果。

表7 與已有文獻的總配送距離的比較

4.2.2 求解穩定性比較

梳理相關文獻，陳久梅等[3]的研究中展示了多次運行結果的最好解、最差解、平均值、標準方差等具體數據，結果新鮮、全面且優質，故將本文結果與之進行求解穩定性的比較。陳久梅等[3]采用IPSO，運行10次，迭代次數1 000次。對比結果顯示，在有限但不相同的運行、迭代次數內，IVNS算法能夠用更少的運行次數和迭代次數獲得質量和穩定性更高的結果，獲得的最好解、最差解、平均解和標準方差均優于IPSO算法。平均解最大差距是272.944 4，減少百分比最大為17.83%，標準方差最大差距是38.71(如表8)。此外，從兩個算法的不同算例的平均解和標準方差對比中可以看出(其中：AveS為平均解，StaD為標準方差)，IVNS算法的平均解和標準方差始終低于IPSO算法，且IVNS算法的標準方差的波動幅度更小，說明所設計的IVNS算法的求解質量和穩定性更高(如圖19a和圖19b)。

表8 與IPSO算法的求解穩定性比較

4.2.3 求解優越性比較

梳理現有相關文獻，REED[9]、ABDULKADER[2]、KAABACHI[26]、陳久梅[3]等獲得了目前最優解，將IVNS算法的求解結果與之對比分析發現，IVNS算法更新了28個算例中的23個目前最優解，優化值最高達到175.126 3，縮小了其余5個結果與目前最優解的差距，差距百分比僅在0.05%～8.98%之間，已經趨近目前最優解。進一步對比28個最好解的平均值，其中HABC算法的結果平均值為1 038.62，為歷史最優，IVNS算法的結果平均值為980.225 6，相對于前者減少58.394 4，優化百分比為5.62%(如表9)。此外，觀察不同算法的不同算例的歷史最優解對比和IVNS算法相對于歷史最優解的優化程度(其中：O為最優解)，僅有vrpnc1-S2、vrpnc1-S3、vrpnc5-S2、vrpnc6-S3、vrpnc12-S3算例未實現優化，其中vrpnc1-S3和vrpnc6-S3算例的未優化程度較大，為-8.98%和-8.76%，而優化算例中vrpnc13-S2的優化程度最大，為13.68%，且所有算例整體的優化程度為正，即整體上實現了優化效果，說明IVNS算法的求解質量更高(如圖20所示，其中HVANS和HABC算法的vrpnc14-S3算例缺失數據按照HAC算法結果填充)?？梢?，相對于已獲得歷史較優解的IPSO、ACS、HAC、HVANS、HABC等算法，IVNS算法具有優越性。

表9 與歷史最優解的求解質量比較

續表9

4.3 算法收斂性分析

以vrpnc2-S2算例為基準，采用其5次運行的迭代結果來展示所設計IVNS算法的收斂性(如圖21)。結果顯示，隨著迭代次數的增加，求解結果逐漸收斂，并且在求解該較大規模算例的情況下，算法并不會過早或過晚收斂，收斂性較好。

5 結束語

本文通過設計針對MCVRP的IVNS算法并展開算例分析，驗證了IVNS算法的有效性、優越性和收斂性。首先，采用掃描法產生初始解使得結果質量更優；運用插入、交換、2-opt*算子設計Shaking過程，在Shaking過程之后進行全局擾動，設計子路徑內和子路徑間搜索優化機制以實現Local Search過程，以及運用2-opt*、插入、交換算子設計子路徑間搜索優化機制，均提高了IVNS算法的有效性。其次，IVNS算法具有優越性，能夠更合理地規劃網絡結構、更穩定地獲得高質量解，且更新了23個(28個算例)目前最優解、縮小了其余5個結果與目前最優解的差距。最后，IVNS算法的收斂性較好，不會過早、過晚收斂。由于篇幅限制，本文未將所設計IVNS算法用于實際MCVRP案例研究中，未來的研究應針對實際的MCVRP進行深入探討，為實際應用提供科學指導。