孫睿 黃海超 霍欣婷 陳景雅

摘 要：優(yōu)化智能算法進行路徑規(guī)劃可以有效緩解用戶出行擁堵問題，為此，設計了多目標優(yōu)化-改進遺傳算法（multi-objective-improved genetic algorithm， M-IGA）組合模型。采用Dijkstra算法改進種群初始化策略，完全規(guī)避了斷路和環(huán)路，提高了初始種群質量；設計基于鄰接矩陣的深度優(yōu)先遍歷交叉策略、鄰接限制半隨機變異策略，兼顧算法全局搜索和局部尋優(yōu)能力，解決了種群多樣性降低、過早收斂的問題。同時，在設計適應度函數(shù)時，引入個體用戶偏好權重系數(shù)，綜合考慮了平均行駛時間、交叉口延誤、道路擁擠狀況、道路等級4種因素來進行多目標優(yōu)化，為用戶尋找符合個體期望的最優(yōu)路徑。研究結果表明，所提出模型相比于蟻群算法路徑尋優(yōu)效率提高了54.322 0%；相比于單目標路徑尋優(yōu)，最優(yōu)路徑綜合代價降低了23.609 1%，有效避開了擁堵及交叉口多的路段。

關鍵詞：多目標優(yōu)化；改進遺傳算法；路徑規(guī)劃；層次分析法

中圖分類號：U491

文獻標志碼：A

隨著社會經濟的不斷發(fā)展，人民生活水平不斷提高，城市路網(wǎng)上私人汽車數(shù)量不斷增加，由此帶來的道路擁堵、停車困難等現(xiàn)象日趨嚴重［1］。路徑誘導及導航服務是智能交通系統(tǒng)的重要組成部分［2］，是解決用戶出行交通擁堵問題的有效方法［3］，而合理選用和優(yōu)化智能算法進行路徑規(guī)劃是實現(xiàn)路徑誘導及導航服務的核心［4］。

遺傳算法是一種采用種群搜索策略的全局性尋優(yōu)算法，該搜索機制使求得最優(yōu)解的可能性和效率大大提高，故該算法被廣泛應用于包括路徑規(guī)劃在內的眾多問題的求解。但傳統(tǒng)遺傳算法存在早熟收斂、種群多樣性降低等問題［5］。同時，由于目前的路徑規(guī)劃研究大多以單一目標（時間最短或者距離最短）進行最優(yōu)路徑搜尋［6-11］，忽略了道路等級、道路擁堵情況等影響因素，使其對現(xiàn)實路網(wǎng)應用意義不大。

為解決以上問題，本文在改進經典遺傳算法的基礎上，針對路徑規(guī)劃應用進行了多目標優(yōu)化：一方面，改進遺傳操作解決傳統(tǒng)遺傳算法在路徑規(guī)劃中的局限性（斷路、回頭路、種群多樣性降低、早熟收斂等）；另一方面，在算法中加入反映個體出行偏好的權重系數(shù)，綜合考慮平均行駛時間、交叉口延誤、道路擁擠狀況、道路等級4種影響因素，更好地解決出行交通擁堵問題。

1 模型構建

1.1 算法編碼

區(qū)別于傳統(tǒng)的二進制編碼，采用實數(shù)編碼方式，更貼近路徑規(guī)劃現(xiàn)實問題。一條路徑就是一個染色體個體，路徑上的每一個道路交叉口或是單獨路段的起終點就是染色體上的基因［12］。如染色體“1-3-5-8-9”代表了路網(wǎng)上由起點1到終點9的一條路徑，1、3、5、8、9都是路網(wǎng)節(jié)點。傳統(tǒng)遺傳算法為了滿足交叉、變異的要求，使用的染色體長度相同［13］。本文采用變長度方式，更能豐富種群的多樣性，也符合現(xiàn)實路徑長度靈活多變的特點。

1.2 初始種群的選取

初始種群的質量在遺傳算法中起決定性作用，而遺傳算法采用完全隨機方式產生的初始種群雖然多樣性豐富［14］，但會包含大量的斷路、回頭路，這會導致算法尋優(yōu)效率降低，遲遲無法收斂。

