面向智能交通系統(tǒng)的最優(yōu)路線規(guī)劃設計方法

摘" 要：交通擁堵已經成為城市化進程中必須要解決的問題之一。隨著智能交通系統(tǒng)的逐漸普及，基于車輛導航和定位系統(tǒng)的路徑規(guī)劃成為解決交通擁堵、提高通行效率的關鍵技術。該文首先介紹現階段常用的幾種路徑規(guī)劃算法，隨后分別概述車輛最優(yōu)行駛路徑的靜態(tài)規(guī)劃和動態(tài)規(guī)劃方法。通過搭建車輛路徑規(guī)劃仿真平臺，利用靜態(tài)路徑規(guī)劃數學模型，可以使用最短路徑查詢算法和詳略層快速查詢算法，為駕駛員規(guī)劃一條最優(yōu)路徑。創(chuàng)建動態(tài)規(guī)劃數學模型，則能幫助車輛主動避開有交通管制的路徑，進一步提升通行效率。實驗表明，使用基于車輛協(xié)調算法的動態(tài)路徑規(guī)劃，能夠減少智能交通網絡中擁堵道路數，從而提高整個智能交通系統(tǒng)的通行效率。

關鍵詞：智能交通系統(tǒng)；最優(yōu)路線規(guī)劃；車輛協(xié)調算法；地圖數據；行駛路徑

中圖分類號：U-9" " " " "文獻標志碼：A" " " " 文章編號：2095-2945（2023）16-0122-04

Abstract： Traffic congestion has become one of the problems that must be solved in the process of urbanization. With the popularization of intelligent transportation system， route planning based on vehicle navigation and positioning system has become a key technology to solve traffic congestion and improve traffic efficiency. This paper first introduces several algorithms for common path planning at present， and then summarizes the static planning and dynamic planning methods of optimal vehicle path respectively. By building the simulation platform of vehicle path planning and using the mathematical model of static path planning， the shortest path query algorithm and detail layer fast query algorithm can be used to plan an optimal path for drivers. The mathematical model of dynamic programming can help vehicles actively avoid the path with traffic control and further improve traffic efficiency. Experiments show that dynamic path planning based on vehicle coordination algorithm can reduce the number of congested roads in the intelligent transportation network， thus improving the traffic efficiency of the entire intelligent transportation system.

Keywords： intelligent transportation system; optimal route planning; vehicle coordination algorithm; map data; driving path

在智慧城市建設背景下，智能交通系統(tǒng)得到了廣泛應用。為提高通行效率、減少道路擁堵，必須要綜合運用物聯網、大數據、人工智能等技術，對車輛行駛過程中的路徑進行最優(yōu)規(guī)劃，從而幫助駕駛員挑選出用時最少、里程最短的路徑。根據車輛行駛方式的不同，可選擇的最優(yōu)路線規(guī)劃方式也有所差異。靜態(tài)規(guī)劃適用于互聯網無法及時獲取交通信息的情況，需要提前下載離線的電子地圖，然后利用車輛導航GIS系統(tǒng)根據車輛自身的位置進行路徑規(guī)劃；動態(tài)規(guī)劃適用于互聯網可以實時獲取道路交通信息的情況，路徑規(guī)劃系統(tǒng)會根據實時路況不斷調整和優(yōu)化路徑，以保證動態(tài)規(guī)劃路徑的最優(yōu)化。

1" 智能交通系統(tǒng)中最優(yōu)路線規(guī)劃的常用算法

現階段比較成熟的最優(yōu)路徑規(guī)劃算法有Dijkstra算法、A-Star算法、雙向規(guī)劃算法等。Dijkstra算法是通過遍歷智能交通網絡中所有節(jié)點的方式，求出起始點之間的最短路徑。雖然能夠規(guī)劃出最優(yōu)路徑，但是效率較低，不適合路況較為復雜的智能交通系統(tǒng)。雙向搜索算法是按照“從起點搜索目標點”和“從目標點反向搜索起點”的方式，雙向同步進行搜索，直到搜索結果重合，從而確定最優(yōu)路徑。但是規(guī)劃路徑中容易出現部分重疊的情況，因此規(guī)劃路徑并不能保證做到全局最優(yōu)。A-Star算法是靜態(tài)路網中最有效的一種搜索方法，算法公式為

X（n）=Y（n）+Z（n），（1）

式中：X（n）表示車輛從起點到終點的最小距離；Y（n）表示車輛從起點到路徑中任意一點n點的最小距離；Z（n）表示從n點到終點的最小距離。

