基于改進(jìn)變鄰域搜索的多隔室車輛路徑優(yōu)化算法

姚冠新，范雪茹，張冬梅

(1.江蘇大學(xué) 管理學(xué)院，江蘇 鎮(zhèn)江 212013；2.揚(yáng)州大學(xué) 江蘇現(xiàn)代物流研究基地，江蘇 揚(yáng)州 225009)

1 問題的提出

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

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

表1 多隔室車輛路徑優(yōu)化相關(guān)問題及算法設(shè)計(jì)

續(xù)表1

續(xù)表1

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

2 問題描述及模型構(gòu)建

2.1 問題描述

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

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

2.2 模型構(gòu)建

MCVRP的數(shù)學(xué)模型如下：

(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)為目標(biāo)函數(shù)，表示最小化多隔室車輛總配送距離；式(2)表示一個(gè)需求節(jié)點(diǎn)只接受一輛多隔室車的服務(wù)且僅能被訪問一次；式(3)表示路徑具有連續(xù)性；式(4)表示多隔室車輛配送過程中的任意種類產(chǎn)品需求之和不超過對應(yīng)的隔室負(fù)載上限；式(5)表示任意需求節(jié)點(diǎn)的任意種類產(chǎn)品需求量不超過相應(yīng)隔室的負(fù)載上限；式(6)表示多隔室車輛返回配送中心時(shí)，某種產(chǎn)品的荷載量等于該多隔室車輛本次配送路線中各需求節(jié)點(diǎn)的該種產(chǎn)品的需求量之和；式(7)表示配送車輛在任意節(jié)點(diǎn)的某種產(chǎn)品的荷載量滿足在該點(diǎn)需求量的遞推關(guān)系。

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

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

3.1 初始解構(gòu)造

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

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

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

步驟3重復(fù)步驟2，直至所有需求節(jié)點(diǎn)都被分組為止。此時(shí)，任意一組內(nèi)所有需求節(jié)點(diǎn)的任意種類產(chǎn)品的需求總量未超過當(dāng)前隔室的負(fù)載上限，且組內(nèi)所有需求節(jié)點(diǎn)的所有種類產(chǎn)品需求總量未超過多隔室車輛整車負(fù)載上限；

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

以1個(gè)配送中心和10個(gè)需求節(jié)點(diǎn)為例，初始解構(gòu)造流程如圖3所示。需注意，IVNS算法中可能出現(xiàn)較少點(diǎn)構(gòu)成的子路徑或較少條子路徑構(gòu)成的解，甚至出現(xiàn)極端情況，如1個(gè)點(diǎn)構(gòu)成的子路徑或1條子路徑構(gòu)成的解。若某段程序中需具備2個(gè)及以上需求節(jié)點(diǎn)構(gòu)成的子路徑或2條及以上子路徑構(gòu)成的解才能繼續(xù)執(zhí)行時(shí)，通過設(shè)計(jì)并執(zhí)行特定程序來重新選擇子路徑或跳出循環(huán)，確保算法運(yùn)行暢通。

3.2 Shaking過程

Shaking過程即系統(tǒng)地改變鄰域結(jié)構(gòu)集以拓展當(dāng)前解的搜索范圍，避免陷入局部最優(yōu)解，從而獲得更優(yōu)解。鑒于此，基于MCVRP的子路徑形式初始解設(shè)計(jì)子程序1中的Shaking過程，從子路徑轉(zhuǎn)換的角度構(gòu)造鄰域結(jié)構(gòu)集合，小范圍擴(kuò)展當(dāng)前解搜索空間，具體步驟如下：

步驟1定義鄰域結(jié)構(gòu)集合Nk(k=1,…,kmax)，其中kmax=9，即設(shè)計(jì)了9個(gè)鄰域結(jié)構(gòu)。

步驟2選取鄰域結(jié)構(gòu)。按照預(yù)先設(shè)定順序，選取鄰域結(jié)構(gòu)集合中的一個(gè)鄰域結(jié)構(gòu)Nk。

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

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

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

單一的鄰域結(jié)構(gòu)可能造成當(dāng)前解的較大波動(dòng)[21]，而多個(gè)鄰域結(jié)構(gòu)可廣泛探索解空間[8]，進(jìn)而提高算法的求解效率和穩(wěn)定性[32]。因此，基于插入、交換、2-opt*等經(jīng)典算子來設(shè)計(jì)鄰域結(jié)構(gòu)集合，并按照固定順序逐一實(shí)現(xiàn)鄰域拓展動(dòng)作。

