自適應(yīng)精英遺傳算法的快遞車路徑規(guī)劃

袁夢飛，闞 秀，曹 樂，王夏霖，吳健珍，羅 曉

自適應(yīng)精英遺傳算法的快遞車路徑規(guī)劃

袁夢飛，闞 秀，曹 樂，王夏霖，吳健珍，羅 曉

（上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620）

針對快遞車物流配送效率低、行駛路線不規(guī)范的問題，提出了自適應(yīng)精英遺傳算法實(shí)現(xiàn)對快遞車的路徑規(guī)劃。通過搭建車載定位系統(tǒng)，實(shí)時對車輛位置進(jìn)行監(jiān)督以確保行駛在規(guī)定路線上。在實(shí)際快遞位置分布的基礎(chǔ)上建立了路徑規(guī)劃模型，設(shè)計了基于經(jīng)緯度坐標(biāo)的適應(yīng)度函數(shù)，以地表距離作為種群評價標(biāo)準(zhǔn)更加貼合實(shí)際運(yùn)輸需求；引入自適應(yīng)交叉算子和自適應(yīng)變異算子，根據(jù)個體基因的適應(yīng)度值自適應(yīng)地調(diào)節(jié)交叉和變異概率，并將精英個體進(jìn)行遺傳保留，更好地平衡了算法的局部搜索能力和全局優(yōu)化性能。通過與其他4種智能算法的對比實(shí)驗(yàn)，來驗(yàn)證改進(jìn)算法的有效性及可行性，實(shí)驗(yàn)結(jié)果表明改進(jìn)算法的收斂性最快且解的精度明顯優(yōu)于其他4種算法。

快遞車；自適應(yīng)交叉算子；自適應(yīng)變異算子；精英遺傳策略；路徑規(guī)劃

0 引言

近年來隨著互聯(lián)網(wǎng)電商行業(yè)的蓬勃興起，快遞配送公司如雨后春筍般紛紛成立，快遞車的路徑規(guī)劃受到了越來越多專家學(xué)者和企業(yè)的關(guān)注[1-4]?？爝f配送路線問題是路徑規(guī)劃的一個重要應(yīng)用領(lǐng)域。目前主要通過智能啟發(fā)式算法求解大規(guī)模的復(fù)雜路徑規(guī)劃問題[5-6]，該類算法可以較快地找到逼近最優(yōu)解的滿意解，但是在快遞配送領(lǐng)域還有很多改進(jìn)的空間。

現(xiàn)有的智能啟發(fā)式算法主要包括：遺傳算法、模擬退火算法和蟻群算法等。文獻(xiàn)[7]利用網(wǎng)絡(luò)約簡技術(shù)對模擬退火算法進(jìn)行了改進(jìn)，并成功使用該算法為電氣與照明公司做出了運(yùn)輸規(guī)劃。文獻(xiàn)[8]通過權(quán)重策略和變異操作改進(jìn)蟻群算法，解決了多倉庫的車輛路徑規(guī)劃。文獻(xiàn)[9]提出了帕累托最優(yōu)的多目標(biāo)車輛路徑問題，將蟻群算法與三元素優(yōu)化（3-optimization，3-opt）算子相結(jié)合，通過所羅門（Solomon）數(shù)據(jù)集驗(yàn)證了算法的有效性。文獻(xiàn)[10-12]都在對遺傳算法做出改進(jìn)的基礎(chǔ)上進(jìn)行路徑規(guī)劃。其中，文獻(xiàn)[10]針對獎品領(lǐng)取車輛的路線問題，將遺傳算法與局部搜索策略相結(jié)合，提高了算法的優(yōu)越性；文獻(xiàn)[11]設(shè)計了改進(jìn)的路由復(fù)制交叉算子和基于衛(wèi)星選擇的變異算子，并將該算法用于物流服務(wù)中，減少了預(yù)期成本；文獻(xiàn)[12]針對制造商的訂單運(yùn)輸問題，將最優(yōu)生產(chǎn)序列的思想嵌入到遺傳算法中，提供了高質(zhì)量的解決方案。然而他們都沒有注意到交叉和變異概率對遺傳算法性能的影響，盡管文獻(xiàn)[11]對交叉和變異算子進(jìn)行了重新設(shè)計，卻不能實(shí)現(xiàn)算子的動態(tài)調(diào)節(jié)，難以根據(jù)當(dāng)前解的質(zhì)量自適應(yīng)調(diào)整，極易陷入局部最優(yōu)。

