黎萬洪，胡明輝,b，陳 龍，饒 坤

(重慶大學 a.汽車工程學院；b.機械傳動國家重點實驗室, 重慶 400044)

路徑規(guī)劃作為智能汽車的決策層，對于提高駕駛人出行效率、緩解城市擁堵具有重要作用。起訖點行程時間是人們出行普遍較為關心之處，因此也成為了路徑規(guī)劃的首要需求[1]，其評價指標是路段行程時間的累加值。根據(jù)路段行程時間是否變化，可以將路徑規(guī)劃劃分為靜態(tài)路徑規(guī)劃(static path planning，SPP)和滾動路徑規(guī)劃(rolling path planning，RPP)。

SPP主要研究起訖點的累積最小權值，如最短路程或最短靜態(tài)行程時間，較經(jīng)典的研究方法有Dijkstra算法、A*算法、蟻群算法等[2]，但都各有缺陷。近年來，國內外學者針對上述算法提出了對應的改進策略，以提高算法的運行效率和規(guī)劃精度。如針對A*算法易陷入局部最優(yōu)、搜索速度較慢的缺陷，顧青等[3]設計了新的啟發(fā)式估計能源成本函數(shù)以改善A*算法；Fu等[4]通過改進當前節(jié)點與目標節(jié)點的搜索策略提高了A*算法的搜索成功率；王維等[5]對估計路徑代價進行指數(shù)衰減的方式加權，使得A*算法自適應地搜索目標點。蟻群算法同樣存在收斂速度慢、容易陷入局部最優(yōu)的缺點，王志中等[6]提出了螞蟻相遇和螞蟻回退策略，并改進了信息素殘留方法。此外，文獻[7-8]也都對蟻群算法進行了相應的改進。A*算法、蟻群算法等都屬于智能啟發(fā)式算法，無論如何改進算法，其包含的隨機因子總有可能使路徑搜索陷入局部最優(yōu)，因而也就無法保證所得路徑是全局最優(yōu)解。盡管經(jīng)典的Dijkstra算法冗余度較高，但當前計算機技術和網(wǎng)絡通信技術的巨大發(fā)展有效地彌補了這一不足，考慮到該算法能保證找到全局最優(yōu)解，仍不失為一種較好的方法。

RPP伴隨著城市交通的發(fā)展而受到廣泛關注，主要研究交通信息的獲取及改進路徑搜索算法的性能。在獲取交通信息方面，Chai等[9]提出了自適應信號控制網(wǎng)絡中的動態(tài)交通路徑規(guī)劃策略；El-Wakeel等[10]提出了一種基于人群感知的動態(tài)路線規(guī)劃系統(tǒng)；李軍[11]提出通過預測道路未來時刻交通信息，不斷調用內嵌算法，從而實現(xiàn)了多階段的RPP；Zhao等[12]通過信息中心網(wǎng)絡中的大數(shù)據(jù)獲取和分析架構，不斷滾動規(guī)劃智能車的行駛路線。在改進路徑搜索算法隨機性方面，Tilk等[13]在有界雙向動態(tài)規(guī)劃約束的最短路徑問題求解變量加速技術的基礎上，引入動態(tài)中途點來減少最短路徑問題求解整體計算量。隨裕猛等[14]在分析A*和D*Lite算法的不足之后，提出了D*Lite Label算法。劉琳等[15]依托車聯(lián)網(wǎng)平臺，通過查找車輛當前位置節(jié)點實時獲取路網(wǎng)權值并進行動態(tài)路徑規(guī)劃。上述RPP的核心思想可以歸納為通過反復調用路徑規(guī)劃算法，不斷更新汽車行駛路線，因此汽車實際行駛路線是由多階段規(guī)劃的局部最優(yōu)路徑拼接而成，而局部最優(yōu)的疊加并不能推導出全局最優(yōu)。另外，文獻[16]詳細闡述了城市交通流具有周期相似性，文獻[17]研究了交通流與路段權值的定量關系，路段行程時間作為路段權值的一種評價指標，也順理成章地體現(xiàn)了周期相似性特征，這一研究成果為時變權值路網(wǎng)的全局最優(yōu)路徑規(guī)劃開辟了新穎的研究思路。

