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

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

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

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

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

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

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

0 引言

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

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

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

1 快遞車定位系統及路徑規劃模型

1.1 車載定位系統搭建

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

圖1 定位模塊

圖2 定位模塊安裝示意圖

1.2 快遞配送路徑規劃模型的建立

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

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

圖3 快遞業務分布

2 自適應精英遺傳算法

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

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

2.1 種群初始化

圖4 基因編碼解碼示例

2.2 適應度函數

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

顯然，適應度函數值越小，表示基因越優秀，

規劃的路徑長度也越短。

2.3 選擇算子

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

2.4 交叉算子

2.4.1 自適應交叉概率函數

為了實現種群在進化過程中根據當前個體基因的適應度值自適應調整交叉概率，本文定義自適應交叉概率函數為

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

2.4.2 順序交叉策略

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

圖5 交叉算子示例

2.5 自適應變異算子

2.5.1 自適應變異概率函數

在傳統的遺傳算法中，相較于交叉概率而言，變異概率值設置的較小。因此，變異概率的微小變化都會對種群基因和算法的求解性能產生極大的影響。為了實現變異概率的自適應調節，本文定義了自適應交叉概率函數為

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

2.5.2 動態變異策略

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

圖6 動態變異算子示例

2.6 精英保留策略

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

2.7 算法框架

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

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

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 配送中心和客戶點經緯度信息

表2 車輛和路徑安排

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

圖7 具體配送路線

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

3.2 與其他算法對比實驗

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

表3 算法適應度值對比

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

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

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

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

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

4 結束語

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

[1] 江海, 陳峰. 面向快遞同城運輸的車輛路徑問題研究[J]. 工業工程, 2019, 22(4): 58-63.

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

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

[4] 鄭丹陽, 毛劍琳, 郭寧, 等. 多車場動態路徑問題的自適應量子蟻群算法[J]. 傳感器與微系統, 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]. 控制理論與應用, 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]. 導航定位學報, 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

袁夢飛，闞秀，曹樂，等. 自適應精英遺傳算法的快遞車路徑規劃[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—)，女，江蘇揚州人，碩士研究生，研究方向為數據處理、路徑規劃。

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