為了保證初始種群的質量，避免斷路、回頭路的產生，本文設計了Dijkstra算法改進的半隨機方式種群初始化策略。具體步驟如下：

Step1 將路網(wǎng)中每一節(jié)點與其余節(jié)點的連接作標記，通路標記1，斷路標記0，構建鄰接矩陣；

Step2 從起點O開始，選擇下一節(jié)點時，按照鄰接矩陣選擇標記1的通路，避免斷路產生；

Step3 標記已選擇過的節(jié)點，禁止下次選中，避免回頭路產生；

Step4 如果當前節(jié)點已無未標記的連通節(jié)點，則退回上一節(jié)點重新選擇；

Step5 重復Step2—Step4，直至擴展到終點D為止，形成一條不包含斷路、環(huán)路的染色體；

Step6 重復Step2—Step5，直至染色體個數(shù)達到初始種群規(guī)模。

1.3 適應度函數(shù)的構造

遺傳算法中適應度函數(shù)也叫評價函數(shù)，是用來判斷群體中個體的優(yōu)劣程度的指標［15］。本文選用時間單位作為適應度函數(shù)的統(tǒng)一量綱，綜合考慮平均行駛時間、交叉口延誤、道路擁擠狀況、道路等級，采用層次分析法 （analytic hierarchy process， AHP）［16］計算個體用戶對以上4種影響因素的偏好權重系數(shù)。

1.3.1 4種因素的權重系數(shù)計算

1）構建判斷矩陣

在用戶現(xiàn)實選擇時，經典9種標度可能會因為重要性區(qū)分不明顯而產生困擾，故模型采用簡化后的3種標度，規(guī)定如表1所示。

根據(jù)表1構建4種因素的判斷矩陣并計算權重，其隨著用戶對4種影響因素重要性排序不同而改變，此處只是舉例說明。D1、D2、D3、D4分別對應平均行駛時間、交叉口延誤、道路擁擠狀況、道路等級4種因素，判斷矩陣如表2所示。

用和法計算D1影響因素權重：

w1=14×11+15+13+15+55+1+53+1+

33+35+1+35+55+1+53+1

=0.576 9

同理可得其余3種影響因素權重分別為：0.115 4、0.192 3、0.115 4。

2）一致性檢驗：

λmax=1n∑ni=1∑nj=1dijwj/wi

=14∑4i=1∑4j=1dijwj/wi

=4.000 2

CI=λmax－nn－1

=4.000 2－44－1

=0.000 067

CR=CIRI=0.000 0670.90

=0.000 074<0.10

式中：λmax為n階判斷矩陣的最大特征值；n為影響因素個數(shù)；dij為判斷矩陣中因素i對因素j的比重；wj、wi分別為影響因素j、i的權重；CI為一致性指標；CR為檢驗系數(shù)；RI為隨機一致性指標，判斷矩陣階數(shù)為4時取值為0.90。

判斷矩陣通過一致性檢驗。

1.3.2 4種因素量綱統(tǒng)一

1）交叉口延誤與道路擁擠狀況

對于交叉口而言，在現(xiàn)階段研究中它的主要評價指標是延誤時間。美國道路通行能力手冊給出了交叉口的評價標準，將服務水平分為六級［17］；對于道路擁擠狀況，已有研究采用模糊數(shù)學中的綜合評價方法計算道路擁擠度系數(shù)對城市路網(wǎng)的交通擁堵狀態(tài)進行評價，并將其分為6個服務水平等級［18］。鑒于交叉口和道路擁擠狀況的服務水平等級都是六級，匯總得到表3。

本文通過地點速度［19］計算擁擠度系數(shù)S來判斷服務水平等級，通過線性插值法計算路網(wǎng)交叉口的平均延誤時間t2；量化道路擁擠狀況影響因素至時間量綱，以表3中擁擠度系數(shù)S為折減系數(shù)，則擁擠延誤時間t3可在平均行駛時間t1的基礎上通過折減計算得到。

2）道路等級

