交通路況感知下的自適應(yīng)動態(tài)路徑規(guī)劃方法

常盟盟，袁磊，丁治明，李路通

(1.北京工業(yè)大學(xué)，信息學(xué)部，北京100124；2.中國科學(xué)院，軟件研究所，北京100190)

0 引言

隨著城市居民交通出行需求不斷攀升，現(xiàn)有城市路網(wǎng)的承載能力不足給城市發(fā)展帶來了巨大挑戰(zhàn)。實際交通路網(wǎng)的狀態(tài)復(fù)雜多變，高峰流量、天氣、突發(fā)事故、交通管制等因素均會導(dǎo)致交通路網(wǎng)狀態(tài)劇烈變化。如何提高交通運行效率，改善城市交通現(xiàn)狀成為一個亟待解決的關(guān)鍵問題。傳統(tǒng)的基于靜態(tài)路網(wǎng)的路徑規(guī)劃方法，如Dijkstra、A*、Floyd 算法、遺傳算法、粒子群算法、蟻群算法及其改進算法等，在路網(wǎng)狀態(tài)動態(tài)變化過程中不能及時的做出有效的應(yīng)對策略。同時，在大規(guī)模動態(tài)路網(wǎng)中，路徑規(guī)劃響應(yīng)速度遠遠跟不上決策速度。針對上述問題，本文提出一種自適應(yīng)的動態(tài)路徑規(guī)劃方法。首先，將路段上的路況信息融合到對路網(wǎng)區(qū)域的分析，對路網(wǎng)進行分層劃分，提高路況分析的合理性；其次，在劃分子網(wǎng)的基礎(chǔ)上，采用層次擴散方法對子網(wǎng)間的路徑傳播進行建模，分析層次子網(wǎng)之間的連接關(guān)系，作為路徑查找的擴展視野；最后，結(jié)合路徑規(guī)劃的實際需求，構(gòu)建一種自適應(yīng)的路徑規(guī)劃模型。與現(xiàn)有的經(jīng)典路徑規(guī)劃方法相比，本文提出的規(guī)劃方法填補了傳統(tǒng)模型在路況變化下的可用性不足，擴展了路徑規(guī)劃模型對當(dāng)下交通出行新需求的適應(yīng)性。

1 相關(guān)工作

層次搜索策略則是結(jié)合道路網(wǎng)絡(luò)的層次特征來提高路徑的搜索效率。胡繼華等[3]將出租車的路徑選擇經(jīng)驗作為語義，構(gòu)建基于經(jīng)驗路徑的網(wǎng)絡(luò)。路徑規(guī)劃算法根據(jù)最短路和經(jīng)驗網(wǎng)絡(luò)進行組合完成路徑規(guī)劃。在一定程度上復(fù)雜語義可以反映路網(wǎng)的動態(tài)變化特征，因此規(guī)劃路徑縮短了路徑的旅行時間。另外，子圖劃分可以捕獲網(wǎng)絡(luò)中具有強連接關(guān)系的節(jié)點、區(qū)域以及同質(zhì)的一些屬性。Zakrzewska 等[4]提出一種動態(tài)網(wǎng)絡(luò)劃分算法，隨著底層圖的變化逐步更新被跟蹤的子網(wǎng)。在每次更新過程中修改子網(wǎng)中的節(jié)點序列，從而將大規(guī)模網(wǎng)絡(luò)的動態(tài)變化局部化處理。Rossetti 等[5]將圖定義為二級實體，核心節(jié)點和外圍節(jié)點。根據(jù)局部拓撲擾動動態(tài)跟蹤子圖的變化，利用局部模式和約束傳播范圍來減少節(jié)點之間尋址的計算開銷。張正華等[6]提出一種交通子網(wǎng)劃分方法，基于路段、排隊長度等多維因素建立關(guān)聯(lián)模型表示節(jié)點的重要性，對網(wǎng)絡(luò)進行動態(tài)劃分。區(qū)別于傳統(tǒng)的圖劃分思想，流式圖劃分[7]一次處理部分圖數(shù)據(jù)，并對于已分配到各個子圖的節(jié)點不再進行遷移。在動態(tài)變化過程中調(diào)整節(jié)點之間的拓撲關(guān)系和權(quán)重變化。該方法可以有效地保留劃分子圖的性質(zhì)，進而提升動態(tài)網(wǎng)絡(luò)中路徑尋址的性能。針對動態(tài)路網(wǎng)環(huán)境下道路狀態(tài)的頻繁更新問題，本文提出一種基于流式圖劃分的自適應(yīng)動態(tài)路徑規(guī)劃方法，指導(dǎo)移動對象在路網(wǎng)行駛過程中能夠自適應(yīng)的避讓或降低路況變化所帶來的影響。

