顧及轉(zhuǎn)向延誤的時(shí)間依賴A＊最短路徑算法

鄭年波,陸 鋒,李清泉,段瀅瀅

1.中國科學(xué)院地理科學(xué)與資源研究所資源與環(huán)境信息系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室,北京100101;2.武漢大學(xué)交通研究中心,湖北武漢430079

顧及轉(zhuǎn)向延誤的時(shí)間依賴A＊最短路徑算法

鄭年波1,陸 鋒1,李清泉2,段瀅瀅1

1.中國科學(xué)院地理科學(xué)與資源研究所資源與環(huán)境信息系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室,北京100101;2.武漢大學(xué)交通研究中心,湖北武漢430079

建立基于路段的時(shí)間依賴網(wǎng)絡(luò)模型,將轉(zhuǎn)向延誤時(shí)間引入到FIFO(先進(jìn)先出)條件的定義中,并給出滿足FIFO條件的路段到達(dá)時(shí)間和轉(zhuǎn)向延誤時(shí)間計(jì)算式。通過將時(shí)間因子引入到啟發(fā)式評價(jià)函數(shù)中,發(fā)展了基于路段標(biāo)號的時(shí)間依賴A＊最短路徑算法。試驗(yàn)表明,所提出的算法能預(yù)測并回避即將發(fā)生的交通擁堵,有效節(jié)省用戶的出行時(shí)間。而其平均計(jì)算時(shí)間僅比傳統(tǒng)算法增加10%左右。由于不再需要進(jìn)行頻繁的路徑重優(yōu)化,該算法能提高路徑規(guī)劃的整體效率。

路徑規(guī)劃;最短路徑;A＊算法;時(shí)間依賴網(wǎng)絡(luò);轉(zhuǎn)向延誤

1 引 言

利用交通信息進(jìn)行動態(tài)路徑規(guī)劃是車輛導(dǎo)航、位置服務(wù)等研究領(lǐng)域的重要課題[1]。而目前相關(guān)算法只是簡單地將當(dāng)前交通信息作為路段權(quán)值調(diào)整的系數(shù),于出發(fā)前利用各種啟發(fā)式最短路徑算法計(jì)算最優(yōu)行駛路徑[2],并于行駛過程中利用實(shí)時(shí)接收的交通信息進(jìn)行路徑的重計(jì)算[3]。它們忽略了路段行程時(shí)間依賴于進(jìn)入該路段的時(shí)刻這一現(xiàn)實(shí),不能從出行全局上為用戶考慮,導(dǎo)致頻繁的路徑重計(jì)算,進(jìn)而影響導(dǎo)航系統(tǒng)的整體效率。有必要研究時(shí)間依賴的最短路徑算法。

時(shí)間依賴最短路徑問題將路段行程時(shí)間建模為時(shí)間依賴的變量,并在滿足先進(jìn)先出條件的情況下,可以通過改進(jìn)的Dijkstra、A＊等標(biāo)號設(shè)定(label-setting,LS)算法來求解[4-9]。然而,這些改進(jìn)的算法普遍缺乏對交叉口轉(zhuǎn)向延誤的考慮。事實(shí)上,交叉口轉(zhuǎn)向引起的時(shí)間延誤可以達(dá)到全部行駛時(shí)間的17%～35%[10]。同一交叉口不同的轉(zhuǎn)向通常有不同的延誤時(shí)間,這與LS算法單一標(biāo)號的性質(zhì)相矛盾,基于節(jié)點(diǎn)標(biāo)號的LS算法不再有效[11]。針對此問題,路段標(biāo)號和對偶圖法是兩種有效的解決策略[10-17]。這些方法都基于靜態(tài)網(wǎng)絡(luò),缺乏對交通網(wǎng)絡(luò)時(shí)間依賴特性的考慮。事實(shí)上,轉(zhuǎn)向延誤的存在影響了時(shí)間依賴網(wǎng)絡(luò)的FIFO條件,需要考慮對之進(jìn)行重新定義。