本文從實(shí)際的快遞配送問題出發(fā)，提出了自適應(yīng)精英遺傳算法。該算法將實(shí)際經(jīng)緯度作為模型輸入，以地表距離作為適應(yīng)度函數(shù)對種群質(zhì)量進(jìn)行評價；并設(shè)計了自適應(yīng)交叉算子和自適應(yīng)變異算子，可以根據(jù)當(dāng)前個體基因的質(zhì)量自適應(yīng)地調(diào)整交叉和變異概率，實(shí)時調(diào)整種群進(jìn)化方向；最后將上一代精英個體的適應(yīng)度值設(shè)置成下一代的閾值進(jìn)行遺傳保留，從而更加快速有效地找到高精度的解。為了將算法應(yīng)用到實(shí)際快遞車的配送中，本文搭建了車載定位系統(tǒng)，將定位模塊安裝在快遞車儀表盤內(nèi)進(jìn)行位置的讀取和上傳。企業(yè)可以根據(jù)算法提供的車輛和路徑信息進(jìn)行相應(yīng)的安排和規(guī)劃，將定位系統(tǒng)上傳的司機(jī)行駛軌跡與規(guī)劃路徑進(jìn)行有效比對，進(jìn)一步規(guī)范司機(jī)的駕駛路線，提高企業(yè)運(yùn)營效率。

1 快遞車定位系統(tǒng)及路徑規(guī)劃模型

1.1 車載定位系統(tǒng)搭建

為了獲得真實(shí)的車輛行駛軌跡信息，用于與規(guī)劃的路線進(jìn)行對比分析，本文選用如圖1所示的多模微型定位導(dǎo)航模塊。所選模塊為合宙電子推出的一款高性能、小體積、低功耗定位模塊，其內(nèi)部支持全球定位系統(tǒng)（global positioning system, GPS）、北斗衛(wèi)星導(dǎo)航系統(tǒng)（BeiDou navigation satellite system, BDS）、格洛納斯衛(wèi)星導(dǎo)航系統(tǒng)（global navigation satellite system, GLONASS）、伽利略衛(wèi)星導(dǎo)航系統(tǒng)（Galileo satellite navigation system, Galileo）等多種定位。定位系統(tǒng)安裝在圖2所示的儀表盤內(nèi)，對快遞車的經(jīng)緯度信息進(jìn)行讀取。為實(shí)現(xiàn)車輛行駛軌跡的穩(wěn)定上傳，本文采用SIM7600CE模塊作為數(shù)據(jù)傳輸模塊，該模塊為一款適用于室外穩(wěn)定信息傳輸?shù)?G通信模塊，通過SIM7600CE可實(shí)現(xiàn)采集系統(tǒng)與上層服務(wù)器的通信，實(shí)現(xiàn)定位信息的上傳。

圖1 定位模塊

圖2 定位模塊安裝示意圖

1.2 快遞配送路徑規(guī)劃模型的建立

根據(jù)北京市朝陽區(qū)某快遞業(yè)務(wù)的實(shí)際配送情況，本文主要研究只有一個配送中心且以多輛快遞車進(jìn)行配送的路徑規(guī)劃問題。在車輛不超載的情況下，對快遞車的使用數(shù)量和路線進(jìn)行優(yōu)化計算，以實(shí)現(xiàn)總行駛路徑最短。

圖3（a）為該快遞公司的實(shí)際位置分布，其中方塊表示配送中心，圓圈表示快遞客戶點(diǎn)?；趯?shí)際的地理位置信息，以經(jīng)度為橫坐標(biāo)、緯度為縱坐標(biāo)進(jìn)行路徑規(guī)劃空間建模，模型地圖如圖3（b）所示。

圖3 快遞業(yè)務(wù)分布

2 自適應(yīng)精英遺傳算法

