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

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

中圖分類號(hào)：U-9" " " " "文獻(xiàn)標(biāo)志碼：A" " " " 文章編號(hào)：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

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

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

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

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

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

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

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

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

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

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

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

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

式中：f表示空間拓?fù)浣Y(jié)構(gòu)相圖F的函數(shù)值，D（R）表示車輛行駛的路徑值。D（R）最小時(shí)，車輛整個(gè)行駛軌跡中始末道路路徑最短，此時(shí)為最優(yōu)路徑，在此基礎(chǔ)上建立路徑規(guī)劃最優(yōu)目標(biāo)函數(shù)。假設(shè)車輛在智能交通網(wǎng)絡(luò)中從初始節(jié)點(diǎn)到達(dá)末端節(jié)點(diǎn)共有m條路徑，則路徑規(guī)劃最優(yōu)目標(biāo)函數(shù)P可表示為

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

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

2.3.1" 最短路徑查詢算法

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

2.3.2" 詳略層快速查詢算法

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

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

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

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

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

3.1.1" 協(xié)調(diào)車輛數(shù)學(xué)模型

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

，（4）

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

，（5）

式中：α和β均為系數(shù)值。

3.1.2" 自主車輛數(shù)學(xué)模型

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

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

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

Tij=■，（7）

式中：vij可利用GPS求得。車輛利用車載GPS實(shí)現(xiàn)定位，并將車輛的實(shí)時(shí)位置標(biāo)記到電子地圖中。車輛在i時(shí)刻的行駛速度，可以用整個(gè)路徑中車輛速度的平均值來(lái)近似表示。

3.2" 動(dòng)態(tài)路徑規(guī)劃的實(shí)驗(yàn)分析

3.2.1" 以周期為基礎(chǔ)的自主車輛實(shí)驗(yàn)

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

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

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

3.2.2" 車輛協(xié)調(diào)算法與堵塞道路數(shù)的關(guān)聯(lián)性分析

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

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

4" 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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