本文面向帶轉(zhuǎn)向延誤的時(shí)間依賴最短路徑問題,定義基于路段的時(shí)間依賴網(wǎng)絡(luò)以及考慮轉(zhuǎn)向延誤的FIFO條件,發(fā)展基于路段標(biāo)號的時(shí)間依賴A＊算法。

2 基于路段的時(shí)間依賴網(wǎng)絡(luò)模型

基于路段的時(shí)間依賴網(wǎng)絡(luò)模型定義如下: GL=(L,U,W,D)。其中,L={0,1,…,n-1}表示有向路段集。U?{(i,j)|(i,j)∈L×L,e(i)=s(j)}表示轉(zhuǎn)向集,其中e(i)表示路段 i的終止節(jié)點(diǎn),s(j)表示路段j的起始節(jié)點(diǎn)。W={wi(t)|i∈L,t∈T}表示時(shí)間依賴路段行程時(shí)間集,其中wi(t)表示t時(shí)刻在路段i上的行程時(shí)間,T表示時(shí)間集。D= {dij(t)|(i,j)∈U,t∈T}表示時(shí)間依賴轉(zhuǎn)向延誤時(shí)間集,其中,dij(t)表示 t時(shí)刻于交叉口(即e(i)或s(j))處由路段i轉(zhuǎn)向路段j的延誤時(shí)間。

設(shè) ai(t)表示t時(shí)刻從節(jié)點(diǎn)s(i)出發(fā)沿路段i到達(dá)其相鄰節(jié)點(diǎn)e(i)的時(shí)間,有ai(t)=t+wi(t)。設(shè)rij(t)表示t時(shí)刻從節(jié)點(diǎn)s(i)出發(fā)沿路段i轉(zhuǎn)入相鄰路段j的時(shí)間,有

設(shè) p={i1,i2,…,im}(m>1)為路段 i1到路段im的一條路徑,其中,e(i1)=s(i2),…,e(im-1) =s(im),則其到達(dá)時(shí)間定義如下

設(shè) P(o,d)為路段 o到路段 d的所有路徑, EAod(t)為 t時(shí)刻從路段o出發(fā)最早到達(dá)路段 d的時(shí)間,則有 EAod(t)=min{ap(t):p∈P(o,d)}。計(jì)算 EAod(t)的過程也就是求解 o-d時(shí)間最短路徑的過程。

FIFO條件 對于網(wǎng)絡(luò)中的每一個轉(zhuǎn)向(i,j)∈U,如果 rij(t)非減,即

則稱網(wǎng)絡(luò)滿足先進(jìn)先出(first in first out, FIFO)條件。文獻(xiàn)[4]指出,FIFO網(wǎng)絡(luò)中的最短路徑問題可以使用改進(jìn)的Dijkstra、A＊等算法來求解。根據(jù)公式(1),要使不等式(3)成立,則路段到達(dá)時(shí)間函數(shù)ai(t)與轉(zhuǎn)向延誤函數(shù)dij(t)必須同時(shí)滿足FIFO條件,即

3 滿足FIFO條件的路段到達(dá)時(shí)間與轉(zhuǎn)向延誤時(shí)間

3.1 路段到達(dá)時(shí)間

在對路段i∈L的交通狀況進(jìn)行建模時(shí),通常將連續(xù)時(shí)間 T劃分成若干時(shí)段[t0,t1),…,[tf-1, tf),并認(rèn)為每個時(shí)段[tk,tk+1)內(nèi)的交通流速度 vk穩(wěn)定。這樣,路段上的一個行程可能跨越速度值不同的多個時(shí)段,其滿足FIFO條件的到達(dá)時(shí)間ai(t)計(jì)算如下(其中 l表示路段i的長度)[5]

式中,

3.2 轉(zhuǎn)向延誤時(shí)間