隨著人們對準時到達目的地、縮短出行時間的需求的日益增加，傳統(tǒng)的SPP和RPP方法已不再適用?；诖耍紫认到y(tǒng)分析了現(xiàn)有路徑規(guī)劃方法的不足之處，隨后推導了時變權值路網(wǎng)的臨界周期路段的實際權值，并基于Dijkstra算法提出了GOPP方法。在驗證經(jīng)典Dijkstra算法能實現(xiàn)全局最優(yōu)解和運算時間低的基礎上，分別利用SPP、RPP和GOPP三種方法規(guī)劃路徑。結果表明，GOPP可以實現(xiàn)時變權值路網(wǎng)的累積行程時間最小，該方法對于有效縮短交通出行時間和智能交通系統(tǒng)的發(fā)展具有一定的理論指導意義。

1 傳統(tǒng)路徑規(guī)劃的缺陷

為了引出GOPP算法，首先探討當前最常見的兩種路徑規(guī)劃方法的缺陷。如圖1所示是一個路段行程時間動態(tài)更新的示例路網(wǎng)，在時段1和時段2的路段行程時間如表1所示，兩個時段相鄰。假設當前車輛位于交叉口2，當前時刻t0處于時段1，目標交叉口為11，現(xiàn)探討起訖點為(2，11)的傳統(tǒng)路徑規(guī)劃方法。

圖1 示例路網(wǎng)及3種路徑規(guī)劃方法比較Fig. 1 Example road network and comparison of three path planning methods

表1 示例路網(wǎng)的時變路段行程時間

SPP只考慮路網(wǎng)當前時刻的權值，根據(jù)時段1的權值分布計算得到的最優(yōu)路徑為2→6→7→11，如圖1綠色路徑所示。現(xiàn)假設車輛到達交叉口6的時刻恰好是時段1和時段2的臨界時刻，路網(wǎng)權值隨即更新為時段2的權值。則車輛在經(jīng)過6→7→11時所耗費的行程時間應當參考時段2的權值分布，那么在時段1規(guī)劃的所謂“最優(yōu)路徑”也就無法證明在時段2是否繼續(xù)保持最優(yōu)。因此，SPP的路徑是特定時域(時段1)的最優(yōu)路徑，無法證明在全時域保持最優(yōu)。

考慮到SPP的缺陷，研究人員提出了RPP方法。參考SPP在交叉口2規(guī)劃的綠色路徑，當車輛到達交叉口6時，路網(wǎng)權值發(fā)生更新。此時RPP根據(jù)時段2的權值立即重新規(guī)劃剩余的道路網(wǎng)絡的路徑，計算發(fā)現(xiàn)黃色路線的累積權值小于綠色路線的累積權值，因此將行駛路線更改為黃色路線。RPP的兩次路徑規(guī)劃起點分別為交叉口1和交叉口6，對應的路徑分別為2→6和6→10→11，路徑規(guī)劃的空域顯然不同。因此，RPP的實際行駛路徑是由特定空域中的局部最優(yōu)路徑拼接而成的，局部最優(yōu)的疊加并非全局最優(yōu)，故RPP無法證明在全空域保持最優(yōu)。

實際上，根據(jù)表1的權值變化通過計算證明圖1的藍色路徑才是最優(yōu)路徑。為更加直觀地展示3種路徑規(guī)劃方式的區(qū)別，繪制了如圖2所示的起訖點直線距離變化示意圖。圖2中交叉口2和交叉口11的縱坐標之差表示兩個交叉口間的空間直線距離，車輛從交叉口2出發(fā)，隨時間推移到達交叉口11。其中，SPP_1表示車輛在交叉口2利用SPP方法規(guī)劃路徑計算得到的理想直線距離變化曲線，但由于車輛在交叉口6時路網(wǎng)權值更新，車輛繼續(xù)按照SPP路徑行駛的實際直線距離變化曲線如SPP_2所示。值得注意的是，藍色最優(yōu)路徑在時段1并未體現(xiàn)其優(yōu)勢，進入時段2卻率先到達了目標點。

