改進(jìn)NSGA-II算法求解多目標(biāo)物流車輛路徑優(yōu)化問題

包賢哲 宋阿妮

(湖北工業(yè)大學(xué)電氣與電子工程學(xué)院 湖北 武漢 430068)

0 引 言

近年來互聯(lián)網(wǎng)電商平臺興起推動物流行業(yè)高速發(fā)展，快遞分撥中心遍布城市鄉(xiāng)村，但隨著快遞數(shù)量的增加、客戶服務(wù)范圍增大，逐漸出現(xiàn)配送快遞效率不高、耗時太長、車輛配送路徑不合理等問題，造成物流行業(yè)成本激增，客戶服務(wù)質(zhì)量下降，嚴(yán)重影響物流行業(yè)的發(fā)展。因此如何高效有序規(guī)劃快遞車輛行駛路徑成為了物流行業(yè)領(lǐng)域研究的重點(diǎn)。

物流運(yùn)輸車輛路徑規(guī)劃問題本質(zhì)上是一個帶約束的NP難問題，隨著對智能優(yōu)化算法研究的深入，出現(xiàn)了許多解決該問題的方法，如郝群茹等[1]結(jié)合四種鄰域變化規(guī)則改進(jìn)禁忌搜索算法來求解車輛行駛路徑；路徑規(guī)劃問題中改進(jìn)禁忌搜索算法[2-3]的收斂速度較快且局部開發(fā)能力較強(qiáng)。黃戈文等[4]提出自適應(yīng)遺傳灰狼算法解決了帶容量的車輛路徑規(guī)劃問題；Akpinar等[5]結(jié)合大領(lǐng)域搜索和蟻群優(yōu)化算法研究路徑規(guī)劃問題；李鳳坤[6]利用中位數(shù)層次分析法將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)求解；范文兵等[7]結(jié)合爬山算法改進(jìn)遺傳算法，優(yōu)化了其局部搜索能力；也有學(xué)者通過其他方式改進(jìn)遺傳算法[8-9]求解該問題并進(jìn)行了驗證。Akhand等[10]結(jié)合自適應(yīng)掃描策略改進(jìn)粒子群算法來優(yōu)化路徑；齊名軍等[11]提出動態(tài)猴子跳躍機(jī)制改進(jìn)粒子群算法提高算法收斂性并用物流實例驗證了算法的有效性。Lai等[12]采用模擬退火算法以及TSA來降低使用車輛數(shù)和行駛成本；混合模擬退火算法[13-14]在路徑規(guī)劃問題上也有著不錯的效果。Wang等[15]采用哈希函數(shù)加速禁忌狀態(tài)來獲得更好的優(yōu)化方案；方文婷等[16]結(jié)合A*算法和蟻群算法克服算法前期收斂慢等問題，在物流配送問題上適應(yīng)性較強(qiáng)。Mohammed等[17]則利用兩階段遺傳算法尋找車輛最優(yōu)路徑。雖然現(xiàn)有研究針對這些問題提出了很多改進(jìn)方案，但這些研究都只以最短路徑為優(yōu)化目標(biāo)而忽略了運(yùn)輸過程中時間窗和成本的問題，這就導(dǎo)致方法的實際運(yùn)用性不高，而考慮運(yùn)輸成本和時間窗的多目標(biāo)優(yōu)化問題更貼近實際情況，具有更高的研究價值。