在處理轉(zhuǎn)向延誤時(shí)間時(shí),也將連續(xù)時(shí)間 T離散化為多個時(shí)段[t0,t1),…,[th-1,th),并認(rèn)為每個時(shí)段[tk,tk+1)內(nèi)的平均延誤時(shí)間恒定為 ck(ck值的確定是交通工程學(xué)中交通流理論研究的重要內(nèi)容)。這樣,車輛實(shí)際的轉(zhuǎn)向延誤時(shí)間可通過如下公式來計(jì)算

此計(jì)算過程考慮了跨越兩個時(shí)段的情況(現(xiàn)實(shí)應(yīng)用中轉(zhuǎn)向等待不太可能跨越兩個以上時(shí)段),能保證先排隊(duì)的車輛先轉(zhuǎn)入下一條路段,即滿足FIFO條件。

4 基于路段標(biāo)號的時(shí)間依賴A＊算法

A＊最短路徑算法以啟發(fā)式評估函數(shù)作為節(jié)點(diǎn)標(biāo)號,通過賦予位于最短路徑上可能性高的節(jié)點(diǎn)以高的優(yōu)先級,來達(dá)到縮減搜索空間的目的[2]。在基于路段的時(shí)間依賴網(wǎng)絡(luò)中,啟發(fā)式評估函數(shù)定義為

式中,t為出發(fā)時(shí)間;ap→i(t)為沿評估路徑 p到達(dá)當(dāng)前路段i的時(shí)間(根據(jù)式(2)計(jì)算);e(i,d)(ap→i(t))為ap→i(t)時(shí)刻從當(dāng)前路段i到目標(biāo)路段d的行程時(shí)間的估計(jì)。啟發(fā)式函數(shù) e(i,d)(ap→i(t))的設(shè)定則是一個事關(guān)算法效率的關(guān)鍵性問題。如果其值不超過相應(yīng)的實(shí)際最小行程時(shí)間(即滿足可納性),則能保證找到數(shù)學(xué)最優(yōu)解[7]。鑒于此,本文令

式中,D(i,d)為當(dāng)前路段 i到目標(biāo)路段d的歐式距離(通過節(jié)點(diǎn)e(i)和節(jié)點(diǎn)e(d)的坐標(biāo)計(jì)算而得); Vmax為所有路段最大可能的行車速度。

基于路段標(biāo)號的時(shí)間依賴A＊(time-dependent A＊,TDA＊)算法的基本思想如下:從起始路段出發(fā),循環(huán)從候選路段集中選取標(biāo)號 Fi(t)最小的路段擴(kuò)展生成后續(xù)路段并更新其標(biāo)號值,標(biāo)號更新后的路段作為下一次的選取對象再插入到候選路段集中。設(shè)o為起始路段,d為終止路段,t為從節(jié)點(diǎn)s(o)出發(fā)的時(shí)間,Pi為路段i在路徑上的直接前驅(qū)路段,Q為候選路段集,R為永久標(biāo)號路段集(到此集合中的路段的最短路徑已經(jīng)找到),則TDA＊算法的流程如下(其中,A rrival(i,t)為基于式(5)的路段到達(dá)時(shí)間計(jì)算函數(shù),Turn(i,j,t)為基于式(6)的轉(zhuǎn)向延誤時(shí)間計(jì)算函數(shù)):

1.初始化。令 ap→o=A rrival(o,t),Fo= ap→o+D(o,d)/Vmax,Fj=ap→j= ∞ ?j≠o,Po= -1,Q={o}。

2.路段選擇。從候選路段集Q中選出Fi值最小的路段i,并將之永久標(biāo)號,即:

如果i==d,則目標(biāo)路段已找到,循環(huán)終止。否則:

3.路段擴(kuò)展。對于路段i的每一條后繼路段j∈L,(i,j)∈U,如果它還未永久標(biāo)記,即 j?R,且ap→i+Turn(i,j,ap→i)+A rrival(j,ap→i+Turn(i, j,ap→i))+D(j,d)/Vmax

4.搜索終止。如果所有路段都擴(kuò)展完,即Q=?,則終止循環(huán);否則轉(zhuǎn)向步驟2。

5 試 驗(yàn)

