徐建閩　王鈺　林培群

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

?

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

徐建閩王鈺林培群

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

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

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

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

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

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

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

1相關(guān)研究

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

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

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

為了解決包含有交叉口延誤和轉(zhuǎn)向限制的SP問題,國(guó)內(nèi)外學(xué)者提出了多種方法.擴(kuò)展網(wǎng)絡(luò)法[13]與對(duì)偶網(wǎng)絡(luò)法[14]將原網(wǎng)絡(luò)進(jìn)行一定轉(zhuǎn)換,然后采用基本的SP算法求解.文獻(xiàn)[15]中提出了一個(gè)基于弧標(biāo)號(hào)的標(biāo)號(hào)修正算法.但是目前對(duì)于動(dòng)態(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]提出用遺傳算法來(lái)求解動(dòng)態(tài)最短路徑.由于智能算法本身比較復(fù)雜、計(jì)算量大,因此以上算法都存在搜索時(shí)間長(zhǎng)或者計(jì)算精度低的問題.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟1(初始化)

Bθ:={v0};

Bc:=?(?c≠θ);

h:=θ;

步驟2

SelectviFromBh

Bh:=Bh{vi};

Ifvi≠vn

For 每一個(gè)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)向限制.在實(shí)時(shí)性方面,算法利用桶結(jié)構(gòu)提高了計(jì)算效率,同時(shí)便于在大數(shù)據(jù)處理平臺(tái)上進(jìn)行并行化處理.從前往后的計(jì)算方式有利于在求解過(guò)程中及時(shí)應(yīng)用最新的交通狀態(tài)數(shù)據(jù).

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

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

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

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

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

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

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

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

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

(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

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

(2)Map階段

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

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

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

圖2Map階段的輸出格式

Fig.2Output format of Map stage

(3)Reduce階段

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

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

圖3Reduce階段的輸出格式

Fig.3Output format of Reduce stage

(4)HaLoop MapReduce的迭代

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

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

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

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

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

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

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

文中設(shè)計(jì)研發(fā)了連續(xù)流智能交通管控平臺(tái),并在此平臺(tái)上對(duì)文中算法進(jìn)行了測(cè)試.連續(xù)流智能交通管控平臺(tái)分析處理多源交通數(shù)據(jù),實(shí)現(xiàn)智能高效的交通管理與控制、交通決策支持以及警用資源管理等功能.測(cè)試系統(tǒng)部署在HaLoop集群,每個(gè)節(jié)點(diǎn)機(jī)器采用相同的軟件配置:操作系統(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ù)文件存儲(chǔ)在ORACLE數(shù)據(jù)庫(kù)中,使用ORACLE的大數(shù)據(jù)連接器(Big Data Connectors)將相關(guān)的數(shù)據(jù)寫入到HDFS中.

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

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

表1　12個(gè)OD對(duì)動(dòng)態(tài)最短路徑的測(cè)試結(jié)果

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

6結(jié)語(yǔ)

文中對(duì)大數(shù)據(jù)環(huán)境下動(dòng)態(tài)最短路徑問題進(jìn)行了研究,利用大數(shù)據(jù)的高性能分析與處理技術(shù)建立了動(dòng)態(tài)交通網(wǎng)絡(luò)數(shù)學(xué)模型,在此基礎(chǔ)上提出了一種改進(jìn)的基于離散時(shí)間的動(dòng)態(tài)最短路徑算法.該算法具有適用于動(dòng)態(tài)非FIFO網(wǎng)絡(luò)和兼顧交叉口延時(shí)兩種特點(diǎn),真實(shí)地反映了城市交通運(yùn)行的特征,更加適合于大數(shù)據(jù)環(huán)境下的動(dòng)態(tài)路徑誘導(dǎo).在算法的實(shí)現(xiàn)上,文中采用了當(dāng)前流行的大數(shù)據(jù)技術(shù),利用HaLoop MapReduce框架,實(shí)現(xiàn)了對(duì)交通數(shù)據(jù)的分布式并行處理,大大提高了路徑的求解效率.最后,在連續(xù)流智能交通管控平臺(tái)的分布式集群環(huán)境中對(duì)算法進(jìn)行了測(cè)試.測(cè)試結(jié)果表明,動(dòng)態(tài)最短路徑算法以及基于HaLoop MapReduce的并行模式在解決大規(guī)模網(wǎng)絡(luò)的動(dòng)態(tài)最短路徑問題上是非常有效的,比傳統(tǒng)動(dòng)態(tài)最短路徑算法具有更高的精確性與實(shí)時(shí)性.未來(lái)對(duì)動(dòng)態(tài)最短路徑問題的研究將進(jìn)一步探討如何利用大量的異構(gòu)實(shí)時(shí)交通數(shù)據(jù),對(duì)路段的行程時(shí)間進(jìn)行較為準(zhǔn)確的預(yù)測(cè),使路徑誘導(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]譚國(guó)真,高文.時(shí)間依賴的網(wǎng)絡(luò)中最小時(shí)間路徑算法 [J].計(jì)算機(jī)學(xué)報(bào),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]高明霞,賀國(guó)光.考慮交叉口延誤和轉(zhuǎn)向限制的弧標(biāo)號(hào)最短路徑算法 [J].蘭州交通大學(xué)學(xué)報(bào),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]胡小兵,黃席樾.對(duì)一類帶聚類特征TSP問題的并行遺傳算法求解 [J].計(jì)算機(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].計(jì)算機(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]林潔,楊立才,吳曉晴,等.求解動(dòng)態(tài)路徑誘導(dǎo)K路最短問題的人工免疫優(yōu)化方法 [J].山東大學(xué)學(xué)報(bào):工學(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é)報(bào),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].計(jì)算機(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]楊慶芳,梅朵,鄭黎黎,等.基于云計(jì)算的城市路網(wǎng)最短路徑遺傳算法求解 [J].華南理工大學(xué)學(xué)報(bào):自然科學(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.

溫惠英,徐建閩,鄒亮.基于遺傳算法的離散時(shí)間動(dòng)態(tài)網(wǎng)絡(luò)最短路徑求解 [J].華南理工大學(xué)學(xué)報(bào):自然科學(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

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

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

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

收稿日期：2015- 01- 07

中圖分類號(hào)：U491.2

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