大數(shù)據(jù)環(huán)境下的動態(tài)最短路徑算法*

徐建閩　王鈺　林培群

(華南理工大學(xué) 土木與交通學(xué)院， 廣東 廣州 510640)

?

大數(shù)據(jù)環(huán)境下的動態(tài)最短路徑算法*

徐建閩王鈺林培群

(華南理工大學(xué) 土木與交通學(xué)院， 廣東 廣州 510640)

摘要：數(shù)量龐大、類型復(fù)雜的海量數(shù)據(jù)給智能交通帶來了新的挑戰(zhàn).文中對交通誘導(dǎo)中的動態(tài)最短路徑問題進(jìn)行了研究,提出了動態(tài)交通網(wǎng)絡(luò)數(shù)學(xué)模型,在此基礎(chǔ)上設(shè)計了考慮交叉口延時的動態(tài)最短路徑算法,并使用當(dāng)前流行的大數(shù)據(jù)技術(shù),設(shè)計了基于HaLoop MapReduce的動態(tài)最短路徑并行計算模型,最后在連續(xù)流智能交通管控平臺上對算法進(jìn)行了測試.實驗結(jié)果表明，文中設(shè)計的算法和基于大數(shù)據(jù)的并行計算模型可以有效地查找到大規(guī)模路網(wǎng)中的動態(tài)最短路徑,同時能很好地滿足實時性需求.

關(guān)鍵詞：大數(shù)據(jù);動態(tài)最短路徑算法;交叉口延誤;路徑誘導(dǎo)

交通誘導(dǎo)系統(tǒng)(TRGS)是智能交通系統(tǒng)(ITS)研究的一個重要方面,也是改善城市交通狀況的最佳途徑之一.隨著智能交通系統(tǒng)、IT技術(shù)以及網(wǎng)絡(luò)與通信技術(shù)的發(fā)展,動態(tài)路徑誘導(dǎo)系統(tǒng)(DRGS)逐漸成為人們關(guān)注的熱點.DRGS基于道路的實時交通狀態(tài),為出行者提供最少出行時間的路徑.

由于路段和交叉口的交通阻抗隨時間不斷變化,因此城市交通網(wǎng)絡(luò)是動態(tài)網(wǎng)絡(luò)或時間依賴網(wǎng)絡(luò)(TDN).同時,交叉口延時以及交通狀態(tài)的隨機性造成了城市路網(wǎng)的非先進(jìn)先出(FIFO)性.如何在這些復(fù)雜限制條件下高效求解最優(yōu)路徑,是動態(tài)路徑誘導(dǎo)問題研究的核心.目前,國內(nèi)外對動態(tài)最短路徑(DSP)問題的研究主要集中在如何對動態(tài)信息進(jìn)行處理與如何提高算法的實時性這兩個關(guān)鍵性問題上.

由于數(shù)據(jù)資源和計算效率的限制,目前的TRGS無法做到準(zhǔn)確、及時的動態(tài)誘導(dǎo).但隨著智能移動設(shè)備的大量應(yīng)用以及城市道路基礎(chǔ)設(shè)施的不斷完善,這些設(shè)備和設(shè)施產(chǎn)生了海量異構(gòu)的實時數(shù)據(jù),為實時的動態(tài)路徑誘導(dǎo)提供了數(shù)據(jù)基礎(chǔ).然而,由于求解動態(tài)最短路徑的模型復(fù)雜,針對海量數(shù)據(jù)的實時計算與分析在傳統(tǒng)數(shù)據(jù)技術(shù)架構(gòu)下很難實現(xiàn).

大數(shù)據(jù)技術(shù)是新的海量數(shù)據(jù)處理技術(shù),在很多領(lǐng)域都取得了顯著的應(yīng)用效果,但在智能交通領(lǐng)域的應(yīng)用還剛剛起步.然而大數(shù)據(jù)技術(shù)使得及時獲取城市路網(wǎng)中實時的路段行程時間與交叉口延誤時間成為可能,也為大規(guī)模路網(wǎng)環(huán)境下的動態(tài)最短路徑的計算提供高性能的分析與處理能力.文中擬在大數(shù)據(jù)環(huán)境下建立一套完整的理論和算法,以解決城市交通的動態(tài)最短路徑求解問題.

1相關(guān)研究

目前基本的最短路徑(SP)問題已有大量成熟的算法,如標(biāo)號設(shè)定法、標(biāo)號修改法、動態(tài)規(guī)劃法、啟發(fā)式和雙向啟發(fā)式算法、基于流體神經(jīng)網(wǎng)絡(luò)的算法等[1- 4].然而,由于路網(wǎng)交通的復(fù)雜性以及交通流狀態(tài)的動態(tài)性,基本的SP算法無法有效解決交通系統(tǒng)中的路徑誘導(dǎo)問題.