本文在課題組自主開發(fā)的城市公眾出行路徑規(guī)劃服務(wù)系統(tǒng)為試驗(yàn)平臺(雙核CPU 1.6 GHz,內(nèi)存1.0 GB,操作系統(tǒng)Windows XP professional SP3)上對所提出的算法進(jìn)行了驗(yàn)證與測試。

5.1 數(shù)據(jù)準(zhǔn)備

試驗(yàn)路網(wǎng)采用北京市四環(huán)以內(nèi)雙線表達(dá)的導(dǎo)航路網(wǎng),共有路段25 602條(交叉路口處的虛擬路段和虛擬節(jié)點(diǎn)概化為單一的拓?fù)涔?jié)點(diǎn))。交通數(shù)據(jù)采用北京市2007年7、8、9三個月的以5 min為周期的浮動車實(shí)測車速數(shù)據(jù),一天分為288個時(shí)段?？紤]到交通流的周期性變化規(guī)律,對所有屬于同一日期類別同一時(shí)段的速度值進(jìn)行平均化處理,形成了從星期一到星期日的7個速度數(shù)據(jù)集。目前的交通數(shù)據(jù)中,共有4 929條路段有交通信息,基本上覆蓋了主要道路。而對于交通信息不能覆蓋的路段,根據(jù)道路類型和進(jìn)入時(shí)間設(shè)置默認(rèn)速度值如表1所示。

表1 預(yù)定義的道路速度Tab 1 Predefined speeds on different road types /(km/h)

另外,考慮到準(zhǔn)確可用的轉(zhuǎn)向延誤數(shù)據(jù)難以獲得,作者從交叉口綠信比的角度考慮,以時(shí)段和轉(zhuǎn)向類型為依據(jù),為所有轉(zhuǎn)向建立了一個簡單的延誤模型:fij(t)=0.5×g(t,ty peij)(見3.2節(jié))。其中,0.5表示交叉口等待的概率,g(t,ty peij)的取值如表2所示。

表2 簡單的時(shí)間依賴轉(zhuǎn)向延誤模型Tab.2 A naive model for time-dependent turn delays /min

5.2 算法準(zhǔn)備

TDA＊算法使用四叉堆優(yōu)先級隊(duì)列來實(shí)現(xiàn)候選路段集[18],并基于經(jīng)驗(yàn)將所有路段的最大可能行車速度設(shè)置為60 km/h。為了算法比較的需要,作者實(shí)現(xiàn)了 RTA＊(real-time A＊)算法和RTA＊_M算法。RTA＊算法是指僅考慮出發(fā)時(shí)刻交通信息的A＊算法,它與靜態(tài)A＊算法的區(qū)別僅在于以當(dāng)前交通信息而不是長度/限速作為路段的權(quán)值。RTA＊_M算法是指整個導(dǎo)航過程中的多次RTA＊算法調(diào)用。該算法的基本流程如下:①出發(fā)前利用RTA＊算法計(jì)算一條最優(yōu)路徑;②沿著規(guī)劃路徑行進(jìn),每當(dāng)有新的交通信息到來時(shí)(根據(jù)歷史交通數(shù)據(jù)進(jìn)行模擬,以每5 min為一個周期),調(diào)用 RTA＊算法計(jì)算新的路徑;③步驟②循環(huán)直至抵達(dá)目的地。RTA＊_M算法的計(jì)算時(shí)間為多次RTA＊算法計(jì)算時(shí)間的和,路徑為多次重計(jì)算后完整的行車路徑。

5.3 試驗(yàn)結(jié)果與算法分析

為了驗(yàn)證TDA＊算法的有效性,選取北辰東路為起始路段,翠微路為終止路段,設(shè)置出發(fā)時(shí)間為周二上午7:00和8:00,分別利用 TDA＊算法和RTA＊算法進(jìn)行計(jì)算,結(jié)果如圖1和圖2所示。

圖1 TDA＊算法與RTA＊算法計(jì)算結(jié)果的比較(出發(fā)時(shí)間:7:00)Fig.1 Comparison of computational results of TDA＊and RTA＊(departure time:7:00)