2 理論基礎(chǔ)

2.1 動態(tài)路網(wǎng)下的路徑規(guī)劃

交通路網(wǎng)是一個隨時間動態(tài)變化的有向圖網(wǎng)絡(luò)，可以定義為在一個時間周期內(nèi)的網(wǎng)絡(luò)狀態(tài)，其中，T為變化周期，在這個周期內(nèi)交通路網(wǎng)可以認為是一個靜態(tài)的網(wǎng)絡(luò)為路網(wǎng)節(jié)點集合，vi為其中的節(jié)點，i是節(jié)點編號，vi∈V，E為邊的集合，ej為其中的有向路段，j是邊編號，ej∈E。隨著T的變化，路網(wǎng)G衍生出不同的時間快照G1,G2,…,GT。路徑的起訖點(Origin-Destination，OD)分別來源于集合V中的兩個節(jié)點，將從起點vo到終點vd的連通路徑稱為OD路徑L。L由相鄰的節(jié)點集合＜vo,vi,…,vd ＞連接而成，路段的旅行代價定義如下：

定義1(路段旅行代價)。設(shè)路徑L中的兩個鄰接節(jié)點序列＜vi,vi+1＞來自于G中的路段集E，令表示δ在邊＜vi,vi+1＞上的代價函數(shù)，則節(jié)點之間的旅行代價為

區(qū)別于常用的歐式距離度量，δ為隨時間變化的映射函數(shù)。路徑L的總代價，即求和連接OD對之間的路段代價為

式中：t0,t1,…,tn為變化的時間周期；vi為對應(yīng)的抵達點；n為花費的時間步長；m為路段的個數(shù)。動態(tài)路徑規(guī)劃的問題域定義為在連續(xù)邊集合E上的函數(shù)，通過尋找最小路徑代價作為最優(yōu)解。由于路網(wǎng)中的路段代價隨著時間t發(fā)生變化，基于時間t的OD路徑優(yōu)化問題定義為

2.2 雙向路徑搜索2-Hop Cover

設(shè)計意圖：教師引導(dǎo)學(xué)生明確遺傳物質(zhì)應(yīng)該具有的特點，使學(xué)生能夠理解為什么當(dāng)時科學(xué)家會認為蛋白質(zhì)是遺傳物質(zhì)。

對于有向圖G中任意給定節(jié)點o和d，其距離為D(o,d)，如果D(o,d)=ShortPath(o,d,Tuple)，那么該Tuple 就是圖G中節(jié)點o到節(jié)點d的2-Hop Cover。在動態(tài)路網(wǎng)中，2-Hop Cover可以通過動態(tài)的調(diào)整局部的Tuple序列來適應(yīng)路網(wǎng)拓撲和道路權(quán)重的變化，保持路徑序列的代價最小。

3 基于路網(wǎng)層次劃分的自適應(yīng)動態(tài)路徑規(guī)劃算法

針對路網(wǎng)的動態(tài)變化問題，本文構(gòu)建了一種基于層次劃分的映射關(guān)系網(wǎng)絡(luò)，將路徑規(guī)劃問題進行時空變化分解，規(guī)劃路徑伴隨層次的變化進行實時調(diào)整，從而實現(xiàn)動態(tài)路徑規(guī)劃需求。如圖1所示，OD請求通過查找路網(wǎng)層次劃分結(jié)構(gòu)獲取最小包含子圖G，函數(shù)ψ(t)更新子圖狀態(tài)。此時的路徑規(guī)劃算法依賴于子網(wǎng)中進行，在路徑旅行過程中，若達到更新的下一周期t+1時，更新所在節(jié)點和目標(biāo)節(jié)點的最小包含子網(wǎng)。從而路徑L的子序列按照時間粒度t進行劃分，伴隨層次網(wǎng)絡(luò)的變化進行調(diào)整，最終實現(xiàn)在動態(tài)路網(wǎng)環(huán)境中的自適應(yīng)路徑規(guī)劃求解。