在基本SP算法的基礎(chǔ)上,很多學(xué)者對DSP問題展開了研究.Hall[5]首次研究了交通網(wǎng)中路段通行時間是隨機并且依賴于時間情況下的最短路徑問題.Ziliaskopulos等[6]提出了動態(tài)最短路徑問題.

針對動態(tài)網(wǎng)絡(luò)的建模,Chabini等[7- 8]提出將時間離散化處理,即將時間區(qū)域劃分為一系列時間片段,假定路段行駛時間在一個時間片段內(nèi)保持穩(wěn)定,這樣動態(tài)網(wǎng)絡(luò)可以建模為靜態(tài)模型.針對動態(tài)網(wǎng)絡(luò)最短路徑的搜索算法,當(dāng)網(wǎng)絡(luò)的權(quán)值都服從FIFO原則的一致性假設(shè)時,可以用擴展的靜態(tài)SP算法(如Dijkstra算法等)來求解[9].當(dāng)網(wǎng)絡(luò)的權(quán)值不滿足FIFO條件時,靜態(tài)SP算法都不再適用.Pallottino等[10]提出了一個適用于非FIFO條件的DSP算法范例——Chrono-SPT,給出了無環(huán)圖的最小代價路徑問題的一般解法,并對其理論上的時間復(fù)雜度進(jìn)行了初步分析.Orda和Rom[11]給出了在節(jié)點允許等待的非FIFO網(wǎng)絡(luò)中,節(jié)點最優(yōu)等待時間和最優(yōu)路徑的計算方法.由于城市道路的交叉口處不允許隨個人意愿等待,因此這種方法不能用于城市路網(wǎng)的動態(tài)最短路徑計算.譚國真等[12]研究了沒有任何限制性條件下的動態(tài)網(wǎng)絡(luò)模型,并提出了適用于非FIFO網(wǎng)絡(luò)的SPTDN算法.SPTDN算法提供了一般性的計算方法,其計算效率不是最優(yōu)的,而且該算法是從后往前計算的,所以限制了某些應(yīng)用.

為了解決包含有交叉口延誤和轉(zhuǎn)向限制的SP問題,國內(nèi)外學(xué)者提出了多種方法.擴展網(wǎng)絡(luò)法[13]與對偶網(wǎng)絡(luò)法[14]將原網(wǎng)絡(luò)進(jìn)行一定轉(zhuǎn)換,然后采用基本的SP算法求解.文獻(xiàn)[15]中提出了一個基于弧標(biāo)號的標(biāo)號修正算法.但是目前對于動態(tài)網(wǎng)絡(luò)的交叉口延誤和轉(zhuǎn)向限制的研究還很少.

隨著人工智能研究的發(fā)展,一些新的智能算法不斷被應(yīng)用在最短路徑的求解中,主要包括遺傳算法[16]、神經(jīng)網(wǎng)絡(luò)算法[17]、蟻群算法[18]、人工免疫算法[19]、人工魚群算法[20]、粒子群算法[21]等.楊慶芳等[22]提出用基于MapReduce的并行遺傳算法解決靜態(tài)最短路徑問題.Wen等[23]提出用遺傳算法來求解動態(tài)最短路徑.由于智能算法本身比較復(fù)雜、計算量大,因此以上算法都存在搜索時間長或者計算精度低的問題.

綜上所述,目前大多數(shù)DSP算法的前提是FIFO網(wǎng)絡(luò),且沒有考慮交叉口延誤與轉(zhuǎn)向限制,這與實際的交通網(wǎng)絡(luò)不相符.同時,DSP的計算對系統(tǒng)在大負(fù)荷情況下的實時性要求非常高,這也是實現(xiàn)動態(tài)路徑誘導(dǎo)面臨的瓶頸問題.

2動態(tài)交通網(wǎng)絡(luò)模型

2.1　動態(tài)交通網(wǎng)絡(luò)數(shù)學(xué)模型

根據(jù)利用多種交通感知技術(shù)所獲取的海量交通數(shù)據(jù),文中建立了更加精確的動態(tài)交通網(wǎng)絡(luò)數(shù)學(xué)模型.動態(tài)路徑問題是非馬爾可夫(Markov)性的,因此動態(tài)網(wǎng)絡(luò)的建模方法與靜態(tài)網(wǎng)絡(luò)不同.此外,在城市路網(wǎng)中,由于交叉口轉(zhuǎn)向而引起的時間延遲可以達(dá)到全部行程時間的17%～35%[24],交叉口延誤已經(jīng)成為DSP問題的一個重要影響因素.文中給出的動態(tài)交通網(wǎng)絡(luò)模型滿足非馬爾可夫性質(zhì),同時描述了交叉口不同流向的實時轉(zhuǎn)向延誤,對城市交通流的運行進(jìn)行了精確的刻畫,展現(xiàn)了城市路網(wǎng)交通的實時性和隨機性.