國內(nèi)外學(xué)者對多目標(biāo)路徑優(yōu)化問題也做過許多研究如梅夢婷等[18]提出結(jié)合差分法的DE-NSGA算法考慮值班時間等因素，有效改善了路徑尋優(yōu)速度但收斂速度較慢。萬逸飛等[19]提出協(xié)同非支配排序遺傳算法求解機(jī)器人路徑規(guī)劃問題并用柵格法證明了算法的有效性但參數(shù)設(shè)置較為復(fù)雜，段征宇等[20]則在傳統(tǒng)VRP模型的基礎(chǔ)上,考慮路網(wǎng)交通狀態(tài)的時變性和隨機(jī)性，設(shè)計了一種帶硬時間窗的隨機(jī)時變車輛路徑問題的非支配排序蟻群算法。改進(jìn)的多目標(biāo)優(yōu)化算法雖然較傳統(tǒng)單目標(biāo)算法的實際應(yīng)用性更高，但在車輛路徑優(yōu)化問題上仍然存在著參數(shù)設(shè)置復(fù)雜、收斂速度慢、容易陷入局部最優(yōu)等問題，且大部分并未將時間窗和遲到懲罰成本等納入模型。

針對這些問題提出一種改進(jìn)的劣汰組NSGA-II算法(Elimination Group NSGA-II,EGNSGA-II)，該算法能夠克服陷入局部最優(yōu)的問題，且具有收斂速度快、參數(shù)設(shè)置簡單、精確度高等優(yōu)點(diǎn)。算法首先通過劣汰組策略將某些更接近最優(yōu)Pareto前沿卻因擁擠度排序被剔除的個體進(jìn)行二次非支配排列，引入到最優(yōu)Pareto前沿中提高算法的粒子多樣性以擴(kuò)大其搜索范圍，再引入全局最優(yōu)個體改進(jìn)粒子進(jìn)化公式，加快最優(yōu)Pareto前沿收斂，提升收斂精度，并用ZDT1-ZDT4典型函數(shù)驗證了算法改進(jìn)的有效性。最后將算法應(yīng)用于物流車輛路徑規(guī)劃實例，證明算法對于路徑規(guī)劃問題有良好的適應(yīng)性，能夠顯著減少快遞投放時間，提升物流行業(yè)運(yùn)轉(zhuǎn)效率增加企業(yè)收益。

1 模型建立

假設(shè)在某城市有一快遞物流中心P，負(fù)責(zé)將快遞送至本區(qū)域設(shè)置的n個快遞點(diǎn)倉庫N=(1,2,…,n)內(nèi)，物流中心擁有M=(1,2,…,m)輛載貨量為T、平均運(yùn)輸速度為v的運(yùn)輸車，快遞點(diǎn)倉庫i與快遞點(diǎn)倉庫j之間的距離為Rij，快遞點(diǎn)倉庫i的收貨量為Pi，卸貨時間為Hi，最佳卸貨時間窗為t∈[Qi,Ei]，其中：Qi表示快遞倉庫i最早卸貨時間，若運(yùn)輸車輛早于該時間到達(dá)，則需要等到時刻Qi再開始卸貨；Ei則表示其最晚接受卸貨時間，若貨車到達(dá)時刻超過時間Ei會產(chǎn)生超時懲罰成本Tpub。車輛每次運(yùn)輸都從物流中心開始并最終回到物流中心。

快遞點(diǎn)倉庫所需貨物只能由一輛運(yùn)輸車運(yùn)輸且只運(yùn)輸一次：

(1)

式中：Gij表示以快遞點(diǎn)倉庫為行、以運(yùn)輸車輛為列的矩陣中第i行第j列的數(shù)據(jù)，快遞點(diǎn)倉庫i貨物由車輛j運(yùn)輸則Gij=1，否則Gij=0。

運(yùn)輸貨物總量不得超過運(yùn)輸車的最大載重即：

(2)

式中：Tj表示第j輛運(yùn)輸車的最大載重，車輛j一共需要運(yùn)送k個快遞點(diǎn)的貨物。

當(dāng)運(yùn)輸車輛運(yùn)輸貨物到達(dá)時刻晚于最晚接受卸貨時間Ei時其超時懲罰成本為：

Tpub=α×(Dij-Ei)Dij>Ei,i∈[1,k]

(3)

式中：α為單位時間內(nèi)超時成本系數(shù)；Dij表示第j輛運(yùn)輸車到達(dá)第i個快遞點(diǎn)的時刻。

所有運(yùn)輸車輛將貨物送到所需的總時間Sall為：