遺傳算法根據(jù)“物競天擇，適者生存”的生物進(jìn)化思想，按照生物遺傳理論將優(yōu)化問題編碼為染色體基因的形式，通過種群遺傳的選擇、基因的交叉和變異等操作，產(chǎn)生問題的最優(yōu)解[13]。然而在進(jìn)化過程中，交叉概率和變異概率是固定不變的值，若概率值過大，會導(dǎo)致算法無法收斂；概率值過小，則容易陷入局部極優(yōu)值。算法缺少精英保留機(jī)制，適應(yīng)度值高的優(yōu)秀個體也可能在進(jìn)化過程中丟失優(yōu)良基因。

本文采用自適應(yīng)交叉算子、自適應(yīng)變異算子與精英保留策略對遺傳算法進(jìn)行優(yōu)化。為了更好地平衡算法的局部搜索能力和全局優(yōu)化性能，在進(jìn)化初期需要將交叉和變異概率設(shè)定大一些，擴(kuò)大搜索空間。到了進(jìn)化后期時，再降低交叉和變異概率，從而加快算法的收斂速度。因此，在進(jìn)化過程中，通過交叉概率和變異概率的動態(tài)調(diào)整，可以使種群的進(jìn)化方向自適應(yīng)變化并將每一代的優(yōu)秀個體作為精英直接遺傳給子代，提高了算法的尋優(yōu)能力與計算精度。

2.1 種群初始化

圖4 基因編碼解碼示例

2.2 適應(yīng)度函數(shù)

遺傳算法通過適應(yīng)度值來對個體基因的優(yōu)劣進(jìn)行評估，本文將最短路徑值作為適應(yīng)度函數(shù)。

顯然，適應(yīng)度函數(shù)值越小，表示基因越優(yōu)秀，

規(guī)劃的路徑長度也越短。

2.3 選擇算子

針對基因選擇過程，本文采用輪盤賭策略[14]進(jìn)行選擇操作。輪盤賭策略是根據(jù)個體的適應(yīng)度值確定在輪盤上所占的比例。適應(yīng)度值越高，則代表該個體基因越優(yōu)秀，在輪盤中所占的比例也越大。這種選擇策略確保了優(yōu)秀個體有較大的概率被選中，符合“優(yōu)勝劣汰”的自然規(guī)律。

2.4 交叉算子

2.4.1 自適應(yīng)交叉概率函數(shù)

為了實(shí)現(xiàn)種群在進(jìn)化過程中根據(jù)當(dāng)前個體基因的適應(yīng)度值自適應(yīng)調(diào)整交叉概率，本文定義自適應(yīng)交叉概率函數(shù)為

在種群的遺傳進(jìn)化過程中，交叉概率的大小在很大程度上決定了種群的搜索空間和基因的多樣性。自適應(yīng)交叉概率函數(shù)將交叉概率與當(dāng)代遺傳中種群適應(yīng)度值的平均值和最大值相聯(lián)系，可以在遺傳進(jìn)化的過程中更好地把握種群進(jìn)化方向。在進(jìn)化初期，不同個體之間的基因質(zhì)量參差不齊，通過自適應(yīng)交叉概率函數(shù)根據(jù)當(dāng)前個體的質(zhì)量對交叉概率進(jìn)行調(diào)節(jié)，若當(dāng)前個體的適應(yīng)度函數(shù)值較差，則增大基因的交叉概率，有利于增強(qiáng)基因的多樣性，擴(kuò)大種群的尋優(yōu)范圍；若當(dāng)前個體的適應(yīng)度函數(shù)值較好，則保持基礎(chǔ)的交叉概率不變，有利于增強(qiáng)局部搜索能力，更快地尋求最優(yōu)解。隨著進(jìn)化過程的持續(xù)進(jìn)行，到進(jìn)化后期，種群的基因不斷地優(yōu)化更新，總體保持著較高的質(zhì)量，個體之間的適應(yīng)度值相差較小，自適應(yīng)交叉概率函數(shù)以較小的交叉概率對基因的交叉進(jìn)行自適應(yīng)調(diào)節(jié)，可以在加快算法收斂速度的同時提高精度。

2.4.2 順序交叉策略