將動態(tài)交通網(wǎng)絡(luò)映射成一個連通的動態(tài)帶權(quán)有向圖，G=(V，A，W，D).V={v1,v2，…,vn},為有限節(jié)點集,表示交通網(wǎng)絡(luò)上所有節(jié)點,由道路的交叉口或者道路的起點/終點抽象而成.A?V={ai,j|i≠j,vi,vj∈V},為有限弧集,表示網(wǎng)絡(luò)上所有有向邊,由道路線路抽象而成.W={wi,j(t)|ai,j∈A,t∈T},為弧權(quán)集合,表示動態(tài)路段行程時間.wi,j(t)表示t時刻從交叉口vi出發(fā)到達(dá)交叉口vj的行程時間.T=[t0,tu],是誘導(dǎo)時間范圍的閉區(qū)間.D={di,j,k(t)|(ai,j,aj,k∈A,t∈T)},為節(jié)點權(quán)集合,表示動態(tài)交叉口延誤時間.di,j,k(t)表示t時刻在交叉口vj處,由交叉口vi方向轉(zhuǎn)向交叉口vk方向的延遲時間.

對動態(tài)網(wǎng)絡(luò)的建模,文中采用將時間離散化處理的方式,把誘導(dǎo)的時間區(qū)域劃分為一系列較小的時間片段.時間區(qū)間T可以表示為T={t0,t0+Δ,t0+2Δ,…,t0+(q-1)Δ},Δ是時間間隔,q為時間片段數(shù).為了保證計算的精確性,取1 min作為一個時間片段,即各節(jié)點(源節(jié)點和目的節(jié)點除外)出發(fā)時間的間隔為1 min.根據(jù)交通網(wǎng)絡(luò)的特點,假定路段的行程時間與交叉口延時分別在5 min與1 min內(nèi)保持穩(wěn)定.

假如靜態(tài)網(wǎng)絡(luò)R的節(jié)點數(shù)為n,邊數(shù)為m,那么擴展為時間片段數(shù)為q的動態(tài)網(wǎng)絡(luò)G以后,網(wǎng)絡(luò)的規(guī)模和復(fù)雜性都發(fā)生了變化.其中,V×T={(vi,th)|vi∈V,th∈T}，表示節(jié)點的狀態(tài)空間,有序?qū)?vi,th)表示在th時刻的交叉口vi.A×T={(ai,j，th)|ai,j∈A，th∈T},表示弧的狀態(tài)空間,有序?qū)?ai,j,th)表示在th時刻的路段ai,j.與靜態(tài)網(wǎng)絡(luò)相比,動態(tài)網(wǎng)絡(luò)的規(guī)模擴大了,同時復(fù)雜性提高了.

2.2　動態(tài)交通網(wǎng)絡(luò)優(yōu)化模型

動態(tài)交通網(wǎng)絡(luò)的最短路徑是指在t時刻從源節(jié)點出發(fā)到達(dá)目的節(jié)點的所有路徑中走行時間最少的路徑.

定義在動態(tài)網(wǎng)絡(luò)中,設(shè)fi(t0)表示在t0(t0∈T)時刻從源節(jié)點v0出發(fā)到達(dá)節(jié)點vi的時間，pi(t)表示交叉口vi在t時刻的前置交叉口，dpi,i,j(t)表示t時刻在交叉口vi處由交叉口vi的前置交叉口pi(t)方向轉(zhuǎn)向交叉口vj方向的延遲時間.

fi(t0)+dpi,i,j(t0+fi(t0))).

車輛在t0+fi(t0)時刻到達(dá)交叉口vi,dpi,i,j(t0+fi(t0))表示從交叉口vi轉(zhuǎn)向交叉口vj方向所產(chǎn)生的時間延遲；wi,j(t0+fi(t0)+dpi,i,j(t0+fi(t0)))表示車輛經(jīng)歷了轉(zhuǎn)向延遲后,由交叉口vi到交叉口vj的行程時間.

3考慮交叉口延誤的動態(tài)最短路徑算法