(4)

為了創(chuàng)造最大效益，可以確定目標(biāo)函數(shù)為使得物流中心使用的運(yùn)輸總成本、運(yùn)輸總時間都最小即：

(5)

式中：Mkm表示車輛每公里的運(yùn)輸成本；q表示一共使用的派送車輛數(shù)。

2 算法設(shè)計

2.1 傳統(tǒng)NSGA-II算法

對于多目標(biāo)優(yōu)化問題，人們常常無法評判解的好壞，而NSGA算法很好地解決了這個問題。NSGA-II算法是Deb等[21]在NSGA的基礎(chǔ)上提出的，是一種基于Pareto最優(yōu)解的多目標(biāo)優(yōu)化算法。相對于NSGA算法，其引入了快速非支配排序算法降低計算的復(fù)雜度，采用擁擠度比較同一等級個體的優(yōu)劣，還加入了精英策略擴(kuò)大了采樣空間，在各方面性能上相較NSGA-I算法都有了顯著提升。

2.1.1Pareto等級及支配關(guān)系

對于最小化的多目標(biāo)優(yōu)化問題，假定某個多目標(biāo)優(yōu)化問題共有n個目標(biāo)分量,個體解Xm=(gm1(x),gm2(x),…,gmn(x))，任意給定兩個多目標(biāo)函數(shù)個體Xa、Xb。

(6)

若個體Xa、Xb滿足式(6)，則Xa支配Xb，即Xb被Xa支配。對于某個體，如果不存在任何個體能支配它，則該個體被稱作非支配解，在一個種群中相互比較，將所有非支配解找出，這些非支配解形成的解集Pareto等級定義為1，將非支配解剔除后，剩下的個體尋找所有非支配解Pareto等級定義為2，以此類推定義所有解的Pareto等級。以二維多目標(biāo)優(yōu)化問題為例，非支配排序結(jié)果如圖1所示。

圖1 雙目標(biāo)非支配排序Pareto等級圖

2.1.2 擁擠度排序

為了使得在空間中得到分布更加均勻的個體，將某Pareto等級下的所有個體的每一個目標(biāo)分量按大小進(jìn)行排序，將排序后每個目標(biāo)分量下的數(shù)值按照式(7)計算某個體的總體擁擠度

(7)

圖2 雙目標(biāo)擁擠度示意圖

2.1.3 精英保留策略

從所有Pareto等級的解中選擇新的父代種群時遵循Pareto等級從小到大依次選擇以保證個體的優(yōu)質(zhì)性，當(dāng)Pareto等級i中的個體被全部選擇，而剩余所需選擇個體又小于Pareto等級i+1的個體總數(shù)時，依據(jù)擁擠度排序優(yōu)先選擇擁擠度更大的個體直至父代種群個體達(dá)到飽和。精英保留策略既能夠保證個體優(yōu)質(zhì)性也能保證其均勻分布性。

2.1.4 編碼交叉及多項式變異

父代種群確定后要進(jìn)行編碼交叉和多項式變異產(chǎn)生新子代個體，模擬交叉變異公式為：

(8)

式中：x1j(t)表示第t次迭代下個體1的第j維目標(biāo)分量。

(9)

式中：δj為(0,1)內(nèi)的隨機(jī)數(shù)；λ為常系數(shù)可根據(jù)變異效果調(diào)整大小。

父代交叉變異產(chǎn)生的新子代個體與父代融合進(jìn)行下一次的非支配排序直至到達(dá)最大迭代次數(shù)，此時輸出Pareto等級為1的個體即為最優(yōu)Pareto前沿。

2.2 劣汰策略NSAGA-II算法

2.2.1 劣汰組策略