針對基因交叉過程，本文選用順序交叉策略。順序交叉策略的具體示例如圖5所示，隨機(jī)選擇一組長度相同的基因片段對父代的基因進(jìn)行交叉操作，將交叉后的基因作為子代基因進(jìn)入后續(xù)進(jìn)化過程。

圖5 交叉算子示例

2.5 自適應(yīng)變異算子

2.5.1 自適應(yīng)變異概率函數(shù)

在傳統(tǒng)的遺傳算法中，相較于交叉概率而言，變異概率值設(shè)置的較小。因此，變異概率的微小變化都會對種群基因和算法的求解性能產(chǎn)生極大的影響。為了實(shí)現(xiàn)變異概率的自適應(yīng)調(diào)節(jié)，本文定義了自適應(yīng)交叉概率函數(shù)為

自適應(yīng)變異概率函數(shù)可以根據(jù)個體當(dāng)前的適應(yīng)度函數(shù)值自適應(yīng)調(diào)整變異的概率。當(dāng)前基因的適應(yīng)度值越差則變異概率越大，在進(jìn)化尋優(yōu)的過程中逐步降低變異概率，使得種群逐漸收斂至最優(yōu)解，提高了算法的搜索效率。

2.5.2 動態(tài)變異策略

針對基因變異過程，本文采用動態(tài)變異策略。動態(tài)變異策略的具體示例如圖6所示，隨機(jī)選擇兩個或以上的基因位進(jìn)行相互間的動態(tài)置換，將置換后的基因作為變異基因遺傳給子代進(jìn)入后續(xù)進(jìn)化過程。

圖6 動態(tài)變異算子示例

2.6 精英保留策略

精英保留策略避免了對優(yōu)秀基因進(jìn)行重復(fù)計算且在更大程度上保護(hù)了優(yōu)秀基因，提高了算法的運(yùn)行效率。

2.7 算法框架

本算法設(shè)計了自適應(yīng)交叉算子與變異算子，根據(jù)當(dāng)前個體的適應(yīng)度函數(shù)值生成自適應(yīng)交叉和變異概率，對選中的基因進(jìn)行順序交叉和動態(tài)變異?；谶z傳進(jìn)化的特征，采用了精英個體的遺傳保留策略。算法具有較強(qiáng)的全局搜索能力，收斂性也較高。

算法的設(shè)計框架如下所示，其中為當(dāng)前迭代次數(shù)，ter為最大迭代次數(shù)。

Algorithm:自適應(yīng)精英遺傳算法 Input: Latitude and longitude matrix Initialize:, while do Population selection: Roulette strategy;Calculate population f according to (5); Population crossover: Calculate pcaccording to (8);Order crossover; Population variation: Calculate pmaccording to (9);Dynamic variation;Elite genetic preservation according to (10); Update population genes; end while Output: Theshortest path.

3 實(shí)驗(yàn)分析與討論

3.1 實(shí)驗(yàn)結(jié)果

表1 配送中心和客戶點(diǎn)經(jīng)緯度信息

表2 車輛和路徑安排

為了更好地了解算法的求解性能，本文根據(jù)圖7的配送方案繪制了如圖8所示的迭代收斂曲線，進(jìn)一步衡量算法的有效性。從迭代收斂曲線可以看出，自適應(yīng)精英遺傳算法在前60次迭代過程中優(yōu)化曲線下降趨勢陡峭，收斂速度較快；隨著迭代次數(shù)的增加，優(yōu)化曲線趨于平坦，在第166次迭代后進(jìn)入穩(wěn)定狀態(tài)，收斂至最優(yōu)解318.6。

圖7 具體配送路線

圖8 自適應(yīng)精英遺傳算法迭代曲線

3.2 與其他算法對比實(shí)驗(yàn)

為了檢驗(yàn)自適應(yīng)精英遺傳算法的有效性，在同樣的實(shí)驗(yàn)環(huán)境下分別與遺傳算法、模擬退火算法、蟻群算法、人工魚群算法4種算法進(jìn)行對比實(shí)驗(yàn)，通過測試結(jié)果驗(yàn)證所提算法的性能。4種算法的配送方案適應(yīng)度值對比如表3所示，車輛路徑如圖9所示。

