智能交通路徑規(guī)劃算法研究綜述

盧東祥

(鹽城師范學(xué)院，江蘇 鹽城 224002)

隨著國(guó)家經(jīng)濟(jì)的發(fā)展和人民生活水平的提高，我國(guó)機(jī)動(dòng)車保有量呈現(xiàn)快速增長(zhǎng)的趨勢(shì)。交通擁堵與安全等問題也逐漸成為嚴(yán)重影響中大城市工作、生活及安全的重要因素之一。按照發(fā)達(dá)國(guó)家的交通發(fā)展規(guī)律和成功經(jīng)驗(yàn)，在考慮居民出行需求的前提下，解決交通的擁堵與安全問題主要依賴最新科技的應(yīng)用，即通過引入人工智能、大數(shù)據(jù)及導(dǎo)航等科學(xué)技術(shù)來有效地提高城市交通的路網(wǎng)利用效率。根據(jù)這一理念，先進(jìn)的信息技術(shù)、大數(shù)據(jù)、北斗導(dǎo)航與人工智能技術(shù)逐漸被綜合運(yùn)用于城市交通的管理過程中，為緩解城市交通壓力和提高居民出行效率提供了切實(shí)可行的解決思路，形成了具有高利用效率的智能交通解決方案。路徑規(guī)劃是車輛定位和導(dǎo)航系統(tǒng)的核心功能之一，可分為單車輛路徑規(guī)劃與多車輛路徑規(guī)劃，二者間相輔相成，共同促進(jìn)著智能交通系統(tǒng)的優(yōu)化和發(fā)展。

為進(jìn)一步提升城市交通的智能程度及利用率，國(guó)內(nèi)外學(xué)者提出了具有借鑒價(jià)值和推廣意義的研究。文獻(xiàn)[1]綜合利用蟻群算法(Ant Colony Optimization，ACO)與有限元，提出了具有較高性能的路徑選擇優(yōu)化算法。在蟻群算法的基礎(chǔ)上，文獻(xiàn)[2]提出了最短路徑規(guī)劃算法，但其效率與實(shí)時(shí)性仍有可提高的空間。文獻(xiàn)[3]系統(tǒng)總結(jié)了多種傳統(tǒng)的路徑規(guī)劃算法，包括A*算法(A-Star)、Floyd算法、Dijkstra算法及蟻群算法等，進(jìn)而提出多項(xiàng)路徑規(guī)劃算法的核心問題。在上述研究?jī)?nèi)容與成果的基礎(chǔ)上，本文詳細(xì)分析了智能交通的研究歷程，深入探討當(dāng)前路徑規(guī)劃算法研究所存在的問題，并展望了其未來發(fā)展的方向。

1 路徑規(guī)劃研究

在城市交通領(lǐng)域中，隨著基礎(chǔ)設(shè)施與計(jì)算軟件的快速發(fā)展，智能交通的路徑規(guī)劃算法逐漸由靜態(tài)轉(zhuǎn)化為動(dòng)態(tài)。通常而言，動(dòng)態(tài)路徑規(guī)劃算法的研究主要可分為實(shí)時(shí)性、并行性、控制系統(tǒng)及混合類型。

1.1 實(shí)時(shí)性

在早期研究中，靜態(tài)規(guī)劃算法是路徑規(guī)劃的主要研究?jī)?nèi)容，且產(chǎn)生了大量具有較高實(shí)用性的優(yōu)質(zhì)算法。然而在交通基礎(chǔ)設(shè)施快速改善及優(yōu)化的背景下，路況信息和交通現(xiàn)狀隨時(shí)有可能發(fā)生劇烈的變化。換言之，路徑規(guī)劃算法的權(quán)值必須及時(shí)按照當(dāng)前的路況進(jìn)行必要的調(diào)整，這便對(duì)路徑規(guī)劃算法提出了較高的實(shí)時(shí)性要求。

1.2 并行性

隨著城市機(jī)動(dòng)車保有量的逐漸增加，道路交通擁堵信息量也呈現(xiàn)出指數(shù)級(jí)的增長(zhǎng)，這導(dǎo)致規(guī)劃算法需考慮海量的數(shù)據(jù)與信息因素。但當(dāng)前利用集中式串行性計(jì)算方法的設(shè)備難以處理規(guī)模龐大數(shù)據(jù)，這意味著利用并行性計(jì)算模式的規(guī)劃算法將成為路徑規(guī)劃研究的重要方向。