NSGA-II在選擇個體少于某Pareto等級下個體時會根據(jù)擁擠度值的大小選擇其中較為分散的個體，但是這種選擇策略也存在一定弊端如圖3所示。圖3中需要從Pareto等級1下的6個個體中選擇5個個體，此時相比于4號、5號個體，3號個體離最優(yōu)Pareto前沿較近，但由于擁擠度選擇原則3號個體擁擠度最低被剔除，由于個體迭代變異是隨機(jī)的，可能3號優(yōu)質(zhì)個體不會再出現(xiàn)，導(dǎo)致解的整體質(zhì)量下降，收斂速度變慢。

圖3 二維多目標(biāo)個體選擇示意圖

為了解決此問題，設(shè)立劣汰組集合，將因為擁擠度排序被淘汰的個體放入劣汰組進(jìn)行二次非支配排序，此時仍然不在最優(yōu)前沿的個體被永久舍棄，當(dāng)劣汰組的個體達(dá)到最大數(shù)量且全部處于最小Pareto等級下時劣汰組成熟，等待算法結(jié)束與最后一代種群合并再次進(jìn)行非支配排序，最終得到最優(yōu)Pareto前沿，該方法能夠顯著增加優(yōu)質(zhì)個體數(shù)量使算法更快收斂。

2.2.2 全局最優(yōu)變異公式

多目標(biāo)優(yōu)化問題由于目標(biāo)分量間無法比較優(yōu)劣所以無法求取最優(yōu)個體，但所有目標(biāo)分量都向最小值方向優(yōu)化，由此假設(shè)取所有目標(biāo)分量和最小的個體為近似最優(yōu)個體，據(jù)此改進(jìn)個體更新公式：

(10)

2.2.3 環(huán)淘汰制

NSGA-II算法通過擁擠度排序一次性產(chǎn)生剩余所需子代個體數(shù)量以保證子代個體的均勻分布性，但此方式很容易因為某Pareto等級下的個體排列不均勻?qū)е碌玫降膫€體分布性較差，如圖4所示。

圖4 Pareto等級2下個體分布圖

根據(jù)圖4，假設(shè)子代個體在選擇完P(guān)areto等級1的所有個體后還需要從Pareto等級2中選擇3個個體，根據(jù)擁擠度排序方式，應(yīng)該選擇1號、2號、3號個體，但很明顯選擇1號、3號、5號個體其分布性更好，由此可見，傳統(tǒng)擁擠度策略存在一定缺陷。

所以采用循環(huán)淘汰制方式，假設(shè)還需要從某Pareto等級下的k個個體中選擇m個個體組成子代種群，先計算所有個體的擁擠度大小，將擁擠度最小的個體淘汰，再次進(jìn)行擁擠度排序，繼續(xù)淘汰擁擠度最小個體，循環(huán)k-m次，剩下的個體即為所需選擇個體。這樣的選擇方式能夠最大程度保證子代個體的均勻分布，加快算法的收斂速度。改進(jìn)后的劣汰組NSGA-II算法流程如圖5所示。

圖5 劣汰組NSGA-II算法流程

3 仿真實驗與分析

為了驗證本文算法改進(jìn)的有效性，選擇傳統(tǒng)NSGA-II算法、劣汰組策略NSGA-II算法、Deb等[22-23]提出的遵循NSGGA-II框架的基于參考點(diǎn)的NSGA-III算法來測試多目標(biāo)函數(shù)的經(jīng)典測試函數(shù)ZDT1-ZDT4，其優(yōu)化結(jié)果如圖6所示。

(a) ZDT1

(b) ZDT2

(c) ZDT3

(d) ZDT4圖6 四種典型測試函數(shù)Pareto前沿圖

由圖6可知，在四個典型算例中，EGNSGA-II算法所得到的最優(yōu)前沿面都要優(yōu)于NSGA-II算法，在ZDT2-ZDT4三個函數(shù)中，EGNSGA-II算法的最優(yōu)前沿也明顯優(yōu)于Deb等提出的基于參考點(diǎn)的NSGA-III算法，該測試證明了算法改進(jìn)的有效性。

