計(jì)及路網(wǎng)權(quán)值時(shí)變特性的全局最優(yōu)路徑規(guī)劃

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

(重慶大學(xué) a.汽車工程學(xué)院；b.機(jī)械傳動(dòng)國家重點(diǎn)實(shí)驗(yàn)室, 重慶 400044)

路徑規(guī)劃作為智能汽車的決策層，對(duì)于提高駕駛?cè)顺鲂行省⒕徑獬鞘袚矶戮哂兄匾饔?。起訖點(diǎn)行程時(shí)間是人們出行普遍較為關(guān)心之處，因此也成為了路徑規(guī)劃的首要需求[1]，其評(píng)價(jià)指標(biāo)是路段行程時(shí)間的累加值。根據(jù)路段行程時(shí)間是否變化，可以將路徑規(guī)劃劃分為靜態(tài)路徑規(guī)劃(static path planning，SPP)和滾動(dòng)路徑規(guī)劃(rolling path planning，RPP)。

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

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

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

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

為了引出GOPP算法，首先探討當(dāng)前最常見的兩種路徑規(guī)劃方法的缺陷。如圖1所示是一個(gè)路段行程時(shí)間動(dòng)態(tài)更新的示例路網(wǎng)，在時(shí)段1和時(shí)段2的路段行程時(shí)間如表1所示，兩個(gè)時(shí)段相鄰。假設(shè)當(dāng)前車輛位于交叉口2，當(dāng)前時(shí)刻t0處于時(shí)段1，目標(biāo)交叉口為11，現(xiàn)探討起訖點(diǎ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)的時(shí)變路段行程時(shí)間

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

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

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

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

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

2 路網(wǎng)的拓?fù)浣Y(jié)構(gòu)與交通仿真

2.1 路網(wǎng)拓?fù)浣Y(jié)構(gòu)與數(shù)據(jù)存儲(chǔ)

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

圖3 路網(wǎng)拓?fù)浣Y(jié)構(gòu)示意圖Fig. 3 Schematic diagram of road network topology

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

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

圖4 路網(wǎng)的數(shù)據(jù)儲(chǔ)存結(jié)構(gòu)Fig. 4 Data storage structure of road network

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

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

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

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

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

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

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

3 GOPP算法及仿真分析

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

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

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

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

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

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

(1)

則路徑1→2→6→10的實(shí)際累計(jì)權(quán)值為：

(2)

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

4 仿真驗(yàn)證及分析

仿真實(shí)驗(yàn)所用的硬件平臺(tái)是Win10 @64 bit + Intel Core i5-4590 @3.3 GHz +RAM @ 8G，軟件平臺(tái)是MATLAB 2018a。

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

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

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

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

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

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

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

4.2 GOPP算法與SPP、RPP的比較

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

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

表4 3種路徑規(guī)劃結(jié)果累計(jì)權(quán)值比較

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

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

綜合分析圖9和圖10，并結(jié)合重慶大學(xué)城實(shí)際交通情況，可以看出：

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

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

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

5 結(jié) 論

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

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

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

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