曼徹斯特是英國重要交通樞紐，本文選取其局部公路網(wǎng)作為模型實驗對象，路網(wǎng)包含50個節(jié)點，交通流數(shù)據(jù)來自英國公路交通數(shù)據(jù)集［20］。在《Guidance on Road Classification and the Primary Route Network》（《道路分類和主要路網(wǎng)指南》）中，全英道路劃分為4個分類等級：A類道路，B類道路，分類未編號道路，未分類道路［21］。本文選取的曼徹斯特局部路網(wǎng)只包含A類道路和B類道路2種。圖1為簡化路網(wǎng)示意圖。

將道路等級轉換為時間量綱t4是通過將其轉換為折減系數(shù)以在平均行駛時間上進行折算。若每一條染色體個體中包含的A類道路數(shù)量≥B類道路數(shù)量，則t4=0，否則按0.2的折減系數(shù)對t1進行折減。

1.3.3 適應度函數(shù)計算

綜上，考慮平均行駛時間、交叉口延誤、道路擁擠狀況、道路等級后的適應度函數(shù)計算如下：

f=w1∑m－1i=1t1（i，i+1）+w2∑m－1i=1t2（i，i+1）+

w3∑m－1i=1t3（i，i+1）+w4t4（1）

t1（i，i+1）=L（i，i+1）（Vi+Vi+1）/2（2）

t2（i，i+1）=t2b+（t2u－t2b）（S（i，i+1）－Sb）×

（Su－Sb） （3）

t3（i，i+1）=S（i，i+1）L（i，i+1）（Vi+Vi+1）/2（4）

t4=0，NA≥NB0.2∑m－1i=1L（i，i+1）（Vi+Vi+1）/2，NA

式中：m為染色體個體中包含的路網(wǎng)節(jié)點數(shù)量；w1、w2、w3、w4分別為4種因素的權值；L（i，i+1）為節(jié)點i到節(jié)點i+1的距離；Vi、Vi+1分別為節(jié)點i， i+1的速度；S（i，i+1）為節(jié)點i到節(jié)點i+1路段的擁擠度系數(shù)；t2b、t2u分別為表3中不同服務等級對應t2的下限值和上限值；Sb、Su分別為表3中對應擁擠度系數(shù)S的下限值和上限值；NA、NB分別為一條染色體中A類、B類道路數(shù)量。

1.4 遺傳操作的改進

1.4.1 選擇操作

本文的選擇方法采用輪盤賭選擇法，但一般輪盤賭選擇法應用中，染色體個體的適應度值越大越容易被選擇保留，與本模型的適應度值越小越優(yōu)化原則相悖，所以將個體被選擇概率作如下改進：

pj=1－fj/∑spj=1fj/（sp－1）（6）

式中：sp為初始種群規(guī)模；fj為個體j的適應度值。

輪盤賭選擇結束后，為了進一步提高選擇后群體的質量，采用最佳個體保留策略，即用此時群體池中適應度值最小個體替換適應度值最大的個體，保證種群向最優(yōu)方向進化。

1.4.2 交叉操作

遺傳算法通過交叉操作將種群中2個個體隨機交換某些基因，期望有益基因組合在一起；但在路徑規(guī)劃問題中這樣的方式極大概率會使后代產生斷路、回頭路，使得交叉操作無意義，大大降低路徑尋優(yōu)的成功率和效率。因此，本文設計基于鄰接矩陣的深度優(yōu)先遍歷交叉策略，不僅完全避免了斷路、回頭路的產生，同時保證交叉操作使子代優(yōu)于父代。具體步驟如下：

Step1 在群體池中按事先設定的交叉率pc選取兩個父代個體I1，I2。

Step2 在個體I1中隨機選取一個節(jié)點m1（除起、終點外）作為待交叉點。

Step3 按照鄰接矩陣在個體I2中查找所有與m1鄰接的點，計算m1與各鄰接點的平均行駛時間，選擇最小值對應的鄰接點作為個體I2中的待交叉點。若個體I2中沒有與m1連通的鄰接點，則返回Step2重新選取待交叉點。

Step4 父代個體I1，I2分別在各自待交叉點斷開，交換前后基因，產生2個子代個體N1，N2。