通過對海量交通數(shù)據(jù)的精確提煉,利用大數(shù)據(jù)技術(shù)高效的處理能力,設(shè)計了改進(jìn)的DSP算法.算法按照時間順序從源節(jié)點開始依次處理各交叉口節(jié)點直到目的節(jié)點.每一個交叉口節(jié)點(源節(jié)點除外)都對應(yīng)一到多個到達(dá)時間.從出發(fā)時間開始以1 min作為一個時間間隔,記錄每個時間節(jié)點所對應(yīng)的交叉口節(jié)點.采用桶列表[10]B(B={B1,B2,…,Bn})來存放在不同時間節(jié)點將要被訪問的交叉口節(jié)點.Bh表示在th時刻將要被訪問的節(jié)點集合.如果出發(fā)時間為tθ,則Bθ={v0}為第一個桶,它只包含了源節(jié)點v0.處理過的節(jié)點被標(biāo)記為(節(jié)點,時間,前置節(jié)點)組合,“時間”為達(dá)到該節(jié)點的時刻,“前置節(jié)點”為對應(yīng)該時刻的前置節(jié)點.從桶中刪除被處理過的節(jié)點,當(dāng)所有桶為空時,算法結(jié)束.

算法步驟如下.其中,FS(vi)表示節(jié)點vi的緊后節(jié)點的集合,pj(th)表示節(jié)點vj在th時刻的緊前節(jié)點,vi(th)表示在th時刻的vi節(jié)點.Bh存儲th時刻將要選擇的節(jié)點.設(shè)源節(jié)點為v0,目的節(jié)點為vn,出發(fā)時間為tθ.

步驟1(初始化)

Bθ:={v0};

Bc:=?(?c≠θ);

h:=θ;

步驟2

SelectviFromBh

Bh:=Bh{vi};

Ifvi≠vn

For 每一個vj∈FS(vi)進(jìn)行如下操作:

ts=th+dpi,i,j(th)+wi,j(th+dpi,i,j(th));

pj(ts)=vi(th);

Ifvj?BsThenBs:=Bs∪vj;

End For

End If

End Select

IfBh≠? Then goto 步驟2;

步驟3

h=h+1;

goto 步驟2;

Else

算法結(jié)束.

文中提出的DSP算法既適合于FIFO網(wǎng)絡(luò),也適合于非FIFO網(wǎng)絡(luò),并兼顧了交叉口的延誤和轉(zhuǎn)向限制.在實時性方面,算法利用桶結(jié)構(gòu)提高了計算效率,同時便于在大數(shù)據(jù)處理平臺上進(jìn)行并行化處理.從前往后的計算方式有利于在求解過程中及時應(yīng)用最新的交通狀態(tài)數(shù)據(jù).

4基于Hadoop MapReduce的算法實現(xiàn)

實現(xiàn)動態(tài)路徑導(dǎo)航的瓶頸之一是算法對海量數(shù)據(jù)的處理能力.文中引進(jìn)大數(shù)據(jù)技術(shù)中的MapReduce計算模型,對誘導(dǎo)算法進(jìn)行并行化處理.Map-Reduce技術(shù)是一種簡潔的并行計算模型,用于大規(guī)模數(shù)據(jù)集的處理和分析,具有較高的處理速度和可靠性,在大數(shù)據(jù)計算領(lǐng)域得到了廣泛應(yīng)用.

MapReduce把一個作業(yè)的執(zhí)行過程分為Map和Reduce兩個階段.在Map階段,由Map函數(shù)對輸入的數(shù)據(jù)進(jìn)行處理,然后將結(jié)果寫到本地磁盤上;在Reduce階段,由Reduce函數(shù)處理Map階段的輸出,并將最終結(jié)果寫到分布式文件系統(tǒng)(HDFS)上.

目前流行的Hadoop MapReduce框架在處理迭代式流程時存在不足,表現(xiàn)在:每次迭代都需要重復(fù)創(chuàng)建所有作業(yè)(Job),并進(jìn)行磁盤讀寫和數(shù)據(jù)傳輸,使得每次迭代的代價非常高.因此Hadoop MapReduce不能很好地支持迭代式作業(yè).由于文中的DSP算法是迭代式計算,所以文中采用了對傳統(tǒng)Hadoop MapReduce進(jìn)行改進(jìn)后的HaLoop[25]框架.HaLoop設(shè)計了新的作業(yè)結(jié)構(gòu),使一個作業(yè)包含多個Map-Reduce任務(wù)對.此外,HaLoop將靜態(tài)變量緩存到各個任務(wù)服務(wù)器(TaskTracker),每次迭代重用這些數(shù)據(jù),大大減少了輸入輸出.HaLoop能高效地支持迭代和遞歸分析.

