多目標(biāo)優(yōu)化-改進(jìn)遺傳算法路徑規(guī)劃模型

孫睿 黃海超 霍欣婷 陳景雅

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

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

中圖分類號(hào)：U491

文獻(xiàn)標(biāo)志碼：A

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

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

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

1 模型構(gòu)建

1.1 算法編碼

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

1.2 初始種群的選取

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

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

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

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

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

Step4 如果當(dāng)前節(jié)點(diǎn)已無未標(biāo)記的連通節(jié)點(diǎn)，則退回上一節(jié)點(diǎn)重新選擇；

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

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

1.3 適應(yīng)度函數(shù)的構(gòu)造

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

1.3.1 4種因素的權(quán)重系數(shù)計(jì)算

1）構(gòu)建判斷矩陣

在用戶現(xiàn)實(shí)選擇時(shí)，經(jīng)典9種標(biāo)度可能會(huì)因?yàn)橹匾詤^(qū)分不明顯而產(chǎn)生困擾，故模型采用簡化后的3種標(biāo)度，規(guī)定如表1所示。

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

用和法計(jì)算D1影響因素權(quán)重：

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

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

=0.576 9

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

2）一致性檢驗(yàn)：

λ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為影響因素個(gè)數(shù)；dij為判斷矩陣中因素i對因素j的比重；wj、wi分別為影響因素j、i的權(quán)重；CI為一致性指標(biāo)；CR為檢驗(yàn)系數(shù)；RI為隨機(jī)一致性指標(biāo)，判斷矩陣階數(shù)為4時(shí)取值為0.90。

判斷矩陣通過一致性檢驗(yàn)。

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

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

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

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

2）道路等級(jí)

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

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

1.3.3 適應(yīng)度函數(shù)計(jì)算

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

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

1.4 遺傳操作的改進(jìn)

1.4.1 選擇操作

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

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

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

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

1.4.2 交叉操作

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

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

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

Step3 按照鄰接矩陣在個(gè)體I2中查找所有與m1鄰接的點(diǎn)，計(jì)算m1與各鄰接點(diǎn)的平均行駛時(shí)間，選擇最小值對應(yīng)的鄰接點(diǎn)作為個(gè)體I2中的待交叉點(diǎn)。若個(gè)體I2中沒有與m1連通的鄰接點(diǎn)，則返回Step2重新選取待交叉點(diǎn)。

Step4 父代個(gè)體I1，I2分別在各自待交叉點(diǎn)斷開，交換前后基因，產(chǎn)生2個(gè)子代個(gè)體N1，N2。

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

Step6 重復(fù)Step1—Step5，直至交叉操作結(jié)束。

1.4.3 變異操作

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

Step1 對群體池中個(gè)體按事先設(shè)定的變異概率pm判斷是否要進(jìn)行變異。

Step2 在變異個(gè)體中隨機(jī)選擇除起、終點(diǎn)外的基因位置作為待變異點(diǎn)，d為待變異點(diǎn)在該個(gè)體中的基因位置序號(hào)。

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

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

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

Step6 若該個(gè)體中始終沒有符合要求的待變異點(diǎn)，則返回Step1，進(jìn)行下一個(gè)體是否需要變異的判斷。

2 實(shí)例應(yīng)用

2.1 模型參數(shù)選取

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

2.2 實(shí)例實(shí)驗(yàn)

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

1）S-IGA與S-GA

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

2）M-GA與S-GA

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

3）M-IGA與S-GA

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

4）M-IGA與M-ACA

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

2.3 結(jié)果分析

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

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

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

3 結(jié)論

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

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

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

參考文獻(xiàn)：

[1]《中國公路學(xué)報(bào)》編輯部. 中國交通工程學(xué)術(shù)研究綜述·2016［J］. 中國公路學(xué)報(bào)， 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］. 關(guān)東學(xué)刊， 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］. 北京： 清華大學(xué)出版社， 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］. 北京交通大學(xué)學(xué)報(bào)， 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］王寧， 胡大偉， 徐杰， 等. 基于客戶價(jià)值和滿意度的城市冷鏈物流時(shí)變路徑問題［J］. 中國公路學(xué)報(bào)， 2021， 34（9）： 297-308.

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

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

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

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

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

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

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

［19］王潤澤. 基于實(shí)時(shí)位置服務(wù)的動(dòng)態(tài)路徑規(guī)劃算法研究［D］. 蘭州： 蘭州交通大學(xué)， 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］陰炳成， 于守靜. 完整街道尺度下城市道路等級(jí)分類［C］// 2017年中國城市交通規(guī)劃年會(huì)論文集. 北京： 中國建筑工業(yè)出版社， 2017： 639-647.

（責(zé)任編輯：周曉南）

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

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（52078190）

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

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