Step5 計算I1，I2，N1，N2的適應度值，比較四者。若最優(yōu)個體在子代中產生，說明交叉操作成功，將四者中適應度值最小的2個個體作為交叉后產生的個體；否則交叉操作失敗，返回Step2重新選取待交叉點。

Step6 重復Step1—Step5，直至交叉操作結束。

1.4.3 變異操作

遺傳算法對變異個體采取隨機變異的方式，會破壞交叉操作的全局尋優(yōu)結果，而且在路徑規(guī)劃問題中并不能達到豐富群體多樣性的功能，反而會降低種群質量。因此，本文設計鄰接限制半隨機變異策略，在保護交叉操作全局搜索能力的基礎上，兼顧變異操作的局部搜索能力，同時維持群體的多樣性，防止出現(xiàn)未成熟收斂現(xiàn)象。具體步驟如下：

Step1 對群體池中個體按事先設定的變異概率pm判斷是否要進行變異。

Step2 在變異個體中隨機選擇除起、終點外的基因位置作為待變異點，d為待變異點在該個體中的基因位置序號。

Step3 按鄰接矩陣尋找基因位置d-1，d+1上節(jié)點的鄰接點，去除d基因位置上的節(jié)點，確定二者的交集B。

Step4 若B不是空集，則將待變異位置d上的節(jié)點隨機變異為B中包含的節(jié)點；若B是空集，返回Step2，重新選擇待變異點。

Step5 變異后檢查此時個體中是否有節(jié)點重復出現(xiàn)，若有，返回Step2。

Step6 若該個體中始終沒有符合要求的待變異點，則返回Step1，進行下一個體是否需要變異的判斷。

2 實例應用

2.1 模型參數(shù)選取

在本模型中，種群規(guī)模過小會導致算法難以收斂，同時得到的最優(yōu)路徑的綜合代價過高，不滿足用戶現(xiàn)實需求；種群規(guī)模過大會浪費計算資源，增加用戶等待時間。為選取最優(yōu)參數(shù)，進行多次實驗模擬，模擬結果如圖2所示。由圖2可以看出：隨著種群規(guī)模增大，收斂迭代次數(shù)呈下降趨勢，最優(yōu)路徑綜合代價先降低后不變。因此最終確定：種群規(guī)模為40，交叉概率為0.9，變異概率為0.1，最大迭代次數(shù)為120。

2.2 實例實驗

本模型采用多目標優(yōu)化-改進遺傳算法（multi-objective-improved genetic algorithm， M-IGA）。為了驗證改進算法和多目標優(yōu)化的性能以及二者組合后模型的整體性能，進行以下4組對比實驗：單目標-改進遺傳算法（single-objective-improved genetic algorithm， S-IGA）與單目標-經典遺傳算法（single-objective-genetic algorithm， S-GA）；多目標-經典遺傳算法（multi-objective-genetic algorithm， M-GA）與單目標-經典遺傳算法（S-GA）；M-IGA與S-GA；M-IGA與多目標-蟻群算法（multi-objective-ant colony algorithm， M-ACA）。每組實驗選取曼徹斯特局部路網(wǎng)上5個起終點（origin destination，OD）對，每個OD對分別做20次實驗，對比實驗結果見表4。由表4可知：

1）S-IGA與S-GA

相比于S-GA，S-IGA的算法運行時間平均增加了14.809 8%，最優(yōu)路徑綜合代價平均降低了12.575 0%。

2）M-GA與S-GA

相比于S-GA，M-GA的算法運行時間平均增加了3.807 4%，最優(yōu)路徑綜合代價平均降低了21.390 2%。

3）M-IGA與S-GA

相比于S-GA，M-IGA的算法運行時間平均增加了21.182 2%，最優(yōu)路徑綜合代價平均降低了23.609 1%。

4）M-IGA與M-ACA

相比于M-ACA，M-IGA的算法運行時間平均減少了54.322 0%，最優(yōu)路徑綜合代價平均降低了26.589 4%。

2.3 結果分析

S-IGA與S-GA對比實驗結果顯示，改進的遺傳算法可以有效降低收斂后的路徑綜合代價。經分析可知：本文設計的Dijkstra算法改進的半隨機方式種群初始化策略、基于鄰接矩陣的深度優(yōu)先遍歷交叉策略和鄰接限制半隨機變異策略，可以保證進化向最優(yōu)推進而并非隨機發(fā)散式無效迭代，同時避免算法陷入局部最優(yōu)解，使改進后的算法全局優(yōu)化出綜合代價更低的路徑。