1.3 控制系統(tǒng)

在大數(shù)據(jù)逐漸普及的背景下，智能交通需引入全方位的控制系統(tǒng)，才能夠進(jìn)一步提高其實(shí)際利用率。通常而言，智能交通中控制系統(tǒng)需制定交通流量的智能分配策略，包括交通信號(hào)燈的智能化控制、車輛轉(zhuǎn)向延誤和導(dǎo)航系統(tǒng)的更新等多種問題。但當(dāng)前該系統(tǒng)的研究仍處于起步階段，存在較大的提升和優(yōu)化空間。

1.4 混合類型

在智能交通研究中，多種傳統(tǒng)規(guī)劃算法具有明顯的優(yōu)勢(shì)，例如Dijkstra算法、Floyd算法及A*算法等，均已在路徑規(guī)劃領(lǐng)域得到了廣泛的普及與應(yīng)用。然而，這些優(yōu)異的算法各自存在著不可忽視的缺點(diǎn)：Dijkstra算法的運(yùn)行和實(shí)現(xiàn)速度較快，但其無(wú)法處理負(fù)權(quán)值；而Floyd算法可輕松計(jì)算節(jié)點(diǎn)間的最短距離，但其算法的時(shí)間復(fù)雜度較高，難以適應(yīng)海量數(shù)據(jù)的計(jì)算；A*算法則融合Dijkstra算法及最佳優(yōu)先算法(Best FS)的優(yōu)點(diǎn)，但該算法不一定能獲取最優(yōu)解?？傊?，綜合利用傳統(tǒng)路徑規(guī)劃、深度學(xué)習(xí)(Deep Learning，DL)、人臉識(shí)別與圖形拼接等多種算法，逐漸成為了路徑規(guī)劃研究的重要發(fā)展方向。

2 智能算法

人工智能的快速發(fā)展為計(jì)算機(jī)技術(shù)的研究引入了生物學(xué)啟發(fā)式計(jì)算?；谶@一現(xiàn)狀，具有隨機(jī)性、通用性和特定性的智能算法被應(yīng)用于路徑規(guī)劃的研究中，并逐漸獲得了廣泛關(guān)注。

2.1 蟻群算法

20世紀(jì)90年代，文獻(xiàn)[4～5]通過觀察螞蟻覓食的行為，首次提出了蟻群系統(tǒng)理論，以嘗試解決經(jīng)典的旅行商問題，得到了具有較高質(zhì)量的結(jié)果。

基于通用蟻群算法，國(guó)內(nèi)眾多學(xué)者均曾嘗試在路徑規(guī)劃研究中引入蟻群算法，并做出了一些值得借鑒的成果。文獻(xiàn)[6]在蟻群算法的基礎(chǔ)上，制定了最近鄰居策略及目標(biāo)引導(dǎo)函數(shù)，從而較好地解決了復(fù)雜地理環(huán)境下機(jī)器人的最優(yōu)路徑規(guī)劃問題。文獻(xiàn)[7]通過修改目標(biāo)引導(dǎo)函數(shù)，進(jìn)一步提高了蟻群算法的收斂速度，進(jìn)而充分改進(jìn)并優(yōu)化了移動(dòng)機(jī)器人的動(dòng)態(tài)路徑規(guī)劃問題。文獻(xiàn)[8]利用蟻群數(shù)量、啟發(fā)因子與信息素?fù)]發(fā)系統(tǒng)等參數(shù)調(diào)整的方法，對(duì)不同環(huán)境下的移動(dòng)機(jī)器人進(jìn)行了全局性仿真實(shí)驗(yàn)，并獲得了全面的最佳匹配參數(shù)。以上工作的研究對(duì)象主要是具有移動(dòng)功能的機(jī)器人，但其研究結(jié)果仍對(duì)智能交通的路徑規(guī)劃算法具有較高的實(shí)用性與可移植性。

