黎萬洪,胡明輝,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)意義。
為了引出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ǔ)。
城市路網(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è)減壓器。
環(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ù)
路徑規(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=?。
仿真實(shí)驗(yàn)所用的硬件平臺(tái)是Win10 @64 bit + Intel Core i5-4590 @3.3 GHz +RAM @ 8G,軟件平臺(tái)是MATLAB 2018a。
首先,為了體現(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
為了驗(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)越性。
首先分析了現(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)意義。