文中采用網(wǎng)絡(luò)分割的方法實現(xiàn)并行計算.首先使用Metis算法將路網(wǎng)進(jìn)行劃分,把網(wǎng)絡(luò)分割成P個子網(wǎng)，每個子網(wǎng)由1個HaLoop的工作(Worker)節(jié)點機器負(fù)責(zé).每個工作節(jié)點機器平均劃分n=N/P個網(wǎng)絡(luò)節(jié)點,其中N表示總節(jié)點數(shù).工作節(jié)點機器的計算任務(wù)是計算從出發(fā)時間開始,在某個時間段內(nèi)每1 min從路徑在所管轄子網(wǎng)的開始節(jié)點出發(fā),到達(dá)中間各節(jié)點以及子網(wǎng)邊界節(jié)點的時間,并記錄每個節(jié)點的到達(dá)時刻和相應(yīng)的前置節(jié)點.HaLoop的主(Master)節(jié)點機器最終將各個子網(wǎng)的計算結(jié)果進(jìn)行匯總,從目的節(jié)點的最早到達(dá)時間開始反推,得到整個網(wǎng)絡(luò)的動態(tài)最短路徑.根據(jù)歷史數(shù)據(jù),可以得到每對OD(出發(fā)地,目的地)最長的行程時間,將這個時間作為各個節(jié)點機器計算的時間范圍.例如:在9:00從節(jié)點v0出發(fā)到節(jié)點vn,歷史數(shù)據(jù)中最長的行程時間為120 min,那么每個工作節(jié)點機器承擔(dān)的計算任務(wù)是計算車輛在從9:00到11:00出發(fā)(每分鐘作為一個出發(fā)時間點),沿著子網(wǎng)內(nèi)路徑依次到達(dá)各節(jié)點的時間.此時,除源節(jié)點v0和目的節(jié)點vn外,路徑的其余節(jié)點都對應(yīng)120個出發(fā)時間.

(1)數(shù)據(jù)輸入

輸入數(shù)據(jù)分為兩種類型:一種是路段數(shù)據(jù);另一種是交叉口數(shù)據(jù).輸入文件中的每一行為1個路段或者交叉口在24 h內(nèi)的實時交通數(shù)據(jù).

路段數(shù)據(jù)結(jié)構(gòu)和交叉口數(shù)據(jù)結(jié)構(gòu)如圖1所示.

路段ID(始節(jié)點ID,終節(jié)點ID)以5min為間隔的行程時間序列相鄰交叉口序列

(a)路段數(shù)據(jù)結(jié)構(gòu)

(b)交叉口數(shù)據(jù)結(jié)構(gòu)

圖1路段數(shù)據(jù)結(jié)構(gòu)和交叉口數(shù)據(jù)結(jié)構(gòu)

Fig.1Date structure of road section and crossing

對于路段數(shù)據(jù),“鍵”為路段ID;“值”包括:(路段始節(jié)點ID,路段終節(jié)點ID),24 h內(nèi)以5 min為間隔的路段行程時間序列,相鄰交叉口ID序列.對于交叉口數(shù)據(jù),“鍵”為(交叉口ID,上游交叉口ID,轉(zhuǎn)向交叉口ID);“值”為24 h內(nèi)以1 min為間隔的轉(zhuǎn)向延遲時間序列.HaLoop將數(shù)據(jù)進(jìn)行切分后,根據(jù)節(jié)點所在的不同子網(wǎng),分發(fā)到多個Map任務(wù).

(2)Map階段

Map函數(shù)將所對應(yīng)子網(wǎng)的路段行程時間和交叉口延時數(shù)據(jù)以及計算時間范圍作為輸入,按照廣度優(yōu)先的原則對圖的結(jié)構(gòu)按照層次進(jìn)行遍歷.Map函數(shù)根據(jù)各時間段的行程時間和交叉口延誤數(shù)據(jù),計算到達(dá)下一交叉口的時間,最后產(chǎn)生鍵/值形式的中間值.中間值的“鍵”為到達(dá)交叉口的時間,“值”分別為交叉口ID、前驅(qū)交叉口ID、到達(dá)前驅(qū)交叉口的時間.

Map階段的輸出格式如圖2所示.

到達(dá)交叉口的時間交叉口ID前驅(qū)交叉口ID到達(dá)前驅(qū)交叉口的時間

圖2Map階段的輸出格式

Fig.2Output format of Map stage

(3)Reduce階段

HaLoop將所有具有相同“鍵”的“值”集合在一起傳遞給Reduce函數(shù).Reduce函數(shù)對具有相同到達(dá)時間的交叉口的“值”集合進(jìn)行處理,產(chǎn)生新的桶.Reduce階段的輸出格式如圖3所示.

到達(dá)交叉口時間(交叉口ID,前驅(qū)交叉口ID,到達(dá)前驅(qū)交叉口時間)序列

圖3Reduce階段的輸出格式

Fig.3Output format of Reduce stage

(4)HaLoop MapReduce的迭代

每次Reduce階段的輸出又作為下一輪Map階段的輸入,作業(yè)服務(wù)器(JobTracker)的循環(huán)控制模塊不斷啟動Map-Reduce計算,通過多次迭代完成路徑所包含的所有交叉口的計算.在迭代過程中,HaLoop的主節(jié)點機器負(fù)責(zé)Job內(nèi)的循環(huán)控制,直到迭代計算結(jié)束.迭代過程如圖4所示.