M-GA與S-GA對比實驗結果顯示，引進偏好權重系數(shù)的多目標優(yōu)化可以有效改善經典遺傳算法的收斂結果。經分析可知：本文在選擇操作的適應度函數(shù)設計中引入平均行駛時間、交叉口延誤、道路擁擠狀況、道路等級的偏好權重系數(shù)，可以有效為用戶避開擁堵、交叉口多的路徑，使得路徑規(guī)劃結果更符合用戶預期。

M-IGA與S-GA以及M-ACA的對比實驗結果表明，本文設計的多目標優(yōu)化-改進遺傳算法組合模型，雖然犧牲了少部分算法運行效率，但是模型規(guī)劃出的最優(yōu)路徑的綜合代價大大降低，減少了3～6 min。與經典遺傳算法縱向比較，最優(yōu)路徑綜合代價降低了23.609 1%；與多目標蟻群算法橫向比較，最優(yōu)路徑綜合代價降低了26.589 4%。

3 結論

本文針對經典遺傳算法路徑規(guī)劃的弊端，分別進行了改進算法、模型多目標優(yōu)化兩方面的研究：

1）Dijkstra算法改進的半隨機方式種群初始化策略，100%規(guī)避了斷路、回頭路的產生，提高了初始種群質量；基于鄰接矩陣的深度優(yōu)先遍歷交叉策略，在完全避免斷路、回頭路產生的同時，保證交叉后子代適應度值優(yōu)于父代，提高交叉操作全局尋優(yōu)能力；鄰接限制半隨機變異策略，在不破壞群體池內優(yōu)秀個體基因的基礎上，維持種群多樣性，防止早熟收斂。

2）在適應度函數(shù)設計時引入偏好權重系數(shù)，對模型進行多目標優(yōu)化。用戶可根據(jù)習慣偏好，在模型的輸入中設置平均行駛時間、交叉口延誤、道路擁擠狀況、道路等級的重要程度排序。實驗結果表明，最優(yōu)路徑的綜合代價相比于單目標減少了23.609 1%，模型可以按需避開交叉口多、擁堵的路段，得到更符合用戶期望的路徑規(guī)劃結果。

參考文獻：

[1]《中國公路學報》編輯部. 中國交通工程學術研究綜述·2016［J］. 中國公路學報， 2016， 29（6）： 1-161.

［2］ HUANG H C， CHEN J Y， SUN R， et al. Short-term traffic prediction based on time series decomposition［J］. Physica A， 2022， 585： 126441.1-126441.15.

［3］ 詹軍. 我國城市交通擁堵問題及治理對策［J］. 關東學刊， 2016（2）： 45-53.

［4］ LIN C， HAN G J， DU J X， et al. Spatiotemporal Congestion-Aware Path Planning Toward Intelligent Transportation Systems in Software-Defined Smart City IoT［J］. IEEE Internet of Things Journal， 2020， 7（9）： 8012-8024.

［5］ 溫正， 孫華克. MATLAB智能算法［M］. 北京： 清華大學出版社， 2017： 145-152.

［6］ WANG Q Y， XU L H， QIU J D. Research and realization of the optimal path algorithm with complex traffic regulations in GIS［C］// International Conference on Automation and Logistics. Piscataway： IEEE， 2007： 516-520.

［7］ LIANG W， ZHANG Y， HU J M， et al. A Personalized route guidance approach for urban travelling and parking to a shopping mall［C］// 4th International Conference on Transportation Information and Safety. Piscataway： IEEE， 2017： 319-324.

［8］ 吳紅波， 王英杰， 楊肖肖. 基于Dijkstra算法優(yōu)化的城市交通路徑分析［J］. 北京交通大學學報， 2019， 43（4）： 116-121， 130.

［9］ RAHIMI-FARAHANI H， RASSAFI A A， MIRBAHA B. Forced-node route guidance system： incorporating both user equilibrium and system optimal benefits［J］. IET Intelligent Transport Systems， 2019， 13（12）： 1851-1859.