2" 車輛最優(yōu)行駛路徑靜態(tài)規(guī)劃的設計方法

2.1" 搭建車輛路徑規(guī)劃仿真平臺

最優(yōu)行駛路徑靜態(tài)規(guī)劃是提前將靜態(tài)地圖數據存儲到車輛的車載系統(tǒng)中，對道路路口始末節(jié)點進行查詢并作出線路規(guī)劃的一種路徑方法，常用的路徑規(guī)劃算法有Dijkstta算法、A-Star算法等。本文使用GIS軟件搭建了車輛路徑規(guī)劃仿真平臺，并應用A-Star算法查詢電子地圖中的相關信息，實現路徑規(guī)劃。仿真平臺的軟件結構如圖1所示。

車輛導航GIS仿真系統(tǒng)可支持地圖輸出、地圖顯示、地圖庫管理和空間查詢等多項功能。其中，地圖顯示部分又包括了圖標顯示、地圖漫游、地圖縮放等子功能；空間查詢部分又包括了節(jié)點查詢、路段查詢、路徑規(guī)劃和距離測算等功能[1]。

2.2" 建立靜態(tài)路徑規(guī)劃數學模型

在智能交通系統(tǒng)中，可以為每條道路賦予一個權值，賦值時考慮的因素有任意2條路徑的空間距離、車輛經過該道路耗費的時間等，用Q（F）表示權值，則存在以下關系

f{D（R）}=Q（F） ，（2）

式中：f表示空間拓撲結構相圖F的函數值，D（R）表示車輛行駛的路徑值。D（R）最小時，車輛整個行駛軌跡中始末道路路徑最短，此時為最優(yōu)路徑，在此基礎上建立路徑規(guī)劃最優(yōu)目標函數。假設車輛在智能交通網絡中從初始節(jié)點到達末端節(jié)點共有m條路徑，則路徑規(guī)劃最優(yōu)目標函數P可表示為

P=min{■D（Ri）}。（3）

2.3" 靜態(tài)路徑規(guī)劃算法設計

2.3.1" 最短路徑查詢算法

車輛駕駛人提前設定好初始路口節(jié)點和末端路口節(jié)點后，按照“從起點向終點”和“從終點向起點”雙向交替、同步進行的方式展開查詢。當2個方向的查詢狀態(tài)結果值與設定的規(guī)劃點重合時，則查詢結束。該查詢方法的優(yōu)勢在于顯著加快了路徑查詢效率，能夠在更短的時間內規(guī)劃出最優(yōu)路徑；不足之處是無法遍歷所有的路徑，因此最終規(guī)劃的路徑只能是局部最優(yōu)，而并非全局最優(yōu)。針對該問題，本文提出了以下解決方法：當正向查詢（從起點向終點）的路徑已經出現在反向查詢（從終點向起點）的查詢列表后，適當增加查詢步數；如果仍然未發(fā)現更加理想的路徑，則選擇當前最優(yōu)路徑；如果發(fā)現其他更加理想的路徑，則替換當前最優(yōu)路徑。

2.3.2" 詳略層快速查詢算法

在靜態(tài)路徑規(guī)劃中，需要對電子地圖中包含的所有道路進行分級。道路的級別越高，路徑越少，空間交通網絡圖越簡略；相反，道路的級別越低，路徑越多，空間交通網絡圖越詳細。在一些電子地圖中，還會將物理空間上相鄰并且方向一致的2條路徑，合并為一條虛擬道路，為最高圖層。級別較高的路徑，路口節(jié)點較少，有利于車輛的行駛。因此在車輛靜態(tài)路徑規(guī)劃時，會優(yōu)先選擇電子地圖上級別較高的圖層，更有利于達到路徑最短、行車時間最少的最優(yōu)目標值。本文研究的智能交通系統(tǒng)中道路數量較少，只劃分為2層，分別是以低等級道路為主的詳細層和以高等級道路為主的略圖層。在開展靜態(tài)路徑規(guī)劃時，從詳細層標定車輛的起點后，切換至略圖層查詢與之對應的綜合節(jié)點，并尋找兩者之間的最優(yōu)路徑；按照同樣的方法，尋找終點與綜合節(jié)點之間的最優(yōu)路徑。這里使用A-Star算法，對車輛行駛路徑上始末節(jié)點之間的歐氏距離進行迭代處理，有效避免了路徑重復疊加的情況，保證最終規(guī)劃的路徑為最優(yōu)路徑[2]。