首先，基于插入算子設(shè)計(jì)鄰域結(jié)構(gòu)N1～N4：1-插入、2-插入、3-插入、4-插入，即分別基于1～4個(gè)(連續(xù))節(jié)點(diǎn)的插入動(dòng)作。插入算子(如圖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隔室的數(shù)量)，即判斷每個(gè)隔室的負(fù)載是否合規(guī)，若否，則重新進(jìn)行選擇；若是，則進(jìn)一步判斷是否distance(newSubpathK)+distance(newSubpathT)

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

最后，基于2-opt*算子設(shè)計(jì)鄰域結(jié)構(gòu)N9：2-opt*。2-opt*算子的基本原理即指定兩條子路徑，分別截?cái)嗳我膺B續(xù)兩點(diǎn)間線路(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個(gè)片段，將兩條子路徑的片段重新連接形成兩種組合情形：情形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)，之后的判斷、選擇動(dòng)作也需要結(jié)合還原及再分配策略并進(jìn)行每個(gè)隔室的負(fù)載判斷和每條子路徑的可行性判斷。此外，可設(shè)計(jì)一定概率獲得不同組合情形以增加解的多樣性，因此，設(shè)置基準(zhǔn)概率T=0.5，隨機(jī)生成0～1的隨機(jī)數(shù)t，當(dāng)tT時(shí)，采用情形2。

3.3 全局?jǐn)_動(dòng)過程

上述Shaking過程是基于子路徑展開的小范圍解空間的探索，為了進(jìn)一步擴(kuò)大解空間的搜索范圍，通過有效的鄰域變換保證多樣化的探索，并最終實(shí)現(xiàn)全局的優(yōu)化[20]，借鑒擾動(dòng)方法設(shè)計(jì)思想[8]，基于總路徑形式解設(shè)計(jì)子程序2中的全局?jǐn)_動(dòng)過程，從總路徑轉(zhuǎn)換的角度構(gòu)造鄰域結(jié)構(gòu)集合，大范圍擴(kuò)展當(dāng)前解搜索空間。具體地，任選總路徑形式當(dāng)前解的兩點(diǎn)執(zhí)行置換、轉(zhuǎn)置、插入動(dòng)作：置換即將原總路徑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)；轉(zhuǎn)置即將ri和rj節(jié)點(diǎn)及之間節(jié)點(diǎn)順序顛倒，獲得新的總路徑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)。需要注意的是，全局?jǐn)_動(dòng)過程也要結(jié)合還原及再分配策略進(jìn)行之后的判斷和選擇，而且，MCVs每個(gè)隔室的負(fù)載判斷及每條子路徑的可行性判斷均不可或缺，具體步驟如下：

步驟1輸入當(dāng)前解w的總路徑形式解x，設(shè)置最大循環(huán)次數(shù)Maxl=9，i=0。

步驟2令i=i+1，結(jié)合判斷、選擇動(dòng)作重復(fù)以下步驟，直至i>Maxl。

步驟3從x中任選兩點(diǎn)xi和xj，產(chǎn)生1～3的偽隨機(jī)整數(shù)m，進(jìn)行以下操作以形成新排列順序，記為x′。

(1)當(dāng)m=1時(shí)，對xi和xj兩節(jié)點(diǎn)執(zhí)行置換操作(如圖7a)；

(2)當(dāng)m=2時(shí)，對xi和xj兩節(jié)點(diǎn)及之間執(zhí)行轉(zhuǎn)置操作(如圖7b)；

(3)當(dāng)m=3時(shí)，對xi和xj兩節(jié)點(diǎn)執(zhí)行插入操作(如圖7c)。

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

3.4 還原及再分配策略

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

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

步驟1輸入子路徑形式的不可行當(dāng)前解r，計(jì)算其子路徑的數(shù)量o，即為分組數(shù)量o。

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

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

步驟1基于總路徑形式的當(dāng)前解y，從第1組的第1個(gè)需求節(jié)點(diǎn)開始按照原順序進(jìn)行重新分組，假設(shè)分成j組，任意組內(nèi)的負(fù)載判斷均合規(guī)，隔室和整車均未超載。

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

此外，由于Shaking過程和全局?jǐn)_動(dòng)過程基于的MCVRP解形式不同，還原及再分配策略在子程序1和2中的順序也不同：子程序1中，基于子路徑形式解執(zhí)行Shaking過程，隨后采用還原策略和再分配策略，最后進(jìn)行局部搜索和優(yōu)化(如圖9a)；子程序2中，先執(zhí)行還原策略獲得總路徑形式解，為全局?jǐn)_動(dòng)過程做準(zhǔn)備，隨后執(zhí)行再分配策略，最后進(jìn)行局部搜索和優(yōu)化(如圖9b)?？梢?，還原及再分配策略的使用使得不止兩條子路徑上的節(jié)點(diǎn)數(shù)量、順序、總需求等發(fā)生變化。