圖2 TDA＊算法與RTA＊算法計(jì)算結(jié)果的比較(出發(fā)時(shí)間:8:00)Fig.2 Comparison of computational results of TDA＊and RTA＊(departure time:8:00)

從圖1可以看出,7:00出發(fā)時(shí),TDA＊算法預(yù)測出車輛到達(dá)時(shí)刻三環(huán)路上將發(fā)生交通擁堵,因此建議繞道四環(huán)以避之。而RTA＊算法由于只考慮當(dāng)前時(shí)刻的交通狀況,因此當(dāng)車輛沿其規(guī)劃的路徑到達(dá)三環(huán)路上時(shí),將會遇到交通擁堵。

從圖2可以看出,8:00出發(fā)時(shí),三環(huán)路上正好發(fā)生交通擁堵,RTA＊算法基于此建議走四環(huán)以避之,而事實(shí)上,當(dāng)車輛到達(dá)三環(huán)路時(shí),交通擁堵狀況可能已經(jīng)緩解。與此相反,TDA＊算法在出發(fā)時(shí)就預(yù)測到三環(huán)路上擁堵狀況即將緩解的趨勢,因此建議一條看似擁堵而實(shí)際并不擁堵的路徑(即三環(huán)路),有效地避免了不必要的繞道。

為了測試TDA＊算法的效率與精度,以周二上午7:30為出發(fā)時(shí)間,從網(wǎng)絡(luò)中任意選取30對OD路段,分別利用 TDA＊算法、RTA＊算法和RTA＊_M算法計(jì)算每對OD間的時(shí)間最短路徑。結(jié)果如圖3、圖4和圖5所示(橫軸表示30條按長度從小到大排序的路徑)。

圖3 TDA＊算法與RTA＊_M算法所計(jì)算路徑行程時(shí)間的比較Fig.3 Comparison of travel times of computational paths of TDA＊and RTA＊_M

圖4 TDA＊算法與RTA＊算法計(jì)算時(shí)間的比較Fig.4 Comparison of computational times of TDA＊and RTA＊

從圖3可以看出,總體而言,相比于RTA＊_ M算法,TDA＊算法所計(jì)算路徑的行程時(shí)間更短。不過這種優(yōu)勢并不明顯,主要原因在于: RTA＊_M算法也考慮了回避交通擁堵的情況,在經(jīng)過多次路徑調(diào)整后,RTA＊_M算法所得路徑的行程時(shí)間比 TDA＊算法所得路徑的行程時(shí)間多得有限,這種現(xiàn)象在路段行車速度長時(shí)間沒有大的變化的情況下,表現(xiàn)得更為明顯。當(dāng)然,交通信息覆蓋率不高、行程時(shí)間預(yù)測模型與轉(zhuǎn)向延誤模型存在一定的誤差等也是一部分影響因素,但影響大小的定量測試需要高質(zhì)量交通數(shù)據(jù)以及準(zhǔn)確的行程時(shí)間預(yù)測模型和轉(zhuǎn)向延誤計(jì)算模型的支持。

圖5 TDA＊算法與RTA＊_M算法計(jì)算時(shí)間的比較Fig.5 Comparison of computational times of TDA＊and RTA＊_M

從圖4可以看出,TDA＊算法的計(jì)算時(shí)間比RTA＊算法略有增加,平均幅度大約為10%。其中多出的時(shí)間主要用于路段到達(dá)時(shí)間和轉(zhuǎn)向延誤時(shí)間的計(jì)算。

從圖5可以看出,TDA＊算法的計(jì)算時(shí)間遠(yuǎn)少于RTA＊_M算法。原因在于導(dǎo)航過程中需要多次調(diào)用RTA＊算法以進(jìn)行路徑的優(yōu)化與重優(yōu)化,而TDA＊算法由于預(yù)先考慮了到達(dá)時(shí)刻路段的交通狀況,整個導(dǎo)航過程只需一次調(diào)用即可?？梢?TDA＊算法有助于降低導(dǎo)航過程中路徑規(guī)劃的頻率,從而提高導(dǎo)航系統(tǒng)的整體效率。