圖1 基于子網(wǎng)劃分的自適應(yīng)路徑規(guī)劃模型Fig.1 Adaptive path planning model based on subnet division

3.1 動態(tài)路網(wǎng)層次劃分

對于頻繁變化的動態(tài)交通網(wǎng)絡(luò)而言，區(qū)域劃分是一個NP難題?，F(xiàn)有的劃分聚類在隨時間變化的路網(wǎng)中，路網(wǎng)節(jié)點或邊的聚類劃分雖然提高了簇內(nèi)的尋址效率，但對于簇之間的路徑搜索因增加了劃分約束而變得復(fù)雜。為了提高路徑查找效率，通過預(yù)計算節(jié)點之間的連接關(guān)系Tuple，并在此基礎(chǔ)上局部更新區(qū)域狀態(tài)來提高路徑查找性能。在每一步劃分過程中，根據(jù)節(jié)點之間的層次關(guān)系預(yù)先計算節(jié)點之間的最短路徑傳播范圍，并將相互分裂的節(jié)點二分為下一層子網(wǎng)，如圖2所示。

圖2 動態(tài)路網(wǎng)層次結(jié)構(gòu)劃分Fig.2 Hierarchy structure partition of situational traffic network

層次結(jié)構(gòu)中每個分支都代表一個子網(wǎng)G和對應(yīng)的路徑元組索引C，路徑查詢在網(wǎng)絡(luò)快照中進行搜索。網(wǎng)絡(luò)快照對應(yīng)一個態(tài)勢鄰接矩陣，記錄了相鄰節(jié)點之間的旅行代價，具體如算法1。

算法1 路網(wǎng)層次劃分Bisect G()輸入：路網(wǎng)g，分裂個數(shù)k，劃分粒度e輸出：路網(wǎng)層次樹h-tree if g 中節(jié)點數(shù)＜e return*h-tree end if for k 階劃分g.level←calmaxc()g ;/*根據(jù)中心性計算最高的節(jié)點等級*/for n in g if 節(jié)點n 的等級等于g 的等級添加n 到中心集合C end if end for end for split ←cluster(C,g)AddTree(*h-tree,split)/*按照C節(jié)點做k-聚類劃分*/for each sub G in split /＊將子圖添加到層次樹結(jié)構(gòu)中＊/Bisect G(sub G,k,e)/＊遞歸進行子圖劃分＊/end for

3.2 雙向擴散路徑查找方法

考慮如下OD出行需求，假設(shè)查找從葉節(jié)點G3,1的起點vo到G3,4的節(jié)點vd。從vo到vd的路徑映射分為梯度擴散L(1)、雙向探測L(2)階段。路徑?jīng)Q策沿著路徑的梯度方向進行節(jié)點探測，即首先定位樹中vo所屬的子網(wǎng)(即葉子節(jié)點)，將中心性高于vo且梯度方向一致的節(jié)點加入探測隊列。梯度?f表示起點到目標(biāo)點創(chuàng)建的方向向量，OD 路徑軌跡沿著?f，并通過近鄰節(jié)點逐步擴散至目標(biāo)節(jié)點。如果沒有滿足條件的中介點，則進入h-1 層子網(wǎng)，h表示G的層次。重復(fù)上述步驟獲得滿足條件的節(jié)點，選擇距離最小的路徑作為規(guī)劃路徑，即

式中：SPD(·)為節(jié)點或子網(wǎng)中心之間的最短路徑；cG為G的中心節(jié)點；Gh為h層的子網(wǎng)。為路徑在t時刻的到達節(jié)點，在時間tn時，路徑到達了目標(biāo)節(jié)點的包含子網(wǎng)；L(1)為vo開始向所在子網(wǎng)的高中介性節(jié)點探測。

路徑探測是在劃分子網(wǎng)中進行最優(yōu)路徑的選擇，隨著路況變化如何決策最優(yōu)路線是路徑搜索的一個關(guān)鍵問題。為了提高查找效率，采用雙向探測算法分別從起點和目標(biāo)點進行正向和逆向的查找。L(2)定義為