圖4基于HaLoop MapReduce的動態(tài)最短路徑算法迭代過程圖

Fig.4Iterative process of dynamic shortest path algorithm based on HaLoop MapReduce

文中DSP算法中，在最壞的情況下，第1階段,工作節(jié)點機器計算的時間復(fù)雜度為O(Mq/P),其中M為交通網(wǎng)絡(luò)的弧段數(shù),時間區(qū)間T為根據(jù)歷史數(shù)據(jù)確定的所對應(yīng)OD的最長行程時間.第2階段,主節(jié)點機器匯總計算的時間復(fù)雜度為O(N).由于O(Mq/P)>O(N),因此假設(shè)不考慮通信成本，則文中DSP算法的時間復(fù)雜度為O(Mq/P).

每個工作節(jié)點機器負(fù)責(zé)1個子網(wǎng)的計算,并把子網(wǎng)的最終計算結(jié)果一次性提交到主節(jié)點機器.子網(wǎng)中所有相關(guān)節(jié)點處理完成之前,各工作節(jié)點機器之間并無通信成本產(chǎn)生.此外,主節(jié)點機器和工作節(jié)點機器之間的通信成本也遠(yuǎn)小于計算時間復(fù)雜度.

通過基于HaLoop MapReduce框架的并行化處理,文中DSP算法的執(zhí)行性能大幅提升.該算法可以在可伸縮的大規(guī)模集群上并行執(zhí)行,并可以處理大規(guī)模的交通數(shù)據(jù),實現(xiàn)在大數(shù)據(jù)環(huán)境下的動態(tài)路徑誘導(dǎo).

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

文中設(shè)計研發(fā)了連續(xù)流智能交通管控平臺,并在此平臺上對文中算法進(jìn)行了測試.連續(xù)流智能交通管控平臺分析處理多源交通數(shù)據(jù),實現(xiàn)智能高效的交通管理與控制、交通決策支持以及警用資源管理等功能.測試系統(tǒng)部署在HaLoop集群,每個節(jié)點機器采用相同的軟件配置:操作系統(tǒng)采用Linux CentOS 7.1,軟件環(huán)境采用HaLoop+Java SE 6+SSH(struts2.3.16,spring3.2.8,hibernate3.6.10).路網(wǎng)和交通數(shù)據(jù)文件存儲在ORACLE數(shù)據(jù)庫中,使用ORACLE的大數(shù)據(jù)連接器(Big Data Connectors)將相關(guān)的數(shù)據(jù)寫入到HDFS中.

算法采用Java語言實現(xiàn),在基于廣州市電子地圖的動態(tài)網(wǎng)絡(luò)上進(jìn)行了測試.廣州市區(qū)道路交通網(wǎng)絡(luò)包含有21 326個節(jié)點,42 632個路段,屬于大型路網(wǎng).各路段行程時間和交叉口延誤數(shù)據(jù)根據(jù)21周的歷史數(shù)據(jù)統(tǒng)計值確定.出發(fā)時間以及交叉口延時以1 min為一個時間間隔;路段的行程時間以5 min為一個時間間隔.文中使用網(wǎng)絡(luò)分割工具M(jìn)etis把路網(wǎng)分成了10個區(qū)域.將路網(wǎng)圖及其分割圖部署到了11臺PC計算機上,形成了小型集群環(huán)境.每臺機器擁有主頻為3.3 GHz的4核處理器、4 G內(nèi)存和800 GB可用硬盤空間.其中一臺機器為主節(jié)點機器,作為HDFS的管理者(NameNode)和MapReduce的作業(yè)服務(wù)器,其余機器為工作節(jié)點機器,作為工作者(DataNode)和任務(wù)服務(wù)器.

在路網(wǎng)中選擇了12個OD對文中算法進(jìn)行測試,測試結(jié)果如表1所示.

表1　12個OD對動態(tài)最短路徑的測試結(jié)果

測試結(jié)果表明:對于長度為50 km左右的長路徑,計算時間在1 000 ms以內(nèi);長度為30 km左右的中等長度路徑,計算時間在700 ms以內(nèi);長度為10 km左右的短途路徑,計算時間為300 ms以內(nèi).文獻(xiàn)[22]中,求解靜態(tài)最短路徑的最高性能的運行時間是7.8 s;文獻(xiàn)[23]中,對動態(tài)最短路徑的平均計算時間是7.18 s.文中的實驗結(jié)果與之相比,計算效率有較大提升,可以滿足大規(guī)模路網(wǎng)中動態(tài)路徑誘導(dǎo)的需求.

6結(jié)語