圖2 起訖點直線距離變化示意圖Fig. 2 Schematic diagram of linear distance change between starting and ending points

以上示例展示了當前兩種常見路徑規(guī)劃方式的核心思想，由于其均無法實現(xiàn)全局最優(yōu)，因此有必要深刻分析圖1藍色最優(yōu)路徑的生成原理，探索一種新的求解復雜城市路網(wǎng)全局最優(yōu)路徑的方法。在此之前，首先介紹城市路網(wǎng)的拓撲結構及交通仿真數(shù)據(jù)的存儲，將其作為路徑規(guī)劃的數(shù)據(jù)基礎。

2 路網(wǎng)的拓撲結構與交通仿真

2.1 路網(wǎng)拓撲結構與數(shù)據(jù)存儲

城市路網(wǎng)是一個權值時變且包含轉向限制的有向圖[18]，如圖3所示。這里的時變性是指因交通流具有一定的周期相似性，導致路網(wǎng)權值(如路段行程時間)也呈現(xiàn)周期相似性規(guī)律的特性，權值更新的周期應當視具體路網(wǎng)和交通情況而定。

圖3 路網(wǎng)拓撲結構示意圖Fig. 3 Schematic diagram of road network topology

路網(wǎng)拓撲結構要素釋義如下：1)圓標數(shù)字是節(jié)點編號，表示路網(wǎng)中的交叉路口(僅考慮十字形和丁字形交叉路口)；2)路段是指兩個相鄰節(jié)點之間的道路，且具有方向性，如6→7表示由節(jié)點6指向節(jié)點7的路段，并定義節(jié)點6為父節(jié)點，節(jié)點7為子節(jié)點；3)黑色數(shù)字表示路段權值，用來描述車輛行駛該路段所花費的代價，選取路段行程時間作為權值。4)綠色數(shù)字表示轉向延誤權值，描述車輛在交叉口轉向所耗費的時間，如車輛的路徑規(guī)劃為1→2→6，車輛從節(jié)點1到達節(jié)點2須右轉，則右轉的延誤權值為9，若節(jié)點有轉向限制，則用無窮大代表轉向延誤權值。

城市路網(wǎng)的數(shù)據(jù)存儲需要考慮交叉口、轉向限制以及路段之間的聯(lián)通性等，目前關于路網(wǎng)數(shù)據(jù)存儲方面的研究有鄰接矩陣、鄰接表、十字鏈表等多種建模存儲方法[19]。筆者參考文獻[20]提出的前向關聯(lián)邊數(shù)據(jù)存儲結構(后文簡稱數(shù)據(jù)存儲結構)，并針對路徑規(guī)劃算法的需要做適當改進，以快速方便地訪問路網(wǎng)數(shù)據(jù)，基于圖3路網(wǎng)的數(shù)據(jù)存儲結構如圖4所示(部分節(jié)點數(shù)據(jù))。

圖4 路網(wǎng)的數(shù)據(jù)儲存結構Fig. 4 Data storage structure of road network

數(shù)據(jù)存儲結構主要由3個矩陣構成：1)路網(wǎng)共有12個節(jié)點，構造12×2矩陣ParentNode_Pointer。矩陣的第一列存放路網(wǎng)所有節(jié)點(視為父節(jié)點)，并按升序排列，第二列存放父子節(jié)點指針；2)再分析路網(wǎng)節(jié)點之間的聯(lián)通關系，構造n×2矩陣ChildNode_Weight(n視具體路網(wǎng)而定)。該矩陣的第一列依次存放矩陣ParentNode_Pointer的每一個父節(jié)點的所有鄰節(jié)點(視為子節(jié)點)，每一個父節(jié)點的若干子節(jié)點仍升序排列，第二列存放父節(jié)點指向子節(jié)點的路段權值。當矩陣ChildNode_Weight唯一確定后，記錄每一個父節(jié)點的最小子節(jié)點所在的行編號，并存放在矩陣ParentNode_Pointer對應的父子節(jié)點指針。3)最后分析路網(wǎng)節(jié)點間的轉向限制及對應權值，構造n×6矩陣TurningNode_Weight。第1至3列存放由父節(jié)點指向子節(jié)點并轉向后的節(jié)點編號(只考慮左轉、直行及右轉)，第4至6列存放對應的轉向權值。