式中：Go、Gd分別為起點、目標(biāo)點所在的最小包含圖，F(xiàn)、B分別為正向、逆向的查找隊列。當(dāng)正向和逆向最短路徑序列融合時，即為當(dāng)前最優(yōu)路徑L(2)。最小包含圖查找過程如算法2所示。

算法2 最小包含圖查找FindMin G()輸入：狀態(tài)樹Stree，起始節(jié)點o，目標(biāo)節(jié)點d輸出：最小共有網(wǎng)絡(luò)Com G Sub G ←*Stree.root if Sub G 包含o，d Push Sub G into Com G /*起止節(jié)點同時位于該子圖，將子圖入隊*/end if if Sub G 的右子樹不為空if leftchild包含o，d FindMin G(&leftchild,o，d)/*起止節(jié)點位于左子樹，遞歸左子樹*/end if end if if Sub G 的左子樹不為空if rightchild包含o，d FindMin G(&rightchild,o，d)/*起止節(jié)點位于右子樹，遞歸右子樹*/end if end if return*Com G

3.3 多路并行的雙向路徑探測算法

提出一種基于層次網(wǎng)絡(luò)的多路并行動態(tài)探測算法(Multi-channel Parallel Dynamic Probing,MPDP)。MPDP探測算法融合了路況的時變狀態(tài)，路徑探測請求包含路徑序列和路徑累計權(quán)重。MPDP探測算法的具體步驟如下：

Step 1vo和vd根據(jù)狀態(tài)樹索引，采用BFS查找包含兩點的最小共有子網(wǎng)Gmin(Min-Common Graph)。分別查找Gmin的左右子樹，獲得vo和vd所在的Go,Gd。

Step 2Go發(fā)送到達目標(biāo)節(jié)點vd的路徑探測請求，計算方向梯度?f(G,vd)，并選擇與?f梯度方向一致的節(jié)點，作為傳播的下一跳。Gd采用逆向遞推序列選擇與?f一致的節(jié)點。

Step 3 按照?f方向逐跳擴散，通過不斷擴大節(jié)點的子網(wǎng)視野來，直到雙向探測抵達Gmin，Gh作為Gmin的鄰近祖先網(wǎng)絡(luò)，作為擴展的接收視野。

Step 4 根據(jù)Gh得到k條路徑序列p1=＜vo,u1,…,vd ＞，p2=＜vo,u2,…,vd ＞，…，pk，其中，ux為不同路徑上的中繼頂點。

Step 5 將備選路徑p1,p2,…,pk上各中繼節(jié)點路段的權(quán)重相加，得到對應(yīng)的路徑權(quán)重wp1(t)，wp2(t)，…，wpk(t)。

路徑的跳數(shù)越多，在一定程度上增加了路徑變化的可能性，引入正則化因子λ，量化子網(wǎng)跳數(shù)產(chǎn)生的影響，優(yōu)化后的路徑代價ωp(t)為

式中：hops()· 為統(tǒng)計路徑跳數(shù)的函數(shù)。比較ωp1和ωp2,…,ωpk，選取最小路徑代價作為t周期內(nèi)的路徑最優(yōu)解。

最終，通過L(1)、L(2)分段路徑映射算法，將OD路徑L映射到時空域中，指導(dǎo)移動對象在旅行過程中根據(jù)路況變化進行動態(tài)調(diào)整，最終路徑L收斂于終點。

4 實驗結(jié)果與分析

為評價算法性能，實驗采用北京市2012年12月實時路網(wǎng)數(shù)據(jù)集，采用開源數(shù)據(jù)集OpenStreetMap 提供的北京市路網(wǎng)，提取了車輛行駛的132039 個路段和92340 個節(jié)點，信息采用50000 多輛出租車近13 億GPS 時間序列軌跡點聚合而成，更新周期為38 s。實驗環(huán)境為Intel(R)Xeon Silver 4210 CPU@2，20 GHz，64 GB 內(nèi)存，Windows10 64位操作系統(tǒng)。

