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

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

0 引言

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

1 相關(guān)工作

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

2 理論基礎(chǔ)

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

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

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

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

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

2.2 雙向路徑搜索2-Hop Cover

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

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

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

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

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

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

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

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

3.2 雙向擴(kuò)散路徑查找方法

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

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

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

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

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

3.3 多路并行的雙向路徑探測(cè)算法

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

表1 路網(wǎng)OD對(duì)路徑請(qǐng)求的實(shí)驗(yàn)結(jié)果Table 1 Results on path requests of OD pairs

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

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

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

圖4 不同起點(diǎn)時(shí)刻的旅行時(shí)間變化Fig.4 Time-consuming in travel at different starting time

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

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

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

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

5 結(jié)論

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