道德焦慮的化解也需要進一步完善村民的民主意識和政治自覺，包括拓展制度化參與渠道、 充分地掌握信息、擁有更多的政治參與權和知情權。同時，在實地調研中還發(fā)現(xiàn)，進一步完善“村民理事會”等自治組織，能夠從制度建設方面充分保障村務公開和村民自治。搭建一個可以交流、處置、落實的工作平臺，確保村民話有地方說、理有地方講、困有人幫、惑有人解，能夠有力推動基層村民政治訴求和生活需求的解決，讓制度創(chuàng)新和信息公開成為道德文化的一個減壓器。

2.2 路網(wǎng)建模及交通仿真

環(huán)境建模方面，基于Vissim建立重慶大學城局部路網(wǎng)，主要工作包括路段的建立、紅綠燈及交通配時的設置、路口交通分流策略的設置等。該路網(wǎng)共有230個節(jié)點，778條路段，總面積近70 km2，如圖5所示。圖中，節(jié)點82周圍的藍色節(jié)點表示子節(jié)點，綠色數(shù)字表示子節(jié)點的鄰近節(jié)點。

圖5 基于Vissim軟件的重慶大學城路網(wǎng)建模Fig. 5 Road network modeling of Chongqing University Town based on Vissim software

交通仿真方面，結合重慶大學城實際交通情況和路網(wǎng)建模環(huán)境，在路網(wǎng)邊沿若干重要節(jié)點設置兩組車流量，分別模擬早高峰期間8:17—8:30與8:30—8:43(以下分別稱為時段1和時段2，并設路網(wǎng)權值時變周期為780 s)兩個時段的車流輸入。同時為每個路段設置行程時間采集器，采集結果作為路段權值。另外為了讓車流充分融入路網(wǎng)內部以體現(xiàn)不同路段的交通特性，在1 800 s后再開始記錄行程時間。最后對仿真所得數(shù)據(jù)做統(tǒng)計分析，得到大學城路網(wǎng)行程時間數(shù)據(jù)庫，以此作為路徑規(guī)劃的數(shù)據(jù)來源。以節(jié)點82作為父節(jié)點的部分仿真行程時間數(shù)據(jù)如表2所示。

表2 部分仿真行程時間數(shù)據(jù)

3 GOPP算法及仿真分析

路徑規(guī)劃算法筆者在經(jīng)典Dijkstra算法基礎上，新增跨時段路段實際權值計算環(huán)節(jié)，提出了GOPP算法，如圖6所示。

圖6 GOPP算法流程Fig. 6 Flow chart of GOPP algorithm

以圖1示例路網(wǎng)為例，介紹GOPP算法的5個步驟：

2)遍歷未知節(jié)點集。進入循環(huán)，在U中搜索距源點s權值最小的節(jié)點k，將該點從U移到S中，同時將該點k的權值和對應的路徑分別存放到dk和pk中。在第1)步基礎上，設集合U中節(jié)點2具有最小累計權值d2，故S={1,2}，U={3,4,5,6,7,8,9,10,11,12}。

3)比較更新鄰近節(jié)點權值。設節(jié)點k至鄰近子節(jié)點j的路段權值與轉向權值之和為w(k,j)，判斷dk+w(k,j)與dj的大小，更新s至j的最小權值dj和對應路徑pj。在第2)步基礎上，節(jié)點2的鄰近節(jié)點包括3和6，由于節(jié)點3和6的累積權值為無窮大，故此時應當更新d3和d6。傳統(tǒng)Dijkstra算法從第1)步至第3)步不斷循環(huán)，直至U=?便結束算法。筆者所提出的GOPP算法新增跨時段路段的實際權值計算環(huán)節(jié)，該環(huán)節(jié)將判斷路網(wǎng)權值是否更新并計算跨時段路段的實際權值，如圖6虛線框所示，具體步驟如下第4)、5)步。

