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

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

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

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

（上海工程技術大學 電子電氣工程學院，上海 201620）

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

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

0 引言

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

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

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

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

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

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

圖1 定位模塊

圖2 定位模塊安裝示意圖

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

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

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

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

2 自適應精英遺傳算法

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

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

2.1 種群初始化

圖4 基因編碼解碼示例

2.2 適應度函數(shù)

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

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

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

2.3 選擇算子

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

2.4 交叉算子

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

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

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

2.4.2 順序交叉策略

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

圖5 交叉算子示例

2.5 自適應變異算子

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

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

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

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

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

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

2.6 精英保留策略

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

2.7 算法框架

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

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

Algorithm:自適應精英遺傳算法 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 實驗分析與討論

3.1 實驗結果

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

表2 車輛和路徑安排

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

圖7 具體配送路線

圖8 自適應精英遺傳算法迭代曲線

3.2 與其他算法對比實驗

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

表3 算法適應度值對比

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

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

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

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

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

4 結束語

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

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

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

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

[4] 鄭丹陽, 毛劍琳, 郭寧, 等. 多車場動態(tài)路徑問題的自適應量子蟻群算法[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] 楊旭, 王銳, 張濤. 面向無人機集群路徑規(guī)劃的智能優(yōu)化算法綜述[J]. 控制理論與應用, 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] 呂倩, 孫憲坤, 熊玉潔. 改進遺傳算法的無人機路徑規(guī)劃[J]. 導航定位學報, 2020, 8(5): 42-48.

[14] 馬潔瑩. 基于輪盤賭策略的混沌螢火蟲算法研究[D]. 西安: 西安電子科技大學, 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

袁夢飛，闞秀，曹樂，等. 自適應精英遺傳算法的快遞車路徑規(guī)劃[J]. 導航定位學報,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

國家自然科學基金項目(61703270)。

袁夢飛(1995—)，女，江蘇揚州人，碩士研究生，研究方向為數(shù)據(jù)處理、路徑規(guī)劃。

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