文中對大數(shù)據(jù)環(huán)境下動態(tài)最短路徑問題進(jìn)行了研究,利用大數(shù)據(jù)的高性能分析與處理技術(shù)建立了動態(tài)交通網(wǎng)絡(luò)數(shù)學(xué)模型,在此基礎(chǔ)上提出了一種改進(jìn)的基于離散時間的動態(tài)最短路徑算法.該算法具有適用于動態(tài)非FIFO網(wǎng)絡(luò)和兼顧交叉口延時兩種特點,真實地反映了城市交通運行的特征,更加適合于大數(shù)據(jù)環(huán)境下的動態(tài)路徑誘導(dǎo).在算法的實現(xiàn)上,文中采用了當(dāng)前流行的大數(shù)據(jù)技術(shù),利用HaLoop MapReduce框架,實現(xiàn)了對交通數(shù)據(jù)的分布式并行處理,大大提高了路徑的求解效率.最后,在連續(xù)流智能交通管控平臺的分布式集群環(huán)境中對算法進(jìn)行了測試.測試結(jié)果表明,動態(tài)最短路徑算法以及基于HaLoop MapReduce的并行模式在解決大規(guī)模網(wǎng)絡(luò)的動態(tài)最短路徑問題上是非常有效的,比傳統(tǒng)動態(tài)最短路徑算法具有更高的精確性與實時性.未來對動態(tài)最短路徑問題的研究將進(jìn)一步探討如何利用大量的異構(gòu)實時交通數(shù)據(jù),對路段的行程時間進(jìn)行較為準(zhǔn)確的預(yù)測,使路徑誘導(dǎo)的準(zhǔn)確性進(jìn)一步提升.

參考文獻(xiàn)：

[1]Ahuja R K,Magnanti T L,Orlin J B.Network flows:theory,algorithms and applications [M].Englewood Cliffs,NJ:Prentice-Hall,1993.

[2]Topkins Donald M.Akshortest path algorithm for adaptive routing in communications networks [J].IEEE Trans Communications,1988,36(7):855- 859.

[3]Shi Hanmao.Time work tradeoffs of the single source shortest paths problem [J].Journal of Algorithms,1999,30(1):19- 32.

[4]Frigioni Daniele.Fully dynamic algorithms for maintaining shortest paths trees [J].Journal of Algorithms,2000,34(2):351- 381.

[5]Hall R W.The fastest path through a network with random time-dependent travel times [J].Transportation Science,1986,20(3):182- 188.

[6]Ziliaskopulos A,Mahmassani H.Time-dependent shortest path algorithms for real-time intelligent vehicle highway system applications [J].Transportation Research Records,1993,1408:94- 100.

[7]Chabini Ismail.Discrete dynamic shortest path problems in transportation applications:complexity and algorithms with optimal run time [J].Transportation Research Records,1998,1645:170- 175.

[8]Kim Seongmoon,Lewis Mark E,White Chelsea C.Optimal vehicle routing with real-time traffic information [J].IEEE Transportation on Intelligent Transportation Systems,2005,6(2):178- 188.

[9]Kaufman D E,Smith R L.Fastest path in time-dependent networks for intelligent vehicle-highway systems application [J].Intelligent Vehicle-Highway Systems Journal,1993,11(1):1- 11.

[10]Pallottino S,Scutella M G.Shortest path algorithms in transportation models:classical and innovative aspects[C]∥Marcotte P,Nguyen S.Equilibrium and Advanced Transportation Modeling.Boston:Kluwer,1998:245- 281.

[11]Orda Ariel,Rom Raphael.Distributed shortest-path protocols for time-dependent networks [J].Distributed Computing,1996,10(1):49- 62.

[12]譚國真,高文.時間依賴的網(wǎng)絡(luò)中最小時間路徑算法 [J].計算機學(xué)報,2002,25(2):165- 171.

Tan Guo-zhen,Gao Wen.Shortest path algorithm in time-dependent networks [J].Chinese Journal of Computers,2002,25(2):165- 171.

[13]Yagar S.Dynamic traffic assignment by individual path minimization and queuing [J].Transportation Research,1971(5):179- 196.

[14]Anez J,Barra T,Perezl B.Dual graph representation of transport networks [J].Transportation Research B,1996,30(3):209- 216.

[15]高明霞,賀國光.考慮交叉口延誤和轉(zhuǎn)向限制的弧標(biāo)號最短路徑算法 [J].蘭州交通大學(xué)學(xué)報,2011,30(6):111- 114.

Gao Ming-xia,He Guo-guang.An arc labeling algorithm for shortest path problem considering turn penalties and prohibitions at intersections [J].Jourrml of Lanzhou Jiaotong University,2011,30(6):111- 114.

[16]胡小兵,黃席樾.對一類帶聚類特征TSP問題的并行遺傳算法求解 [J].計算機工程與應(yīng)用,2004,40(35):66- 74.