此外，在同一時(shí)期內(nèi)，諸多國(guó)外學(xué)者也通過蟻群算法及其改進(jìn)算法，做出一系列具有較高參考意義的工作。文獻(xiàn)[9]首次將強(qiáng)化蟻群算法應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃問題中，對(duì)包含約束條件的連續(xù)函數(shù)優(yōu)化問題提出了有效的解決思路，并進(jìn)一步促進(jìn)了特定條件下路徑規(guī)劃算法的改進(jìn)與求解。文獻(xiàn)[10]充分地考慮城市交通的負(fù)荷，提出了基于蟻群優(yōu)化技術(shù)的最短路徑規(guī)劃算法。該算法在提高性能的同時(shí)，還兼顧了算法的性能及靈活性。文獻(xiàn)[11]分別考慮車輛路徑規(guī)劃和商品配送問題，提出了救災(zāi)場(chǎng)景下基于蟻群算法的商品和車輛路徑規(guī)劃問題。該算法的運(yùn)行效率和執(zhí)行結(jié)果均達(dá)到了較為優(yōu)秀的狀態(tài)。文獻(xiàn)[12]證明了有向無(wú)環(huán)圖上單目標(biāo)最短路徑問題的蟻群優(yōu)化算法多項(xiàng)式運(yùn)行時(shí)間界，并首次從算法理論角度對(duì)蟻群算法的性能與運(yùn)行效率給出了精確的評(píng)估。文獻(xiàn)[13]通過擴(kuò)展容量約束車輛路徑問題，提出帶回程的車輛路徑問題，并利用改進(jìn)蟻群算法實(shí)現(xiàn)了該問題的組合優(yōu)化，具有較強(qiáng)的實(shí)用性與有效性。文獻(xiàn)[14]在啟發(fā)式蟻群算法的基礎(chǔ)上，設(shè)計(jì)出具有應(yīng)急疏散功能的多目標(biāo)優(yōu)化模型，解決了緊急情況下大型公共建筑撤離過程中的路徑規(guī)劃問題，并填補(bǔ)了這一應(yīng)用領(lǐng)域的研究空白。文獻(xiàn)[15]通過重新設(shè)置全局更新規(guī)則、干擾因子和信息素更新算子，提出了基于改進(jìn)蟻群算法的道路權(quán)重模型，從而為城市交通中的機(jī)動(dòng)車輛規(guī)劃更優(yōu)的出行路線。文獻(xiàn)[16]通過引入實(shí)時(shí)性的物聯(lián)網(wǎng)技術(shù)，以較大的幅度改進(jìn)了蟻群算法的性能及效率，從而進(jìn)一步實(shí)現(xiàn)了對(duì)導(dǎo)航系統(tǒng)中車輛路徑規(guī)劃的優(yōu)化。文獻(xiàn)[17]對(duì)比了蟻群算法和遺傳算法(Genetic Algorithm，GA)在路徑規(guī)劃問題中的應(yīng)用，并實(shí)現(xiàn)了此類算法中多項(xiàng)參數(shù)的調(diào)試與優(yōu)化，從而給出了適用于云計(jì)算的分布式計(jì)算方法。文獻(xiàn)[18]基于改進(jìn)蟻群算法，提出了考慮信息反饋的車輛路徑規(guī)劃算法，并在垃圾運(yùn)輸和收集系統(tǒng)中得到了成功的應(yīng)用。2017年，文獻(xiàn)[19]通過調(diào)整算法步驟和結(jié)構(gòu)，提出了基于改進(jìn)蟻群算法的多目標(biāo)優(yōu)化調(diào)度模型，進(jìn)而解決了路徑規(guī)劃問題在云計(jì)算時(shí)代的任務(wù)調(diào)度方法。2019年，文獻(xiàn)[20]在改進(jìn)蟻群算法的基礎(chǔ)上，通過結(jié)合K-means算法(K-means Clustering Algorithm)與支持向量機(jī)技術(shù)，建立了智能交通中高速列車的無(wú)線定位模型。2020年，文獻(xiàn)[21]提出了一種基于網(wǎng)格的交通網(wǎng)絡(luò)擁擠概率量化模型。同時(shí)給出多項(xiàng)式時(shí)間之內(nèi)的路徑規(guī)劃算法，從而實(shí)現(xiàn)了智能交通系統(tǒng)中的流量調(diào)節(jié)和調(diào)度。2021年，文獻(xiàn)[22]提出了一種基于成對(duì)鄰近學(xué)習(xí)的蟻群算法，通過利用用戶節(jié)點(diǎn)間的接近程度，跟蹤機(jī)動(dòng)車輛的動(dòng)態(tài)變化，實(shí)現(xiàn)了動(dòng)態(tài)車輛路徑規(guī)劃問題的求解。