表3 算法適應(yīng)度值對比

通過對比發(fā)現(xiàn)，在遺傳算法、模擬退火算法、蟻群算法、人工魚群算法4種算法中，蟻群算法的求解性能相比其他3種算法而言效果略好，但是仍然與自適應(yīng)精英遺傳算法存在一定的差距。從車輛和路徑的具體安排可以看出，遺傳算法、模擬退火算法、人工魚群算法都采用了7輛車進(jìn)行配送，而本文提出的自適應(yīng)精英遺傳算法和蟻群算法均采用6輛車進(jìn)行配送。在快遞車的配送過程中，增加車輛的使用數(shù)量會增加車輛從配送中心出發(fā)和返回配送中心的這兩段路徑，因而在很大程度上增加行駛距離。為了減少快遞車的行駛距離，算法在尋優(yōu)過程中會根據(jù)本文設(shè)置的最大車輛使用數(shù)量，逐步合并路徑從而減少車輛的使用數(shù)量。因此，在保證車輛不超載的一般情況下，使用車輛的數(shù)量越少，算法的尋優(yōu)效果越好，所得到的行駛路徑也更短。

圖9 4種算法車輛和路徑安排

自適應(yīng)精英遺傳算法與其他4種算法的迭代收斂對比如圖10所示。圖10中結(jié)果表明，蟻群算法在4種對比算法中收斂速度最快，與本文提出算法的收斂速度相當(dāng)。然而在收斂至相同解的情況下，本文提出的算法收斂曲線更加陡峭，收斂速度也更快。

圖10 自適應(yīng)精英遺傳算法與其他算法迭代收斂曲線

綜合以上分析，本文所提出的自適應(yīng)精英遺傳算法具有較好的收斂性，尋優(yōu)效果和求解性能都較出色。

4 結(jié)束語

為了有效提高配送效率，進(jìn)一步規(guī)范快遞車在物流配送中的行駛路線，本文提出了自適應(yīng)精英遺傳算法。通過在快遞車上搭建車載定位系統(tǒng)，實(shí)時獲得車輛的行駛軌跡信息以確保車輛行駛在規(guī)定的路線范圍內(nèi)。為了減少快遞車的行駛路徑，根據(jù)實(shí)際快遞配送業(yè)務(wù)建立了路徑規(guī)劃模型，將客戶點(diǎn)的經(jīng)緯度坐標(biāo)轉(zhuǎn)換為地表距離作為適應(yīng)度函數(shù)，從而實(shí)現(xiàn)對種群質(zhì)量的有效評估，并設(shè)計了自適應(yīng)交叉算子和自適應(yīng)變異算子對遺傳算法中的交叉和變異概率進(jìn)行自適應(yīng)調(diào)節(jié)。在種群進(jìn)化的過程中，本文改進(jìn)的算法交叉和變異概率可以根據(jù)個體的適應(yīng)度函數(shù)值進(jìn)行動態(tài)調(diào)節(jié)，從而有效控制算法的收斂速度和運(yùn)行效率，并將上一代精英個體的適應(yīng)度值作為閾值對下一代進(jìn)行遺傳保留。通過與其他4種智能算法的實(shí)驗(yàn)對比，證明了本文改進(jìn)的算法能夠使用較少的車輛完成配送任務(wù)，減少了行駛路徑，且收斂速度較快、求解精度也更高。

[1] 江海, 陳峰. 面向快遞同城運(yùn)輸?shù)能囕v路徑問題研究[J]. 工業(yè)工程, 2019, 22(4): 58-63.

[2] 禹鑫燚, 郭永奎, 歐林林, 等. 基于線性時序邏輯的移動端快遞派送路徑規(guī)劃[J]. 高技術(shù)通訊, 2017, 27(6): 544-553.

[3] 宋汶軒. 城市快遞配送車輛路徑規(guī)劃研究[D]. 北京: 北京郵電大學(xué), 2019.

[4] 鄭丹陽, 毛劍琳, 郭寧, 等. 多車場動態(tài)路徑問題的自適應(yīng)量子蟻群算法[J]. 傳感器與微系統(tǒng), 2017, 36(10): 133-136.