3" 車輛最優(yōu)行駛路徑動態(tài)規(guī)劃的設計方法

3.1" 最優(yōu)路線規(guī)劃數學模型的建立

車輛最優(yōu)行駛路徑的動態(tài)規(guī)劃是智能交通系統(tǒng)研究的關鍵點之一。其實現方式是動態(tài)采集道路交通信息，并將該信息反饋至車載客戶端，達到根據實時路況信息不斷調整、優(yōu)化路徑的目的。車輛行駛路徑的動態(tài)規(guī)劃系統(tǒng)結構如圖2所示。

在該系統(tǒng)中，利用分布在智能交通網中的海量傳感器動態(tài)收集交通信息，計算機接受并處理交通信息后，依據交通信息的分析結果周期性更新車輛行駛過程中的道路情況。車輛駕駛員從車載客戶端設定了起點和終點后，智能交通網的控制中心結合當前的交通信息，在交通網地圖上標定起點和終點，并規(guī)劃兩者之間的最優(yōu)路徑。在智能交通系統(tǒng)中，根據車輛行駛方式的不同又可分為協(xié)調車輛和自主車輛2種。前者是指遵循交通規(guī)則行駛的車輛，后者是指基于人工智能可以實現自主行駛的車輛，需要分別建立相應的數學模型進行動態(tài)路徑規(guī)劃。

3.1.1" 協(xié)調車輛數學模型

創(chuàng)建協(xié)調車輛模型應滿足以下基本要求：①智能交通系統(tǒng)中，交通流量為均勻的線性分布；②智能交通系統(tǒng)的交通信息流，可以同步地反饋至控制中心與車載客戶端；③智能交通系統(tǒng)中的各條路徑之間具有獨立相關性。假設車輛行駛的周期時間為T，在一個周期內車輛行駛的始末節(jié)點之間路徑數量為N，車輛在某個時刻（i）的速度為vi、所處的路徑為ri、所在位置為Pi，則協(xié)調車輛數學模型Ci可表示為

，（4）

式中：車輛在i時刻下的速度vi與多種因素有關，例如公路的寬度、同一時間公路上車輛的數量，以及路徑的長度等。在車輛行駛路徑的規(guī)劃中，道路抗阻（Tr）也是不可忽視的一個重要因素，表示的是車輛從起點到終點的平均行駛時間[3]。假設該路徑中無交通行駛量，則Tr=t0；設車輛的行駛量為V，公路運行能力值為C，則道路抗阻Tr的計算公式為

，（5）

式中：α和β均為系數值。

3.1.2" 自主車輛數學模型

要想讓車輛實現智能自主行駛，需要在獲取地理信息的基礎上，設定起點并規(guī)劃路徑；同時，在車輛智能自主行駛的過程中，還要不間斷地收集路徑信息和車輛位置信息，對路徑和車輛狀態(tài)進行動態(tài)調整，幫助車輛避開障礙并順利到達終點。同樣，設立自主車輛數學模型也必須滿足以下幾個條件：①傳感器在實時采集交通信息時，受到環(huán)境因素（如溫度、電磁干擾等）的影響，難免會產生一定的誤差，這類誤差產生的影響十分微小，不予考慮；②交通信息的更新頻率應當與道路交通信息變化需求一致；③傳感器采集到的交通信息，能夠同步傳輸到車載客戶端與路徑規(guī)劃系統(tǒng)。假設在時間周期T中傳感器采集到的交通信息為wi，交通網道路徑為G，則自主車輛數學模型Ai可表示為

Ai=R（G，wi）。（6）

考慮到在同一個時間周期內，智能交通網絡中的道路阻抗和交通信息是不變的，這種情況下可使用路徑靜態(tài)規(guī)劃算法。其中，道路阻抗（Tij）可根據道路長度（dj）和車流量速度（vij）求出，其表達式為

Tij=■，（7）

式中：vij可利用GPS求得。車輛利用車載GPS實現定位，并將車輛的實時位置標記到電子地圖中。車輛在i時刻的行駛速度，可以用整個路徑中車輛速度的平均值來近似表示。

3.2" 動態(tài)路徑規(guī)劃的實驗分析

3.2.1" 以周期為基礎的自主車輛實驗

實驗步驟為：①在電子地圖上標定處車輛行駛的始終點；②利用定時裝置，設定均等時間；③在實時獲取路況信息的基礎上，更新智能交通網絡中的道路抗阻；④利用車載GPS裝置，明確當前道路上車輛的行駛位置，以當前車輛所在位置為起點，重新規(guī)劃起點到終點的路徑。實驗結果如圖3、圖4所示。