2.2 遺傳算法

20世紀(jì)60年代，受生物遺傳中變異、交叉和選擇等行為的啟發(fā)，文獻(xiàn)[23～25]總結(jié)并提出了遺傳算法。由此，該算法逐漸被應(yīng)用于組合優(yōu)化、圖像處理及機(jī)器學(xué)習(xí)等諸多領(lǐng)域內(nèi)。

2000年，文獻(xiàn)[26]首次在模糊控制與導(dǎo)航系統(tǒng)中引入了通用遺傳算法，并獲取了優(yōu)于隨機(jī)決策表的規(guī)劃路徑。2001年，文獻(xiàn)[27]汽車和運(yùn)輸技術(shù)大會(huì)上，利用常見的遺傳算法，提出了智能交通系統(tǒng)中的路徑優(yōu)化方法，且從算法理論方向證明了遺傳算法在路徑規(guī)劃研究中的重要作用，具有較強(qiáng)的原創(chuàng)性。在文獻(xiàn)[26～27]的啟發(fā)下，眾多研究者開始考察遺傳算法在路徑規(guī)劃研究中的應(yīng)用。文獻(xiàn)[28]有機(jī)結(jié)合禁忌搜索算法(Tabu Search)和遺傳算法的優(yōu)點(diǎn)，提出了具有智能化特征的混合遺傳算法。該算法有效改善了公交車輛的動(dòng)態(tài)運(yùn)營(yíng)決策效率，提升了服務(wù)質(zhì)量。文獻(xiàn)[29]在地理信息系統(tǒng)的基礎(chǔ)上，通過引入遺傳算法，增強(qiáng)了算法求解的隨機(jī)性，并以更大概率接近復(fù)雜規(guī)劃問題的最優(yōu)解，改善了公路線性優(yōu)化最終解的質(zhì)量。文獻(xiàn)[30]在機(jī)器學(xué)習(xí)及控制論的國(guó)際會(huì)議上，利用遺傳算法和人工智能技術(shù)，提出了城市公共交通系統(tǒng)的調(diào)度算法與執(zhí)行程序。該研究致力于提高公交系統(tǒng)的運(yùn)行效率，具有非常強(qiáng)的前瞻性與參考性。文獻(xiàn)[31]通過引入U(xiǎn)MTS技術(shù)，提出了基于遺傳算法的城市軌道交通優(yōu)化網(wǎng)絡(luò)規(guī)劃設(shè)計(jì)工具，實(shí)現(xiàn)了路徑規(guī)劃與信號(hào)傳輸?shù)耐皆O(shè)計(jì)和優(yōu)化。在文獻(xiàn)[30]的基礎(chǔ)上，文獻(xiàn)[32]綜合利用有向圖理論和遺傳算法，提出了滿足時(shí)間、成本及任務(wù)分配要求的路徑規(guī)劃算法，從而實(shí)現(xiàn)了路徑規(guī)劃問題的全新解決思路。與傳統(tǒng)基于圖的算法相比，文獻(xiàn)[32]中的算法具有更為簡(jiǎn)單的實(shí)現(xiàn)方法和更高的效率。在同一時(shí)期，文獻(xiàn)[33]在進(jìn)化計(jì)算會(huì)議上，基于遺傳算法的主要計(jì)算步驟，利用增加進(jìn)化算子及更新表示環(huán)境的方法，提出了適用于靜態(tài)和動(dòng)態(tài)障礙物環(huán)境的分布路徑規(guī)劃算法。其進(jìn)一步優(yōu)化了路徑規(guī)劃算法的計(jì)算速度與魯棒性能。此后，學(xué)界對(duì)于路徑規(guī)劃算法的研究進(jìn)入高峰。文獻(xiàn)[34]通過修改編碼、交叉和變異等計(jì)算步驟，得到了適用于最優(yōu)路徑規(guī)劃的改進(jìn)遺傳算法，為圖論中最短路徑問題提供了切實(shí)可行的解決方法，具有較高的學(xué)術(shù)價(jià)值及參考意義。文獻(xiàn)[35]在地理空間信息系統(tǒng)中引入啟發(fā)式的遺傳算法，提出了具有并行計(jì)算功能的改進(jìn)遺傳算法，為路徑規(guī)劃問題的快速求解提供了一定的參考。此外，文獻(xiàn)[36]通過改變遺傳算法的計(jì)算方法和步驟，在智能運(yùn)輸系統(tǒng)中提出了具有自適應(yīng)功能的平滑參數(shù)概率神經(jīng)網(wǎng)絡(luò)算法。該算法提供了企業(yè)級(jí)的解決方案，進(jìn)一步提高了智能交通系統(tǒng)的利用率，并具有較強(qiáng)的實(shí)用性。在小型手持計(jì)算設(shè)備的快速發(fā)展背景下，文獻(xiàn)[37]提出基于遺傳算法的路線引導(dǎo)系統(tǒng)，其魯棒性、準(zhǔn)確性與計(jì)算效率均達(dá)到了較高水平。文獻(xiàn)[38]在可行解空間中引入全局采樣功能，并在遺傳算法中融合傳統(tǒng)的Dijkstra算法和A*算法，從而給出了具有決策功能的路徑規(guī)劃算法。在2010～2016年間，大多數(shù)學(xué)者的關(guān)注點(diǎn)逐漸轉(zhuǎn)移至路徑規(guī)劃算法的系統(tǒng)性與實(shí)時(shí)性。文獻(xiàn)[39～41]重點(diǎn)對(duì)智能交通系統(tǒng)中的路徑規(guī)劃算法進(jìn)行了系統(tǒng)化的改造，掃除了遺傳算法在地理空間信息系統(tǒng)中的實(shí)用性障礙。文獻(xiàn)[42]則著重提高了智能交通系統(tǒng)中遺傳算法的計(jì)算速度與效率，優(yōu)化了路徑規(guī)劃算法的實(shí)時(shí)性。2017年后，在大數(shù)據(jù)、云計(jì)算和人工智能技術(shù)快速發(fā)展的背景下，由于算法效果的優(yōu)化空間不斷減少，路徑規(guī)劃算法的研究成果數(shù)量呈現(xiàn)了下降趨勢(shì)，但仍出現(xiàn)不少值得借鑒的研究成果。文獻(xiàn)[43]提出了基于改進(jìn)遺傳算法的車輛導(dǎo)航系統(tǒng)多目標(biāo)規(guī)劃算法，大幅縮短了機(jī)動(dòng)車輛的路徑距離。文獻(xiàn)[44]通過開發(fā)遺傳算法的框架，對(duì)高速公路的擁擠情況及行程時(shí)間做出較為精確的校準(zhǔn)和評(píng)估。文獻(xiàn)[45]在無(wú)線傳感器網(wǎng)絡(luò)中引入自適應(yīng)克隆遺傳算法，有效提高了算法的全局搜索能力，為復(fù)雜的交通環(huán)境提供一種有效的任務(wù)分配策略，并進(jìn)一步提升了物聯(lián)網(wǎng)時(shí)代下智能交通的通行效率。