6 結(jié) 論

面向帶轉(zhuǎn)向延誤的時(shí)間依賴最短路徑問題,本文通過定義基于路段的時(shí)間依賴網(wǎng)絡(luò)模型,并將轉(zhuǎn)向延誤引入到FIFO條件的定義中,發(fā)展了基于路段標(biāo)號的時(shí)間依賴A＊最短路徑算法。該算法能預(yù)測并回避即將發(fā)生的交通擁堵,有效節(jié)省用戶出行時(shí)間、提高導(dǎo)航系統(tǒng)整體運(yùn)行效率,具有較強(qiáng)的實(shí)用價(jià)值。

TDA＊算法的精度和可用性與行程時(shí)間數(shù)據(jù)和轉(zhuǎn)向延誤數(shù)據(jù)的準(zhǔn)確性直接相關(guān),本文只是簡單對歷史交通數(shù)據(jù)作了均化處理,轉(zhuǎn)向延誤使用的也僅是經(jīng)驗(yàn)值。在后續(xù)工作中將深入探討準(zhǔn)確可用的路段行程時(shí)間預(yù)測模型與交叉口轉(zhuǎn)向延誤計(jì)算模型。

[1] LU Feng,ZHENG Nianbo,DUAN Yingying,et al.Travel Information Services:State of the Art and Discussion on Crucial Technologies[J].Journal of Image and Graphics, 2009,14(7):1219-1229.(陸鋒,鄭年波,段瀅瀅,等.出行信息服務(wù)關(guān)鍵技術(shù)研究進(jìn)展與問題探討[J].中國圖象圖形學(xué)報(bào),2009,14(7):1219-1229.)

[2] FU L,SUN D,RILETT L R.Heuristic Shortest Path Algorithms for Transportation Applications:State of the Art[J].Computers&Operation Research,2006,33(11): 3324-3343.

[3] HUANG B,WU Q,ZHAN F B.A Shortest Path Algorithm with Novel Heuristics for Dynamic Transportation Networks[J]. InternationalJournalof Geographical Information Science,2007,21(6):625-644.

[4] KAUFMAN D E,SMITH R L.Fastest Paths in Timedependent Networks for Intelligent Vehicle-Highway Systems Application[J].Journal of Intelligent Transportation Systems,1993,1(1):1-11.

[5] SUNG K,BELL M G H,SEONG M,et al.Shortest Paths in a Network with Time-dependent Flow Speeds[J].European Journal of Operational Research,2000,121(1): 32-39.

[6] HORN M.Efficient Modeling of Travel in Networks with Time-Varying Link Speeds[J].Networks,2000,36(2): 80-90.

[7] CHABINI I,LAN S.Adaptations of the A＊Algorithm for the Computation of Fastest Paths in Deterministic Discrete-Time DynamicNetworks[J]. IEEE Transactions on Intelligent Transportation Systems,2002,3(1):60-74.

[8] KANOULAS E,DU Y,XIA T,et al.Finding Fastest Paths on a Road Network with Speed Patterns[C]∥Proc of the 22nd International Conference on Data Engineering. Washington D C:IEEE Computer Society,2006.

[9] NANNICINI G,LIBERTI L.Shortest Paths on Dynamic Graphs[J]. International Transactions in Operational Research,2008.15(5):551-564.

[10] HAN Gang,J IANGJie,CHEN Jun,et al.An Arc Based Dijkstra Algorithm for Road Turning Penalty in Vehicle Navigation System[J].Acta Geodaetica et Cartographic Sinica,2002,31(4):366-368.(韓剛,蔣捷,陳軍,等.車載導(dǎo)航系統(tǒng)中顧及道路轉(zhuǎn)向限制的路段Dijkstra算法[J].測繪學(xué)報(bào),2002,31(4):366-368.)