圖3、4中，2個黑色三角形分別表示車輛形式的起點和終點，■表示該道路上發(fā)生了交通堵塞。圖3表示在交通信息尚未更新情況下規(guī)劃的車輛行駛路徑；圖4表示實時更新交通信息后，重新規(guī)劃的車輛形式路徑。對比可以發(fā)現，通過實時獲取交通信息，并動態(tài)規(guī)劃車輛行駛路徑，能夠繞開發(fā)生交通堵塞的原路徑，重新規(guī)劃一條距離最短、用時最少的新路徑，保障車輛以最優(yōu)路徑到達終點[4]。在本次實驗中，分別測試了第1～4個周期內自主車輛最優(yōu)路徑的提升效率，統(tǒng)計結果見表1。

根據表1可以發(fā)現，在第1個周期內，原規(guī)劃路徑用時與最優(yōu)路徑用時相等；而從第2個周期開始，車輛在最優(yōu)路徑下從起點到達終點的用時，開始低于原規(guī)劃路徑。在第4個周期時，車輛如果按照原規(guī)劃路徑，從起點到達終點需要花費3 682.14 ms；按照最優(yōu)路徑只需要花費3 452.38 ms，效率提升了6.24%。

3.2.2" 車輛協(xié)調算法與堵塞道路數的關聯性分析

當智能交通網絡中同時有多輛車提出路徑規(guī)劃申請時，部分路徑可能會出現重復的情況。當同一路徑在同一時刻有多輛汽車時會產生堵塞情況，從而導致通行效率降低?；趨f(xié)調車輛的多車中心路徑規(guī)劃采用價值函數幫助駕駛員避開交通擁堵路段，其實現方式為：當智能交通網絡中某條道路的車輛數持續(xù)增加，會提升道路抗阻，從而降低后續(xù)其他車輛選擇該路徑的概率，起到緩解擁堵的效果[5]。選擇不同的算法，對智能交通網絡道路堵塞情況的影響也存在差異。這里以基于協(xié)調算法的中心路徑導航和基于自主算法的自主路徑導航為例，對比不同車輛數下車輛的平均出行用時，結果如圖5所示。

由圖可知，當同一路徑中申請導航的車輛數目增加后，車輛通過當前道路的平均用時也會相應的增加，說明道路的擁堵程度在加重。這種情況下可以通過降低行駛速度的方式，或者是讓后續(xù)導航車輛避開此擁堵路段的方式解決擁堵問題。對比來看，基于協(xié)調算法的中心路徑導航在車輛數超過1 000輛時，車輛平均出行用時要低于自主導航。說明使用車輛協(xié)調算法，能夠降低智能交通網絡中堵塞道路數量，對改善交通狀況和實現路徑最優(yōu)規(guī)劃有積極幫助。

4" 結束語

隨著城市交通的日益復雜和車輛數量不斷增加，固定出行路徑帶來的交通堵塞問題也變得越來越嚴重。依托智能交通系統(tǒng)，可以幫助駕駛員根據實時路況信息科學規(guī)劃其他的出行路徑，減少通行時間、提高通行效率。本文研究表明，無論是基于車輛導航GIS平臺的行駛路徑靜態(tài)規(guī)劃，還是基于協(xié)調車輛數學模型的行駛路徑動態(tài)規(guī)劃，都可以幫助車輛避開交通管制或交通擁堵路段，在規(guī)劃最優(yōu)路線的基礎上，減少了車輛到達目的地的用時。

參考文獻：

[1] 王榮，藺陸洲，路鵬飛，等.北斗高精度智能交通系統(tǒng)的設計及測試[J].網絡空間安全，2020，11（4）：5-13.

[2] 喬翔宇，戴榮健，高劍，等.基于共享模式的網聯自動駕駛車輛路徑規(guī)劃研究[J].交通工程，2020，20（2）：73-78.

[3] 孫娟，陳韶鈺，張洪森.基于PLC的智能交通系統(tǒng)設計的研究[J].內蒙古科技與經濟，2021（3）：100-101，107.

[4] 孫環(huán).汽車組合電子導航儀的路徑智能規(guī)劃效果測評研究[J].自動化與儀器儀表，2021（2）：221-226.

[5] 徐維祥，岳垚.基于出行計劃的三維地圖的最優(yōu)路徑規(guī)劃方法[J].浙江大學學報（工學版），2022，56（8）：1542-1552.