5)計算臨界節(jié)點對的實際累計權值。在第4)步基礎上，設臨界路段6→10在時段1和時段2的權值分別為ω6_10_1和ω6_10_2，車輛在路段6→10于時段1的行駛路程比例r為：

(1)

則路徑1→2→6→10的實際累計權值為：

(2)

據(jù)此將集合S中的所有臨界父節(jié)點構成集合Sc，將集合U中的所有臨界子節(jié)點構成集合Uc，進而組成臨界節(jié)點對集C。參照式(1)與式(2)，可以計算臨界節(jié)點對集的所有跨時段路段實際權值。之后更新時段編號Tnum，然后循環(huán)第2)步到第5)步，直到U=?。

4 仿真驗證及分析

仿真實驗所用的硬件平臺是Win10 @64 bit + Intel Core i5-4590 @3.3 GHz +RAM @ 8G，軟件平臺是MATLAB 2018a。

4.1 經(jīng)典Dijkstra算法與蟻群算法的比較

首先，為了體現(xiàn)經(jīng)典Dijkstra算法在靜態(tài)權值路網(wǎng)中的全局最優(yōu)計算能力，基于預先建立的重慶大學城局部路網(wǎng)和時段1(8:17—8:30)的路段行程時間數(shù)據(jù)庫，將智能啟發(fā)式算法代表之一的蟻群算法作為對照[6]，不失一般性地設定了3組起訖點進行仿真實驗。路徑規(guī)劃結果及累積路段行程時間如圖7和表3所示，圖7中的藍色、紫色、綠色分別代表起訖點(1，229)(4，224)(12，209)，實線與虛線分別代表Dijkstra算法和蟻群算法。

圖7 Dijkstra算法與蟻群算法的3組路徑規(guī)劃結果Fig. 7 Three groups of path planning results of Dijkstra algorithm and ant colony algorithm

表3 Dijkstra算法與蟻群算法的3組路徑規(guī)劃的累計行程時間

由表3可知，Dijkstra算法的累積行程時間均小于蟻群算法。以圖7的起訖點(12,209)為例，蟻群算法所規(guī)劃的路徑與Dijkstra算法部分重合，表明具有一定的路徑尋優(yōu)能力，但中途有兩次與Dijkstra算法路徑分離，這是由于蟻群算法本身自帶隨機因子，在從源節(jié)點至目標節(jié)點的搜索過程中受隨機因素影響較大，盡管在螞蟻信息素的引導下可以加快收斂，但同時也增大了陷入局部最優(yōu)的概率。

圖8為蟻群算法的行程時間隨迭代次數(shù)的變化圖，由圖可知當?shù)螖?shù)達到22次后，蟻群算法便已陷入了局部最優(yōu)，極不利于對全局最優(yōu)路徑的求解，而作為廣度優(yōu)先搜索算法的Dijkstra算法則避免了局部最優(yōu)的缺陷。另外，蟻群算法和Dijkstra算法的運行時間大約分別在1 s和1.5 s左右，Dijkstra算法以額外較小的運行時間成本獲得了更滿意的最優(yōu)路徑。綜上所述，選擇Dijkstra算法作為靜態(tài)權值路網(wǎng)的全局最優(yōu)路徑規(guī)劃方法是可行且有效的，在時變權值路網(wǎng)中則采用改進之后的GOPP算法。

圖8 蟻群算法行程時間隨迭代次數(shù)的變化Fig. 8 The change of the travel time of ant colony algorithm with the number of iterations

4.2 GOPP算法與SPP、RPP的比較