3.5 Local Search過程

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

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

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

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

3.6 停止準(zhǔn)則

與IVNS算法主程序的多起點(diǎn)尋優(yōu)機(jī)制相對應(yīng)，采用最大迭代次數(shù)停止準(zhǔn)則，迭代一定次數(shù)后結(jié)束循環(huán)，在歷次迭代的較優(yōu)解中保留最優(yōu)解。其中，子程序1停止準(zhǔn)則即遍歷Shaking過程的9種鄰域結(jié)構(gòu)后，結(jié)束循環(huán)并保留最優(yōu)解；子程序2停止準(zhǔn)則即對全局?jǐn)_動(dòng)過程循環(huán)9次后，結(jié)束循環(huán)并保留最優(yōu)解。

4 算例分析

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

4.1 算法的有效性分析

基于vrpnc2-S2算例，在其他程序不變的情況下，僅測試當(dāng)前動(dòng)作對結(jié)果的影響，每個(gè)變換下均運(yùn)行5次、迭代500次，獲得最好解、最差解、平均解及標(biāo)準(zhǔn)方差，所有表格中加粗?jǐn)?shù)據(jù)為對比之下的最優(yōu)解；此外，由于最好解、最差解、平均解等指標(biāo)能夠反映算法的尋優(yōu)能力，極差(最差解—最好解)、標(biāo)準(zhǔn)方差、極差百分比(極差/最好解)等指標(biāo)能夠反映算法的求解穩(wěn)定性[34]，故再計(jì)算極差和極差百分比來繪制尋優(yōu)能力和求解穩(wěn)定性統(tǒng)計(jì)分析圖并進(jìn)行統(tǒng)計(jì)學(xué)分析。

4.1.1 初始解策略的有效性

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

表2 不同初始解構(gòu)造策略對結(jié)果的影響

4.1.2 Shaking過程算子的有效性

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

表3 Shaking過程算子對結(jié)果的影響

4.1.3 全局?jǐn)_動(dòng)過程的有效性

在Shaking過程后增加全局?jǐn)_動(dòng)過程。結(jié)果顯示，相比于僅有Shaking過程，結(jié)合了全局?jǐn)_動(dòng)過程的IVNS算法減小了最好解、最差解、平均解，略增加了標(biāo)準(zhǔn)方差。其中，平均解減少了0.525 4，提升了求解質(zhì)量，跳出了局部最優(yōu)，標(biāo)準(zhǔn)方差增加了0.36，降低了穩(wěn)定性(如表4)。此外，觀察全局?jǐn)_動(dòng)過程的尋優(yōu)能力和求解穩(wěn)定性的相關(guān)指標(biāo)變化趨勢，最好解、最差解、平均解均呈下降趨勢，但是極差、標(biāo)準(zhǔn)方差、極差百分比均呈上升趨勢，說明全局?jǐn)_動(dòng)過程的設(shè)計(jì)使得IVNS算法的尋優(yōu)能力變強(qiáng)，雖然導(dǎo)致求解穩(wěn)定性變差，但與全局?jǐn)_動(dòng)過程的大范圍解空間探索的設(shè)計(jì)初衷吻合(如圖13c和圖13d)。可見，全局?jǐn)_動(dòng)過程的設(shè)計(jì)和應(yīng)用使得IVNS算法更有效。

表4 全局?jǐn)_動(dòng)過程對結(jié)果的影響

4.1.4 Local Search過程優(yōu)化機(jī)制及算子的有效性

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

表5 Local Search過程子路徑內(nèi)及子路徑間搜索優(yōu)化機(jī)制對結(jié)果的影響

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

表6 Local Search過程子路徑間搜索優(yōu)化機(jī)制中算子對結(jié)果的影響

4.2 與已有文獻(xiàn)結(jié)果對比

4.2.1 配送路徑規(guī)劃合理性比較

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

表7 與已有文獻(xiàn)的總配送距離的比較

4.2.2 求解穩(wěn)定性比較

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

表8 與IPSO算法的求解穩(wěn)定性比較

4.2.3 求解優(yōu)越性比較

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

表9 與歷史最優(yōu)解的求解質(zhì)量比較

續(xù)表9

4.3 算法收斂性分析

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

5 結(jié)束語

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