實驗參數(shù)設(shè)置：在h-tree的同一層次中，層次劃分k值的選擇關(guān)系到路徑所經(jīng)過的子網(wǎng)個數(shù)。對于跨子網(wǎng)的OD路徑，所經(jīng)過的子網(wǎng)序列的最大值為2(k-2)-1,k≥2。為了提高子網(wǎng)間路徑的查找效率，同時降低子網(wǎng)跳數(shù)增加所帶來的潛在態(tài)勢變化，k取值為2。劃分粒度e依賴于實際的路網(wǎng)規(guī)模，以北京市路網(wǎng)(包含92340節(jié)點)為例。CH算法采用節(jié)點收縮過程構(gòu)建了104928 條捷徑，通過節(jié)點關(guān)聯(lián)進一步聚合為2143個層次指導(dǎo)路網(wǎng)的語義劃分。因此，等同的將最小劃分粒度e設(shè)置為[92340/2143]=43。

將本文提出的路徑動態(tài)探測方法MPDP 與Dijkstra，A*，CH，動態(tài)A*算法進行實驗對比。為了捕捉路網(wǎng)對路徑規(guī)劃造成的影響，在北京市實時路網(wǎng)數(shù)據(jù)上進行不同時段的實驗設(shè)置。表1為8:00和14:00 對路網(wǎng)中OD 點對進行路徑請求，對應(yīng)其平均訪問節(jié)點個數(shù)。

表1 路網(wǎng)OD對路徑請求的實驗結(jié)果Table 1 Results on path requests of OD pairs

在算法查詢性能方面，Dijkstra 擴散過程采用貪心算法，迭代計算其到n階鄰居節(jié)點的最短路徑，8:00平均尋址節(jié)點訪問總數(shù)為57671，其單次查詢耗時為126 ms，時間復(fù)雜度最高。A*和動態(tài)A*算法在路徑搜索過程采用啟發(fā)式策略，在很大程度上降低了不必要的訪問節(jié)點，其訪問節(jié)點總數(shù)較Dijkstra 降低了37.56%和76.32%，請求時間最小降低到88 ms。CH算法通過進行節(jié)點收縮的預(yù)處理，減少了路徑查詢所依賴圖的體量來提高路徑查找性能。其對應(yīng)的訪問節(jié)點總數(shù)為462，在查詢時間上提速為98 ms。然而CH 算法中的節(jié)點依賴于快照，需要額外的從快照中恢復(fù)計算實際節(jié)點。MPDP算法采用了分層的圖劃分方法，其檢索范圍小于CH 基于全局節(jié)點收縮的圖快照，故其訪問節(jié)點數(shù)和響應(yīng)時間均高于上述模型，最小訪問節(jié)點數(shù)為378，響應(yīng)時間為56 ms。圖3為不同方法在不同起點時刻的查詢性能。差異性越大表示模型的魯棒性越好?？梢钥吹?，Dijkstra，A*和CH 算法的查詢性能并沒有發(fā)生顯著變化，而動態(tài)算法的差異性較大。查詢性能依賴于模型路徑查找的時間復(fù)雜度，不同模型的訪問節(jié)點數(shù)隨著路網(wǎng)態(tài)勢的增加有所提高，這是由于路網(wǎng)變化導(dǎo)致原來的最短路徑序列失效。路網(wǎng)中OD 平均路徑距離在14:00 為1675.32 m，在8:00 增加到1821.34 m，兩個時刻路網(wǎng)狀態(tài)下Dijkstra，A*和CH 算法的查詢耗時差異為0.90%,3.00%和9.18%。動態(tài)A*算法能夠根據(jù)路網(wǎng)變化作出調(diào)整，其差異為35.38%，但其查詢耗時較大。MPDP算法其差異值為9.80%并且查詢耗時最小。因此，針對路況變化動態(tài)路徑規(guī)劃算法具有更好的魯棒性和查詢性能。

圖3 不同模型的單次查詢耗時對比Fig.3 Comparison of single query time of different algorithms

路況的時變性導(dǎo)致在不同起點時刻，路徑規(guī)劃算法下的旅行耗時不同，如圖4所示。選取北京市OD 起訖地點(40.019201,116.354828),(39.778991,116.353455)，分別在8:00 和14:00 進行不同的路徑規(guī)劃算法。在14:00，5種方法計算得到該起訖點的相同路徑序列包含187 個節(jié)點，如圖5(b)所示；在8:00，Dijkstra，A*和CH算法采用14:00時的相同路徑，動態(tài)A*和MPDP 算法根據(jù)路況變化得到包含157個節(jié)點的新路徑，如圖5(a)所示。