為了驗證所提出的GOPP算法在時變權值路網(wǎng)求解全局最優(yōu)路徑的優(yōu)越性，需要合理設定起訖點及路徑規(guī)劃時刻，否則可能因累積行程時間小于本時段周期，或者部分路段的行程時間在相鄰時段變化不大，而出現(xiàn)GOPP和RPP、SPP的路徑規(guī)劃結果相同的情況?；诖?，筆者在細致分析所建路網(wǎng)及行程時間特點基礎上，選取了起訖點(12,209)作為仿真實驗節(jié)點。設車輛位于源節(jié)點12的時刻為早上8:17(即時段1起始時刻)，路網(wǎng)的權值將在8:30更新，利用Dijkstra算法分別采用SPP、RPP和GOPP 3種思想進行路徑規(guī)劃，3種路徑規(guī)劃結果見表4和圖9。

圖9 3種路徑規(guī)劃仿真結果比較Fig. 9 Comparison of simulation results of three path planning methods

表4 3種路徑規(guī)劃結果累計權值比較

3種路徑規(guī)劃方式的起訖點直線距離變化曲線如圖10所示。

圖10 3種路徑規(guī)劃方式的起訖點直線距離變化曲線Fig. 10 Straight line distance curves of starting and ending points of three path planning methods

綜合分析圖9和圖10，并結合重慶大學城實際交通情況，可以看出：

1)3種算法制定的3條路徑在節(jié)點12至節(jié)點49重合，然后GOPP方法出現(xiàn)分離；算法SPP和RPP沿路段49→48朝西延伸至節(jié)點107，之后再次出現(xiàn)分離；而算法GOPP沿49→72朝南延伸直至目標節(jié)點；

2)節(jié)點107南向路段(大學城中路)分布有重慶大學、重慶一中等學校，北向路段分布有重慶師范大學、大學城地鐵站，仿真結果表明算法SPP和RPP到達節(jié)點107的時刻為8:30:11，此時正是早高峰擁堵時段，路網(wǎng)權值已經(jīng)更新。因此，RPP在節(jié)點107基于時段2的路網(wǎng)權值重新規(guī)劃剩余路徑，規(guī)劃結果表明節(jié)點107沿西(大學城南路)行駛可以有效避免擁堵；

3)節(jié)點184東西路段(大學城南路)是大學城路網(wǎng)的骨干路段，南北路段分布有華潤微電園、固廢流轉中心等企業(yè)，在時段1交通較為擁堵，進入時段2逐漸緩解，因此圖10藍色曲線在經(jīng)過了節(jié)點184后便較快到達了終點。故GOPP規(guī)劃路徑累計權值為僅為1 158.7 s，相比SPP和RPP分別減少了212.7 s和57.6 s，證明了GOPP在縮短出行規(guī)劃時間上的優(yōu)越性。

5 結 論

首先分析了現(xiàn)有路徑規(guī)劃方法的不足，隨后推導了跨時段路段的實際權值，界定了路徑規(guī)劃領域的局部最優(yōu)疊加值與全局最優(yōu)值的區(qū)別，并基于Dijkstra算法提出了一種全局最優(yōu)路徑規(guī)劃方法。仿真結果表明，GOPP相比SPP和RPP具有最小的累積權值，有效地驗證了GOPP在面向時變權值路網(wǎng)求解全局最優(yōu)路徑的優(yōu)越性。有如下結論：

1)SPP和RPP兩類常見路徑規(guī)劃方式在面對具有權值時變特性的交通路網(wǎng)時，無法求解全局最優(yōu)路徑；

2)經(jīng)典的Dijkstra算法盡管算法冗余度較高，卻以廣度優(yōu)先比智能啟發(fā)式算法更能求得全局最優(yōu)解；

3)基于Dijkstra算法的GOPP路徑規(guī)劃方法能夠實現(xiàn)權值時變路網(wǎng)的時間最短全局最優(yōu)路徑的求解，可以有效縮短駕駛員的交通出行時間，對今后智能網(wǎng)聯(lián)汽車和智能交通系統(tǒng)的發(fā)展具有一定的理論指導意義。