［10］ALPKOAK A， CETIN A. Safe map routing using heuristic algorithm based on regional crime rates ［C］// Artificial Intelligence and Applied Mathematics in Engineering Problems. Cham： Springer， 2020： 335-346.

［11］王寧， 胡大偉， 徐杰， 等. 基于客戶價值和滿意度的城市冷鏈物流時變路徑問題［J］. 中國公路學報， 2021， 34（9）： 297-308.

［12］董小帥， 毛政元. 基于改進遺傳算法的動態(tài)路徑規(guī)劃研究［J］. 計算機工程與應用， 2018， 54（19）： 49-55.

［13］馬永杰， 云文霞. 遺傳算法研究進展［J］. 計算機應用研究， 2012， 29（4）： 1201-1206， 1210.

［14］于瑩瑩， 陳燕， 李桃迎. 改進的遺傳算法求解旅行商問題［J］. 控制與決策， 2014， 29（8）： 1483-1488.

［15］楊從銳， 錢謙， 王鋒， 等. 改進的自適應遺傳算法在函數(shù)優(yōu)化中的應用［J］. 計算機應用研究， 2018， 35（4）： 1042-1045.

［16］孔祥麗. 多影響因素下的導航路網(wǎng)數(shù)據(jù)路徑規(guī)劃研究［D］. 武漢： 武漢大學， 2018.

［17］蔣吳廷. 城市道路信號交叉口交通狀態(tài)判別方法研究［D］. 重慶： 重慶交通大學， 2020.

［18］石征華， 侯忠生. 城市快速路擁擠度判別方法研究［J］. 交通與計算機， 2006， 24（5）： 20-23.

［19］王潤澤. 基于實時位置服務的動態(tài)路徑規(guī)劃算法研究［D］. 蘭州： 蘭州交通大學， 2020.

［20］HIGHWAYS ENGLAND. Highways England network journey time and traffic flow data［DB/OL］.（2015-06-22）［2021-06-15］. http：//data.gov.uk/dataset/highways-england-network-journey-time-and-traffic-flow-data.

［21］陰炳成， 于守靜. 完整街道尺度下城市道路等級分類［C］// 2017年中國城市交通規(guī)劃年會論文集. 北京： 中國建筑工業(yè)出版社， 2017： 639-647.

（責任編輯：周曉南）

Path Planning Model Based on Multi-Objective Optimization

Improved Genetic Algorithm

SUN Rui， HUANG Haichao， HUO Xinting， CHEN Jingya*

（School of Civil Engineering and Transportation， Hohai University， Nanjing 210098， China）

Abstract：

Optimizing intelligent algorithm for path planning can effectively alleviate the problem of user travel congestion. The multi-objective optimization improved genetic algorithm combination model was designed. The Dijkstra algorithm was used to improve the population initialization strategy， which completely avoided the open circuit and loop， and improved the quality of the initial population. Taking into account the global search and local optimization ability of the algorithm， the depth-first traversal crossover strategy and adjacency -restricted semi random mutation strategy based on adjacency matrix were designed， so as to solve the problems of reduced population diversity and premature convergence. Meanwhile， the individual user preference weight coefficient was introduced in the design of the fitness function， and the four factors of average driving time， intersection delay， road congestion and road grade were comprehensively considered for multi-objective optimization to find the optimal path that meets the individual expectation for users. The results show that compared with ant colony algorithm， the path optimization efficiency of the model is improved by 54.322 0%; compared with single objective path optimization， the comprehensive cost of the optimal path is reduced by 23.609 1%， effectively avoiding congestion and multiple sections of intersections.

Key words：

multi-objective optimization; improved genetic algorithm; path planning; analytic hierarchy process

收稿日期：2022-01-11

基金項目：國家自然科學基金資助項目（52078190）

作者簡介：孫 睿（1998—），女，在讀碩士，研究方向：智能交通系統(tǒng)中的動態(tài)路徑規(guī)劃，E-mail：sunrui@hhu.edu.cn.

通訊作者：陳景雅，E-mail：13805151397@139.com.