[5] ZHANG S, GAJPAL Y, APPADOO S S. A meta-heuristic for capacitated green vehicle routing problem[J]. Annals of Operations Research, 2018, 269(1/2): 753-771.

[6] 楊旭, 王銳, 張濤. 面向無人機(jī)集群路徑規(guī)劃的智能優(yōu)化算法綜述[J]. 控制理論與應(yīng)用, 2020, 37(11): 2291-2302.

[7] KHODABANDEH E, BAI L H, HERAGU S S, et al. Modelling and solution of a large-scale vehicle routing problem at GE appliances & lighting[J]. International Journal of Production Research, 2017, 55(4): 1100-1116.

[8] YU B, YANG Z Z, XIE J X. A parallel improved ant colony optimization for multi-depot vehicle routing problem[J]. Journal of the Operational Research Society, 2011, 62(1): 183-188.

[9] ZHANG H Z, ZHANG Q W, MA L A, et al. A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows[J]. Information Sciences, 2019, 490: 166-190.

[10] LONG J Y, SUN Z Z, PARDALOS P M, et al. A hybrid multi-objective genetic local search algorithm for the prize-collecting vehicle routing problem[J]. Information Sciences, 2019, 478: 40-61.

[11] WANG K Z, LAN S L, ZHAO Y X. A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service[J]. Journal of the Operational Research Society, 2017, 68(11): 1409-1421.

[12] ZOU X X, LIU L, LI K P, et al. A coordinated algorithm for integrated production scheduling and vehicle routing problem[J]. International Journal of Production Research, 2018, 56(15): 5005-5024.

[13] 呂倩, 孫憲坤, 熊玉潔. 改進(jìn)遺傳算法的無人機(jī)路徑規(guī)劃[J]. 導(dǎo)航定位學(xué)報, 2020, 8(5): 42-48.

[14] 馬潔瑩. 基于輪盤賭策略的混沌螢火蟲算法研究[D]. 西安: 西安電子科技大學(xué), 2018.

Path planning of express vehicle based on adaptive elite genetic algorithm

YUAN Mengfei, KAN Xiu, CAO Le, WANG Xialin, WU Jianzhen, LUO Xiao

（School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China）

Aiming at the problem of low logistics distribution efficiency of express vehicles and irregular driving routes, an adaptive elite genetic algorithm was proposed to realize the path planning of express vehicles. By building a vehicle-mounted positioning system, the vehicle position was monitored in real time to ensure that it was driving on a prescribed route. A path planning model was established on the basis of the actual express location distribution, and a fitness function based on latitude and longitude coordinates was designed, and the ground distance was used as the population evaluation criterion to better fit the actual transportation needs; adaptive crossover operator and adaptive mutation operator were introduced according to the fitness value of individual genes, adaptively adjusted the crossover and mutation probability, and retained the elite individuals genetically, which better balanced the local search ability and global optimization performance of the algorithm. Through comparative experiments with other four intelligent algorithms, the effectiveness and feasibility of the improved algorithm were verified. The experimental results showed that the improved algorithm had the fastest convergence and the accuracy of the solution was significantly better than the other four algorithms.

express vehicle; adaptive crossover operator; adaptive mutation operator; elite genetic strategy; path planning

P228

A

2095-4999(2021)06-0104-08

袁夢飛，闞秀，曹樂，等. 自適應(yīng)精英遺傳算法的快遞車路徑規(guī)劃[J]. 導(dǎo)航定位學(xué)報,2021,9(6): 104-111.（YUAN Mengfei, KAN Xiu, CAO Le, et al. Path planning of express vehicle based on adaptive elite genetic algorithm[J].Journal of Navigation and Positioning, 2021, 9(6): 104-111.)

10.16547/j.cnki.10-1096.20210616.

2021-02-04

國家自然科學(xué)基金項(xiàng)目(61703270)。

袁夢飛(1995—)，女，江蘇揚(yáng)州人，碩士研究生，研究方向?yàn)閿?shù)據(jù)處理、路徑規(guī)劃。

闞秀(1983—)，女，上海人，博士，副教授，研究方向?yàn)閿?shù)據(jù)處理、網(wǎng)絡(luò)化系統(tǒng)研究。