圖4 不同起點時刻的旅行時間變化Fig.4 Time-consuming in travel at different starting time

圖5 相同OD對在不同路網(wǎng)狀態(tài)下的最優(yōu)路徑Fig.5 Optimal path for same OD pair in different road network situations

同一算法在不同起點時刻計算出的路徑旅行耗時不同，這是由于路況變化導(dǎo)致路段的通行能力降低。在14:00，不同算法的路徑旅行時間并沒有顯著差異，可以認為路網(wǎng)狀態(tài)接近于靜態(tài)路網(wǎng)。對比8:00 的路徑耗時可以看出，隨著路況變化的增強，傳統(tǒng)的靜態(tài)路網(wǎng)規(guī)劃算法沒有對這些受影響路段進行規(guī)避，導(dǎo)致旅行時間延長。而動態(tài)A*和MPDP 路徑規(guī)劃算法可以有效地降低路況變化引起的增量代價，提高預(yù)估到達時間的準(zhǔn)確性。

路況變化同樣對路徑規(guī)劃算法的節(jié)點探測范圍產(chǎn)生影響。對于靜態(tài)網(wǎng)絡(luò)模型，路徑探測通過一次執(zhí)行來完成，即僅與路網(wǎng)上一時間快照的狀態(tài)相關(guān)。因此，節(jié)點探測過程保持不變，如圖6(a)和6(b)中的Dijkstra，A*和CH 探測曲線比較一致。對于動態(tài)A*算法，在8:00的探測節(jié)點總數(shù)為13248。相對于Dijkstra，A*算法能夠通過較小的節(jié)點訪問量和探測距離，抵達目標(biāo)節(jié)點。這是由于動態(tài)A*算法可以在旅行過程中，根據(jù)路徑啟發(fā)函數(shù)動態(tài)調(diào)整下一階段的行駛路徑。然而動態(tài)A*算法依然需要訪問大量的節(jié)點進行對比計算，從而做出合理決策，因此動態(tài)A*算法的節(jié)點訪問量較高，其節(jié)點訪問總數(shù)和探測范圍為13248和120031。CH探測算法通過預(yù)處理對節(jié)點進行篩選，因此CH 算法的節(jié)點訪問總數(shù)低于Dijkstra，A*和動態(tài)A*算法。CH算法通過節(jié)點收縮聚合生成整個路網(wǎng)的核心主干網(wǎng)絡(luò)，然而其對每個節(jié)點的重要性計算采用平等的衡量指標(biāo)，難以適應(yīng)環(huán)境下動態(tài)變化的節(jié)點優(yōu)先級，因此其探測范圍為345814 高于動態(tài)A*算法。MPDP算法結(jié)合動態(tài)A*和CH算法的優(yōu)點，通過層次劃分方法，減少了路徑探測的節(jié)點總數(shù)，同時根據(jù)劃分子網(wǎng)之間的尋址關(guān)系有效減少了路徑的探測距離。并且隨著變化能夠動態(tài)調(diào)整訪問節(jié)點和探測范圍，說明MPDP算法對變化的路網(wǎng)具有良好的魯棒性。

圖6 不同影響下的路徑探測范圍Fig.6 Path detection range under influence of situations

5 結(jié)論

本文在所提出的動態(tài)路徑索引的基礎(chǔ)上構(gòu)建了多路并行的路徑規(guī)劃方法，通過實驗驗證了時空索引樹有助于對動態(tài)路網(wǎng)的快速建模，提高了傳統(tǒng)路徑規(guī)劃方法在動態(tài)路網(wǎng)中的適用性。同時得出，在動態(tài)路網(wǎng)中不考慮路況狀態(tài)的路徑規(guī)劃方法需要昂貴的計算代價和耗時，而降低動態(tài)路網(wǎng)所帶來的附加代價必然需要路徑規(guī)劃模型從時空角度進行優(yōu)化。本文提出的動態(tài)路徑規(guī)劃方法在計算過程中融合了時空變化特征，在空間上通過索引結(jié)構(gòu)縮小路徑查找視野，同時周期性的對路網(wǎng)狀態(tài)進行更新，從時空角度對路徑規(guī)劃過程進行調(diào)整，這也是對基于靜態(tài)路網(wǎng)的路徑規(guī)劃方法的一種新擴展。