在S=100 km×100 km的范圍里，存在一個物流中心P=(55,45),該物流中心擁有4輛不同型號的運(yùn)輸車即m=4，需要在一天內(nèi)向周圍存在的20個快遞點(diǎn)倉庫進(jìn)行貨物供給，車輛和快遞點(diǎn)倉庫的具體信息見表1和表2。

表1 運(yùn)輸車輛信息表

表2 快遞點(diǎn)倉庫信息表

續(xù)表2

根據(jù)表1、表2提供的數(shù)據(jù)，設(shè)初始父代種群個體數(shù)量N=500，劣汰組的個體數(shù)量為Nl=200，迭代最大次數(shù)tmax=200，目標(biāo)分量n=2，用NSGA-III算法、多目標(biāo)粒子群算法(MOPSO)、改進(jìn)的NSGA-II算法、傳統(tǒng)NSGA-II算法對該問題進(jìn)行求解，得到的Pareto最優(yōu)前沿如圖7所示。

圖7 四種算法的Pareto最優(yōu)前沿

根據(jù)圖7可以很明顯地看出改進(jìn)的劣汰組NSGA-II前沿面分布性更好，覆蓋范圍更大，能夠得到更精確的結(jié)果。將算法最優(yōu)前沿面所有點(diǎn)的目標(biāo)函數(shù)值求和，選取求和后最小的數(shù)值作為適應(yīng)度數(shù)值，可以得到四種算法的迭代過程如圖8所示。

圖8 四種算法迭代過程

可以看出，EGNSGA-II算法在27次左右就得到最優(yōu)結(jié)果，相對于MOPSO、NSGA-II算法擁有更快的迭代速度以及更高的精度，算法性能對比提升顯著。另一方面，在搜索前期NSGA-III算法與EGNSGA-II算法擁有著相似的收斂速度，但在收斂后期局部搜索過程中，EGNSGA-II算法的收斂速度更快且相對收斂精度更高。綜合以上分析可以看出，EGNSGA-II算法在收斂速度和精度上都更加優(yōu)秀，從而證明了該算法改進(jìn)的有效性，對路徑搜索問題的適應(yīng)性較好。

因為時間數(shù)據(jù)差異并不大，而運(yùn)輸成本是影響企業(yè)效益的首要因素，所以在最優(yōu)Pareto前沿選擇最優(yōu)解時將成本作為主要考慮的目標(biāo)分量，得到最終的優(yōu)化結(jié)果如表3所示。

表3 兩種算法求解結(jié)果表

可以看出，在相同的配送時間下EGNSGA-II算法耗費(fèi)的成本最低，改進(jìn)后的算法能夠有效幫助物流企業(yè)降低成本，在此方案下4輛運(yùn)輸車的行駛路線如圖9所示。

圖9 運(yùn)輸車路線規(guī)劃

可以看出，四輛運(yùn)輸車的運(yùn)輸分配相對均勻，符合物流行業(yè)實際運(yùn)輸情況，算法對于該問題的適應(yīng)性較好。

4 結(jié) 語

針對物流行業(yè)快遞配送效率不高、車輛路徑分配不合理等問題提出一種基于劣汰組策略的NSGA-II多目標(biāo)優(yōu)化算法，該算法采用劣汰組策略保留被擁擠度排序淘汰的優(yōu)質(zhì)個體，增加個體多樣性擴(kuò)大前期搜索范圍，再將近似全局最優(yōu)個體引入變異公式，平衡算法全局和局部的搜索能力，提高算法收斂精度和速度，再利用循環(huán)淘汰制策略增強(qiáng)子代個體的分布性。用典型的多目標(biāo)測試函數(shù)對改進(jìn)算法進(jìn)行驗證，證明了改進(jìn)的有效性。最后通過物流運(yùn)輸實例證明該算法對物流車輛路徑規(guī)劃問題適應(yīng)性很好，相對于傳統(tǒng)NSGA-II算法性能上有較大提升。接下來會嘗試將其他算法與改進(jìn)后的NSGA-II算法進(jìn)行有效融合進(jìn)一步提升算法的各方面性能。