包賢哲 宋阿妮

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

0 引 言

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

物流運(yùn)輸車輛路徑規(guī)劃問題本質(zhì)上是一個(gè)帶約束的NP難問題，隨著對(duì)智能優(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)行了驗(yàn)證。Akhand等[10]結(jié)合自適應(yīng)掃描策略改進(jìn)粒子群算法來優(yōu)化路徑；齊名軍等[11]提出動(dòng)態(tài)猴子跳躍機(jī)制改進(jìn)粒子群算法提高算法收斂性并用物流實(shí)例驗(yàn)證了算法的有效性。Lai等[12]采用模擬退火算法以及TSA來降低使用車輛數(shù)和行駛成本；混合模擬退火算法[13-14]在路徑規(guī)劃問題上也有著不錯(cuò)的效果。Wang等[15]采用哈希函數(shù)加速禁忌狀態(tài)來獲得更好的優(yōu)化方案；方文婷等[16]結(jié)合A*算法和蟻群算法克服算法前期收斂慢等問題，在物流配送問題上適應(yīng)性較強(qiáng)。Mohammed等[17]則利用兩階段遺傳算法尋找車輛最優(yōu)路徑。雖然現(xiàn)有研究針對(duì)這些問題提出了很多改進(jìn)方案，但這些研究都只以最短路徑為優(yōu)化目標(biāo)而忽略了運(yùn)輸過程中時(shí)間窗和成本的問題，這就導(dǎo)致方法的實(shí)際運(yùn)用性不高，而考慮運(yùn)輸成本和時(shí)間窗的多目標(biāo)優(yōu)化問題更貼近實(shí)際情況，具有更高的研究價(jià)值。

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

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

1 模型建立

假設(shè)在某城市有一快遞物流中心P，負(fù)責(zé)將快遞送至本區(qū)域設(shè)置的n個(gè)快遞點(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，卸貨時(shí)間為Hi，最佳卸貨時(shí)間窗為t∈[Qi,Ei]，其中：Qi表示快遞倉庫i最早卸貨時(shí)間，若運(yùn)輸車輛早于該時(shí)間到達(dá)，則需要等到時(shí)刻Qi再開始卸貨；Ei則表示其最晚接受卸貨時(shí)間，若貨車到達(dá)時(shí)刻超過時(shí)間Ei會(huì)產(chǎn)生超時(shí)懲罰成本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個(gè)快遞點(diǎn)的貨物。

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

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

(3)

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

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

(4)

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

(5)

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

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

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

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

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

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

(6)

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

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

2.1.2 擁擠度排序

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

(7)

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

2.1.3 精英保留策略

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

2.1.4 編碼交叉及多項(xiàng)式變異

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

(8)

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

(9)

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

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

2.2 劣汰策略NSAGA-II算法

2.2.1 劣汰組策略

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

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

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

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

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

(10)

2.2.3 環(huán)淘汰制

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

圖4 Pareto等級(jí)2下個(gè)體分布圖

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

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

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

3 仿真實(shí)驗(yàn)與分析

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

(a) ZDT1

(b) ZDT2

(c) ZDT3

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

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

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

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

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

續(xù)表2

根據(jù)表1、表2提供的數(shù)據(jù)，設(shè)初始父代種群個(gè)體數(shù)量N=500，劣汰組的個(gè)體數(shù)量為Nl=200，迭代最大次數(shù)tmax=200，目標(biāo)分量n=2，用NSGA-III算法、多目標(biāo)粒子群算法(MOPSO)、改進(jìn)的NSGA-II算法、傳統(tǒng)NSGA-II算法對(duì)該問題進(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é)果，相對(duì)于MOPSO、NSGA-II算法擁有更快的迭代速度以及更高的精度，算法性能對(duì)比提升顯著。另一方面，在搜索前期NSGA-III算法與EGNSGA-II算法擁有著相似的收斂速度，但在收斂后期局部搜索過程中，EGNSGA-II算法的收斂速度更快且相對(duì)收斂精度更高。綜合以上分析可以看出，EGNSGA-II算法在收斂速度和精度上都更加優(yōu)秀，從而證明了該算法改進(jìn)的有效性，對(duì)路徑搜索問題的適應(yīng)性較好。

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

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

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

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

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

4 結(jié) 語

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