Hu Xiao-bing,Huang Xi-yue.Solving traveling salesman problem with characteristic of clustering by parallel genetic algorithm [J].Computer Engineering and Applications,2004,40(35):66- 74.

[17]Hopfield J J,Tank D W.Neural computation of decisions in optimization problems [J].Biological Cybernetics,1985(3):141- 152.

[18]黃貴玲,高西全,靳松杰,等.基于蟻群算法的最短路徑問題的研究和應(yīng)用 [J].計算機工程與應(yīng)用,2007,43(13):233- 235.

Huang Gui-ling,Gao Xi-quan,Jin Song-jie,et al.Study and application on shortest path search problem based on ant algorithm [J].Computer Engineering and Applications,2007,43(13):233- 235.

[19]林潔,楊立才,吳曉晴,等.求解動態(tài)路徑誘導(dǎo)K路最短問題的人工免疫優(yōu)化方法 [J].山東大學(xué)學(xué)報:工學(xué)版,2007,37(2):103- 108.

Lin Jie,Yang Li-cai,Wu Xiao-qing,et al.Artificial immune optimization method for solving theK-shortest paths search in dynamic route guidance systems [J].Journal of Shandong University:Engineering Science,2007,37(2):103- 108.

[20]馬憲民,劉妮.自適應(yīng)視野的人工魚群算法求解最短路徑問題 [J].通信學(xué)報,2014,35(1):1- 6.

Ma Xian-min,Liu Ni.Improved artificial fish-swarm algorithm based on adaptive vision for solving the shortest path problem [J].Journal on Communications,2014,35(1):1- 6.

[21]魏明,靳文舟.求解車輛路徑問題的離散粒子群算法 [J].計算機科學(xué),2010,37(4):187- 191.

Wei Ming,Jin Wen-zhou.Discrete particle swarm optimization algorithm for vehicle routing problems [J].Computer Science,2010,37(4):187- 191.

[22]楊慶芳,梅朵,鄭黎黎,等.基于云計算的城市路網(wǎng)最短路徑遺傳算法求解 [J].華南理工大學(xué)學(xué)報:自然科學(xué)版,2014,42(3):166- 169.

Yang Qing-fang,Mei Duo,Zheng Li-li,et al.Cloud computing-based genetic algorithm to solve the shortest path in urban road networks [J].Journal of South China University of Technology:Natural Science Edition,2014,42(3):166- 169.

[23]Wen Hui-ying,Xu Jian-min,Zou Liang.Genetic algorithm-based computation of the shortest path in discrete-time dynamic networks [J].Journal of South China University of Technology:Natural Science Edition,2008,36(2):13- 28.

溫惠英,徐建閩,鄒亮.基于遺傳算法的離散時間動態(tài)網(wǎng)絡(luò)最短路徑求解 [J].華南理工大學(xué)學(xué)報:自然科學(xué)版,2008,36(2):13- 28.

[24]Caldwel T.On finding minimum routes in a network with turn penalties [J].Communication of the ACM,1961,4(2):107- 108.

[25]Bu Yingyi,Howe Bill,Balazinska Magdalena,et al.HaLoop:eficient iterative data processing on large clusters [J].Proceedings of the VLDB Endowment,2010,3(1/2):285- 296.

Foundation item: Supported by the National Natural Science Foundation of China(51078150)

A Dynamic Shortest Path Algorithm for Big Data

XuJian-minWangYuLinPei-qun

(School of Civil Engineering and Transportation, South China University of Technology, Guangzhou 510640, Guangdong, China)

Abstract:Massive heterogeneous data processing has been a great challenge to intelligent traffic applications.In this paper, the dynamic shortest path problem in traffic guidance is dealt with, and a mathematic model of dynamic traffic networks is constructed. Then, a dynamic shortest path algorithm considering the intersection delay is proposed. Furthermore, a distributed and parallel processing model for solving the dynamic shortest path problem is presented based on HaLoop MapReduce and by using big data techniques. Finally, the proposed algorithm is tested on the intelligent traffic management and control platform based on continual flow. Experimental results demonstrate that the proposed algorithm and the presented model can effectively find the dynamic shortest path in large scale networks and can meet the real-time requirement.

Key words:big data; dynamic shortest path algorithm; intersection delay; route guidance

文章編號：1000- 565X(2015)10- 0008- 08

作者簡介：王強(1973-)，男，博士后，廣東華路交通科技有限公司高級工程師，主要從事路橋檢測評估研究.E-mail： wq2351@163.com

基金項目：*國家自然科學(xué)基金資助項目(51078150)；交通運輸部建設(shè)科技項目(2011318223390)；廣東省交通運輸廳科技項目(科技-2009- 01- 001- 05)

收稿日期：2015- 01- 07

中圖分類號：U491.2

doi:10.3969/j.issn.1000-565X.2015.10.001