[11] REN Gang,WANG Wei,DENG Wei.Shortest Path Problem with Turn Penalties and Prohibitions and Its Solutions[J].Journal of Southeast University:Natural Science Edition,2004,34(1):104-108.(任剛,王煒,鄧衛(wèi).帶轉(zhuǎn)向延誤和限制的最短路徑問題及其求解方法[J].東南大學(xué)學(xué)報(bào):自然科學(xué)版,2004,34(1): 104-108.)

[12] CALDWELL T.On Finding Minimum Routes in a Network with Turn Penalties[J].Communications of the ACM, 1961,4(2):108.

[13] ZHENG Nianbo,LI Qingquan,XU Jinghai,et al.A BidirectionalHeuristic ShortestPath Algorithm with Turn Prohibitionsand Delays[J]. Geomaticsand Information Science of Wuhan University,2006,31(3): 256-259.(鄭年波,李清泉,徐敬海,等.基于轉(zhuǎn)向限制和延誤的雙向啟發(fā)式最短路徑算法[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2006,31(3):256-259.)

[14] GAO Song,LU Feng.An Arc-labeling Shortest Time Path Algorithm[J].Geo-Information Science,2008,10 (5):604-610.(高松,陸鋒.基于路段標(biāo)記的交通網(wǎng)絡(luò)時(shí)間最短路徑算法[J].地球信息科學(xué),2008,10(5): 604-610.)

[15] GUTIéRREZ E,MEDAGLIA A L.Labeling Algorithm for the Shortest Path Problem with Turn Prohibitions with Application to Large-scaleRoad Networks[J]. Annals of Operations Research,2007,157(1):169-182.

[16] A?EZ J,DE LA BARRA T,PéREZ B.Dual Graph Representation of Transport Networks[J].Transportation Research Part B:Methodological,1996,30(3): 209-216.

[17] WINTER S.Modeling Costs of Turns in Route Planning [J].GeoInformatica,2002.6(4):345-361.

[18] LU Feng,LU Dongmei,CUI Weihong.Improved Dijkstra Algorithm Based on Quad-Heap PriorityQueueand Inverse Adjacent List[J].Journal of Image and Graphics, 1999,4A(12):1044-1050.(陸鋒,盧冬梅,崔偉宏.基于四叉堆優(yōu)先級隊(duì)列及逆鄰接表的改進(jìn)型Dijkstra算法[J].中國圖象圖形學(xué)報(bào),1999,4A(12):1044-1050.)

The Adaption of A＊Algorithm for Least-time Paths in Time-dependent Transportation Networks with Turn Delays

ZHENGNianbo1,LU Feng1,LI Qingquan2,DUAN Yingying1
1.State Key Laboratory of Resources and Environmental Information System,Institute of Geographic Sciences and Natural Resources Research,Chinese Academy of Sciences,Beijing 100101,China;2.Transportation Research Center,Wuhan University, Wuhan 430079,China

A link-based time-dependent network model was built by introducing the turn delay time into the definition of“first in first out(FIFO)”condition.A link-labelling time-dependent A＊shortest path algorithm is developed by adapting temporally the heuristic evaluationfunction and using Euclidian distance divided by maximum possible driving speed as the heuristic evaluator.An experiment on the real road network showed that the proposed algorithm is capable of forecasting and bypassing those forthcoming traffic congestions and then shortening travel time,only with a cost of about 10%more computational time than the traditional algorithms.Moreover,it is able to improve overall efficiency of route planning heavily because the frequent path re-optimization processes are no longer needed.

route planning;shortest path;A＊algorithm;time-dependent network;turn delay

ZHENG Nianbo(1979—),male,postdoctoral,majors in geographic information systems for transportation,intelligent transportation systems and spatial information services.

1001-1595(2010)05-0534-06

P208

A

國家863計(jì)劃(2007AA12Z241);國家自然科學(xué)基金(40871184,40830530);中國博士后基金(20090450563)

(責(zé)任編輯:叢樹平)

2009-09-14

2010-01-07

鄭年波(1979—),男,博士后,主要從事GIS-T、ITS、空間信息服務(wù)等研究。

E-mail:zhengnb@lreis.ac.cn