3 結(jié)束語(yǔ)

針對(duì)復(fù)雜交通環(huán)境中的路徑規(guī)劃問題，本文從實(shí)時(shí)性、并行性、控制系統(tǒng)及混合算法等研究方向出發(fā)，深入研究和分析了基于蟻群算法與遺傳算法的路徑規(guī)劃算法研究歷程和發(fā)展脈絡(luò)。由本文的總結(jié)和分析可知：

(1)利用蟻群和遺傳算法的路徑規(guī)劃研究已獲得較為豐富的成果，但大多數(shù)成果的做法為通過修改啟發(fā)式算法的細(xì)節(jié)或參數(shù)，來實(shí)現(xiàn)對(duì)算法效果的優(yōu)化，這樣的研究思路難以進(jìn)行深入的研究；

(2)在物聯(lián)網(wǎng)及人工智能等多種新型技術(shù)普及的背景下，路徑規(guī)劃研究面臨著更加復(fù)雜的應(yīng)用環(huán)境及運(yùn)行條件。然而，如何修改啟發(fā)式算法以適應(yīng)多種新型技術(shù)的快速發(fā)展，仍是該領(lǐng)域的重要課題之一，其研究進(jìn)展對(duì)于國(guó)家的現(xiàn)代化建設(shè)具有重要的理論意義和應(yīng)用價(jià)值。