基于深度優(yōu)先反向搜索算法確定有效路徑集合

張建旭，蔣 燕, 劉興國

(重慶交通大學(xué) 交通運輸學(xué)院，重慶 400074)

?

基于深度優(yōu)先反向搜索算法確定有效路徑集合

張建旭，蔣 燕, 劉興國

(重慶交通大學(xué) 交通運輸學(xué)院，重慶 400074)

基于最短路徑中任意路段因發(fā)生交通事件而失效時的替代路徑搜索，合理界定了有效路徑的阻抗值范圍。參考深度優(yōu)先算法和有效路徑Dail算法離終點越來越近的思想，提出了一種從終點出發(fā)，反向搜索前置節(jié)點的多條有效路徑搜索算法。算例結(jié)果表明：該算法能自動識別與路網(wǎng)結(jié)構(gòu)相關(guān)的有效路徑阻抗值范圍，且能快速找到阻抗范圍內(nèi)的有效路徑集合。

交通工程；圖論；有效路徑；深度優(yōu)先算法；Floyd算法

0 引 言

在城市交通網(wǎng)絡(luò)中，為防止起訖點間的理想路徑因交通事件而擁擠或中斷，交通管理者需要快速識別備選分流路徑，將瓶頸段的車流快速分流到理想路徑外的其他合理路徑當(dāng)中。備選分流路徑選擇的實質(zhì)就是有效路徑集合的確定。

現(xiàn)有最典型的有效路徑確定方法為Dail算法[1-2]及K路徑算法，但這兩種算法都存在一定的缺陷。Dail算法以路網(wǎng)中路段所在位置與起訖點位置關(guān)系來確定該路段是否為有效路段，而忽略了路阻的權(quán)重。這樣可能會造成所選出的有效路徑所包含路段的路阻和很大，而路阻較小的路徑卻沒能被選中[3]。K路徑算法[4]避免了Dail算法的這一問題，但也存在搜索次數(shù)多，計算量大的問題。每次均以最短路徑搜索算法為基礎(chǔ)，計算多條路徑阻抗值并比較，得出第K條有效路徑。K路徑算法對路徑阻抗值排序的思想，需人為判斷有效路徑條數(shù)K。

通過對傳統(tǒng)Dail算法和K路徑算法的分析可知，這兩種算法無法準(zhǔn)確地找到路徑阻抗值在一個合理范圍內(nèi)的有效路徑集合。筆者以交通出行擁堵常發(fā)狀況為基礎(chǔ)，合理地界定了有效路徑阻抗值范圍。根據(jù)有效路徑定義，自動識別不同路網(wǎng)結(jié)構(gòu)下OD對間有效路徑阻抗值的范圍。結(jié)合深度優(yōu)先算法與Dail算法離終點越來越近的思想，從終點出發(fā)，以中間節(jié)點的臨界阻抗值是否不小于起點至該中間節(jié)點最短路徑阻抗值為判斷條件，能夠快速找到OD對間阻抗值合理范圍內(nèi)的有效路徑集合。

1 有效路徑阻抗值的范圍界定

如何判定某一路徑是否為有效路徑，其關(guān)鍵在于判斷這一路徑的阻抗值是否在一個合理的阻抗值范圍內(nèi)。何勝學(xué)，等[5]認(rèn)為，路徑K為有效路徑，則其阻抗值應(yīng)不大于最短路徑阻抗值(1+Hrs)倍。一般情況下，伸展系數(shù)Hrs的值對于城際間的研究可取0.6，對于城市內(nèi)的研究可在區(qū)間[0.3,0.5]內(nèi)取值[6]。F.Leurent[6]明確了有效路徑的阻抗范圍，其不足之處在于其伸展系數(shù)為一個經(jīng)驗值，這對于不同形式的路網(wǎng)結(jié)構(gòu)，誤差往往較大。例如，對于棋盤式路網(wǎng)路段普遍較短的情況，根據(jù)這一值找出的有效路徑數(shù)較多；但對于組團式城市，這樣的經(jīng)驗值則較為合理。李景，等[7]在進(jìn)行多路徑交通流分配時認(rèn)為：若所選路徑的路權(quán)與最短路徑的路權(quán)的相對差小于或等于臨界相對差，則該條路徑即為有效路徑，其中，臨界相對差是指出行者在出行過程中所能容忍的比最短路徑多走的路程或多用的時間與最短路徑路權(quán)的比值。

考慮到在城市交通網(wǎng)絡(luò)中，起訖點間最短路徑一般不會出現(xiàn)多條路段同時中斷的情況，而是匯、分流交通量大的一條路段出現(xiàn)交通中斷或幾條路段在不同時段發(fā)生交通擁堵，為此，筆者對有效路徑的阻抗值范圍重新定義。為方便敘述，先定義以下變量：

G=(V,A,D)表示一個有向交通網(wǎng)絡(luò)；

V={vi|i=1,2,…,n}表示節(jié)點的集合；

A={aij|i,j=1,2,…,n}表示所有有向路段的集合，?aij∈A表示從vi至vj存在有向路段，稱vj與vi相連，vi與vj反向相連；

D={dij|i,j=1,2,…,n}表示有向路段阻抗值的集合，dij表示有向路段aij的阻抗值大??；

L=[lij]n×n為該網(wǎng)絡(luò)最短路徑阻抗矩陣，lij表示從vi至vj最短路徑的阻抗值。假定初始阻抗矩陣也為鄰接矩陣，即L(0)=[dij]n×n；

對有效路徑新定義有以下說明：

說明1：有效路徑條數(shù)與最短路徑所包含的路段數(shù)無絕對函數(shù)關(guān)系。這是由以下兩種情況引起的。

1)一般情況下，OD對間最短路徑所包含路段失效時，其替代路徑可能是同一條。如圖1中，v2至v4間最短路徑為v2→v3→v4，路段a23、a34分別失效時，其最短替代路徑均是v2→A→v4。

圖1 定義1說明簡單路網(wǎng)

2)此外，有些路徑不是某路段失效時的替代路徑，但其阻抗值介于有效路徑阻抗值范圍內(nèi)，這樣的路徑也是有效路徑。圖1中v1至v4間，v1→v2→B→v4不是最短路徑路段a23或a24失效時的替代路徑。但其阻抗值小于路段a12失效時，最短替代路徑的阻抗值為5，所以該路徑也是有效路徑。

說明2：對于不同起訖點的有效路徑存在相對性。即OD對間，一條路徑在小網(wǎng)絡(luò)結(jié)構(gòu)中不是有效路徑，但在一個較大的網(wǎng)絡(luò)中，這條路徑可能變成其他OD對有效路徑的組成部分。

例如圖1中，根據(jù)定義1，v2至v4間，v2→B→v4不是節(jié)點對(v2,v4)的有效路徑。但對于節(jié)點對(v1,v4)間，v1→v2→B→v4是有效路徑。這與起終點距離越大，出行者可接受的相對距離也越大的出行心理相符，也是因為阻抗范圍隨路網(wǎng)結(jié)構(gòu)變大而增大的結(jié)果。

定義3：在節(jié)點對(r,s)有效路徑搜索時，除終點vs外，其他中間節(jié)點均存在臨界阻抗值u。對于某路徑i，某路段akg∈A位于該路徑i中，則中間節(jié)點vk的臨界阻抗值(urk)i，等于后置節(jié)點vg的臨界阻抗值減去路段akg的阻抗值，即(urk)i=(urg)i-dkg。在計算時，假定終點vs臨界阻抗值urs=Crrs。

從定義3可知，從中間節(jié)點到終點vs存在j條路徑，那么節(jié)點vk的臨界阻抗值需要計算j次。例如圖2中，對于節(jié)點對(1,10)尋找有效路徑，可能需要分別從路徑v10→v9→v6和v10→v7→v6計算節(jié)點v6的臨界阻抗值。根據(jù)定義3，假定終點v10的臨界阻抗值u1,10=Cr1,10=21，從路徑1：v10→v9→v6計算時，(u19)1=21-5=16，則(u16)1=(u19)1-d69=11。從路徑2：v10→v7→v6計算時，(u17)2=21-4=17，(u16)2=(u17)2-d67=17-5=12。此時對于從v6至v10的上述2條路徑，中間節(jié)點v6的臨界阻抗值需要計算2次，結(jié)果分別為11和12。

圖2 定義3示例說明

推論1：節(jié)點對(r,s)有效路徑搜索時，對中間節(jié)點臨界阻抗值判斷，如果urk≥lrk，此時沿著vk繼續(xù)向起點vr搜索，必定能找到1條及以上的阻抗值介于(lrs,lrs′)的有效路徑。則稱vk、akg為OD對(r,s)間1條有效路徑所包含的有效節(jié)點、有效路段。

證明：對于某路徑i，在計算中間節(jié)點vk的臨界阻抗值(urk)i時，令節(jié)點vk至終點vs在路徑i上所有路段阻抗值之和為(sks)i。

(urk)i≥lrk?(urk)i+(sks)i≥lrk+(sks)i?urs≥lrk+(sks)i

不等式表示的是從vr至vs的一條路徑的阻抗值在(r,s)有效路徑阻抗最大容許值范圍內(nèi)。這條路徑由vr至vk最短路徑及在計算中間節(jié)點vk的臨界阻抗值(urk)i時，節(jié)點vk至終點vs在路徑i上所有路段組成。

如圖2中，從路徑2：v10→v7→v6出發(fā)計算得(u16)2=12>l16=10，路徑v10→v7→v6的阻抗值(s6,10)2=9，則u16+(s6,10)2=21>l16+(s6,10)2=19。已知，對于起點1而言，終點v10的阻抗最大容許值Cr1,10=21，這說明路徑v1→v6→v7→v10是一條有效路徑，其路徑阻抗為19。事實上從v6向前搜索還可以找到另外一條有效路徑v1→v2→v4→v6→v7→v10，其阻抗值正好為21。

2 有效路徑搜索算法

通過筆者的定義可知，找出OD對(r,s)間有效路徑，需找出有效路徑阻抗值范圍。筆者以floyd最短路徑算法[8-11]基礎(chǔ)計算得到兩個結(jié)果，供有效路徑搜索使用：①沒有路段失效時，任意節(jié)點間最短路徑阻抗矩陣L；②初始最短路中任意路段失效時，OD對(r,s)間有效路徑阻抗值范圍。

現(xiàn)有對于阻抗值范圍內(nèi)的有效路徑搜索算法研究中，賴樹坤，等[12]通過圖的遍歷方法進(jìn)行搜索，需找出起點出發(fā)所有路徑，當(dāng)其終點為目標(biāo)節(jié)點，且阻抗值在預(yù)先給定的范圍內(nèi)時，此時判斷該路徑為有效路徑。該方法必需遍歷全部路徑，造成大量的冗余計算。為防止這種算法在求解有效路徑時的“組合爆炸”問題，何勝學(xué)，等[5]利用節(jié)點坐標(biāo)劃分有效搜索區(qū)域，根據(jù)已求出的節(jié)點位勢，以節(jié)點估價函數(shù)確定下一步搜索鄰接節(jié)點。該方法能有效縮小搜索范圍，但是在搜索過程中，需對每一個節(jié)點定位，這樣使得計算復(fù)雜，并且在山地城市中高差較大必然引起節(jié)點位勢及搜索半徑的不準(zhǔn)確，導(dǎo)致計算結(jié)果產(chǎn)生較大差異。

筆者探索一種基于深度優(yōu)先算法的反向搜索算法，該算法能夠自動判斷有效路徑阻抗值范圍，并從終點節(jié)點出發(fā)，不重復(fù)篩選地一次性找出滿足阻抗范圍條件的全部有效路徑。

深度優(yōu)先算法基本思想[13-14]是：為了求得問題的解，先選擇某一種可能情況向前(子節(jié)點)探索，在探索過程中，一旦發(fā)現(xiàn)原來的選擇不符合要求，就回溯至父親節(jié)點重新選擇另一節(jié)點，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至求得最優(yōu)解。深度優(yōu)先算法在最優(yōu)解搜索過程中，往往存在不滿足條件要求的“死路”或已訪問節(jié)點，為避免下次繼續(xù)朝這個方向走，對這些“死路”或已訪問節(jié)點進(jìn)行標(biāo)記，可以得到更高的效率。

筆者基于深度優(yōu)先原理，設(shè)計出可實現(xiàn)多條有效路徑搜索的算法，具體思路如下：對于OD對(r,s)間有向路徑搜索，主要從終點vs出發(fā)向起點vr搜索；首先計算與vs反向相連的一個節(jié)點vg的臨界阻抗值，判斷該值與vr至該節(jié)點的最短路徑阻抗值的關(guān)系，若urg≥lrg滿足，則尋找與節(jié)點vg反向相連且滿足判斷條件urk≥lrk的子節(jié)點vk；如果不滿足條件，則尋找其他滿足條件的節(jié)點；這樣一直向下搜索，直到當(dāng)前訪問節(jié)點為起點vr時，則找到了第1條有效路徑。根據(jù)第1條有效路徑，從節(jié)點vr反溯至其父親節(jié)點，從其父親節(jié)點尋找與其反向相連且能滿足判斷條件的其他未訪問節(jié)點。如果有，繼續(xù)向前搜索，則尋找到另一條有效路徑；如果沒有，則回溯至當(dāng)前節(jié)點的父親節(jié)點。一直這樣回溯，直到回溯至終點vs，且不再存在滿足條件且沒有訪問過的節(jié)點，算法結(jié)束。

本算法說明：①對于從任意中間節(jié)點vk判斷是否繼續(xù)沿此節(jié)點繼續(xù)向前搜索的判斷條件均為urk≥lrk，如果滿足此條件則繼續(xù)搜索，如果不滿足則回溯至其父親節(jié)點；②算法在一條有效路徑搜索節(jié)點標(biāo)記時，對搜索過的當(dāng)前節(jié)點的兄弟節(jié)點及父親節(jié)點進(jìn)行標(biāo)記，防止搜索時回到父親節(jié)點或已訪問過的兄弟節(jié)點，對子節(jié)點進(jìn)行臨時標(biāo)記，當(dāng)回溯至當(dāng)前節(jié)點的父親節(jié)點時，清除對當(dāng)前節(jié)點的子節(jié)點的標(biāo)記；③中間節(jié)點的臨界阻抗值隨不同路徑變化而變化，在存儲中間節(jié)點臨界阻抗值時，需實時更新。

多條有效路徑搜索的具體算法步驟如下：

2.1 有效路徑阻抗值范圍確定

Step1：將實際路網(wǎng)抽象成簡單路網(wǎng)圖，根據(jù)floyd算法找到OD對(r,s)間最短路徑及阻抗值。floyd算法調(diào)用如下。

1)輸入初始權(quán)矩陣L(0)=(lij(0))n×n，其中：

2)：計算L(k)=(lij(k))n×n，(k=1,2,…,n)，其中：lij(k)=min[lij(k-1),lik(k-1)+lkj(k-1)]。

2.2 深度優(yōu)先反向搜索算法尋求有效路徑

進(jìn)行下一步前先定義幾個存儲空間。

建立數(shù)據(jù)棧S，數(shù)值p表示S的第p個元素，S(p)表示當(dāng)前訪問節(jié)點，初始化時第一個訪問元素S(p=1)=s。S主要記錄當(dāng)前搜索的節(jié)點及被標(biāo)記的當(dāng)前節(jié)點的所有父親節(jié)點。當(dāng)S(p=1)=0時搜索結(jié)束，此時，終點節(jié)點vs的所有反向相連子節(jié)點全都被訪問過，不存在滿足判斷條件的子節(jié)點。

建立游歷標(biāo)記矩陣o為n×n的零矩陣，主要記錄子節(jié)點的臨時訪問情況。元素o(i,j)=1表示從vi出發(fā)至vj已經(jīng)被訪問過，只做臨時標(biāo)記。

建立臨時路徑存儲矩陣q,令q(1,1)=s。該矩陣記錄每一次搜索訪問過的所有節(jié)點編號。當(dāng)該矩陣當(dāng)前行最后一個元素為vr時(或urS(p)-dhS(p)

建立永久路徑存儲矩陣y，當(dāng)臨時路徑存儲矩陣q的最后一個元素為節(jié)點vr時，記錄此路徑。即永久路徑存儲矩陣y的當(dāng)前行等于臨時路徑存儲矩陣q的當(dāng)前行。記錄完成后換行。

Step4：如果棧的第一個元素不為0時，執(zhí)行以下程序。

1)如果當(dāng)前訪問節(jié)點S(p)為出發(fā)地vr，轉(zhuǎn)至step4.4進(jìn)入回溯。

2)找到與節(jié)點S(p)反向相連的節(jié)點vh，判斷節(jié)點vh是否滿足游歷矩陣元素o(S(p),h)=0且urs(p)-dhs(p)≥lrh，滿足則轉(zhuǎn)至step4.5。

3)不滿足條件則繼續(xù)尋找滿足條件的節(jié)點vh，如果與節(jié)點p反向相連的節(jié)點全被訪問過，沒有滿足條件的節(jié)點vh。轉(zhuǎn)至step4.4進(jìn)入回溯。

4)①將當(dāng)前訪問節(jié)點的子節(jié)點全部標(biāo)記為未訪問，即o(S(p),:)=0；②讓臨時路徑存儲矩陣q換行(換行后的行元素與前一行除最后一個元素外的元素一致，下一次記錄臨時路徑時則從此行的最后一個元素開始)；③如果當(dāng)前訪問節(jié)點為vr，則將臨時路徑存儲矩陣q的當(dāng)前行存儲至永久路徑存儲矩陣y當(dāng)前行中，換行；④讓無后繼點的或以達(dá)到目標(biāo)點的節(jié)點元素出棧，即：S(p)=0。訪問上一個父親節(jié)點，即棧的前一個元素。

5)①標(biāo)記從節(jié)點S(p)至節(jié)點vh已經(jīng)訪問過，即游歷矩o(S(p),h)=1；②讓節(jié)點vh入棧，并作為下一個訪問節(jié)點；③節(jié)點vh的臨界阻抗值等于當(dāng)前訪問節(jié)點臨界阻抗值減去這兩個節(jié)點間的路段阻抗值；④將節(jié)點vh存入臨時路徑存儲矩陣q當(dāng)前行后一個列元素當(dāng)中。

Step5：當(dāng)棧的第一個元素為0時，搜索結(jié)束，輸出永久存儲矩陣y。

具體使用MATLAB編程，流程如圖3。

圖3 深度優(yōu)先反向搜索算法流程

3 算例說明

對于圖4所示簡化交通網(wǎng)絡(luò)，存在v1，v2，…，v10共計10個節(jié)點和14條路段，每條路段的行駛阻抗為固定值，已標(biāo)注在對應(yīng)的路段中，將使用深度優(yōu)先反向搜索算法找出OD對(1,10)間的有效路徑。

圖4 算例簡化路網(wǎng)

根據(jù)有效路徑定義，先找到OD對(1,10)的最短路徑：v1→v2→v7→v9→v10。當(dāng)最短路徑所包含路段分別失效時，找到OD對(1,10)有效路徑的阻抗值范圍為(19,22)。

根據(jù)深度優(yōu)先反向搜索算法搜索有效路徑過程如圖5。

<>—節(jié)點v1至該節(jié)點的最短路徑阻抗值；[ ]—節(jié)點的臨界阻抗值

圖5中，有效路徑搜索時，每次節(jié)點向前搜索均需計算節(jié)點臨界阻抗值，只有當(dāng)該節(jié)點的臨界阻抗值大于或等于起點vs至該節(jié)點的最短路徑阻抗值時，繼續(xù)往下搜索。具體步驟如下：

搜索1：從終點v10出發(fā)找到第1條滿足阻抗條件的有效路徑1：v10→v6→v3→v2→v1。

搜索2：從起點v1開始回溯，每回溯至上一父親節(jié)點vk均判斷該節(jié)點是否存在沒有訪問過且滿足判斷條件urk≥lrk的其他子節(jié)點，滿足則繼續(xù)沿該子節(jié)點向前搜索，不存在這樣的節(jié)點則繼續(xù)回溯至上一父親節(jié)點。本次搜索直到回溯至v6時，存在與其反向相連的節(jié)點v5，滿足u15≥l15。繼續(xù)向前搜索找到有效路徑2：v10→v6→v5→v3→v2→v1。

搜索3：從有效路徑2回溯至v5，找到與之反向相連的節(jié)點v4，且滿足判斷條件u14≥l14。從節(jié)點v4繼續(xù)向前搜索找到有效路徑3：v10→v6→v5→v4→v2→v1。

搜索4：按照前述方法，從有效路徑3回溯至終點節(jié)點v10，找到與v10反向相連沒有訪問過的節(jié)點v9，計算得u19≥l19。此時沿著v9繼續(xù)向前搜索找到有效路徑4：v10→v9→v4→v2→v1。

搜索5：從有效路徑4回溯至v9，找到與v9反向相連沒有訪問過的節(jié)點v8，計算得u18≥l18。此時沿著v8繼續(xù)向前搜索找到有效路徑5：v10→v9→v8→v4→v2→v1。

搜索6：從有效路徑5回溯至v8，回溯至v8找到與v8反向相連沒有訪問過的節(jié)點v7，計算得u17≥l17。此時沿著v7繼續(xù)向前搜索找到有效路徑6：v10→v9→v8→v7→v1。

搜索7：從有效路徑6回溯，直至終點節(jié)點v10，沒能找到與v10反向相連且沒有訪問過的節(jié)點。此時搜索結(jié)束。

根據(jù)筆者算法，使用MATLAB編程搜索出算例路網(wǎng)圖中，OD對(1,10)間的有效路徑如表1。

表1 OD對(1,10)間有效路徑集合

表1中，本搜索算法找出OD對(1,10)間的有效路徑阻抗值均介于(19,22)之間，共6條。從本算例來看，筆者提出的算法自動識別了有效路徑阻抗值范圍，從而避免了K路徑算法人為判斷有效路徑條數(shù)K的情況。也沒有出現(xiàn)Dail算法搜索時，相對較近的有效路徑未被選中的情況。

本算例使用廣度優(yōu)先算法搜索過程如圖6。在有效路徑搜索過程中，廣度優(yōu)先搜索算法和深度優(yōu)先反向搜索算法，均需完成圖的遍歷，故這兩種算法具有相同的時間復(fù)雜度。在搜索過程中，深度優(yōu)先反向算法每一次搜索得到的是一條完整的有效路徑，完成每一次搜索后即可清除臨時存儲空間；而廣度優(yōu)先算法每一次搜索得到的是組成有效路徑的零散路段、節(jié)點集合，需完成最后一次搜索后才能清除所有臨時存儲數(shù)據(jù)。相比之下，對于大型路網(wǎng)中有效路徑搜索，廣度優(yōu)先搜索算法會占據(jù)更大的存儲空間。

圖6 廣度優(yōu)先搜索算法有效路徑搜索過程

簡而言之，對于大型網(wǎng)絡(luò)中有效路徑搜索，深度優(yōu)先反向搜索算法具有和廣度優(yōu)先搜索算法相同的時間復(fù)雜度和更小的空間復(fù)雜度，且搜索過程具有系統(tǒng)性和連續(xù)性。故深度優(yōu)先反向搜索算法更適合于大型網(wǎng)絡(luò)中有效路徑的搜索。

4 結(jié) 語

考慮現(xiàn)有多條有效路徑算法無法客觀界定OD對間阻抗值范圍，可能出現(xiàn)有效路徑漏選的情況，筆者對有效路徑重新定義，找到了OD對間合理的阻抗范圍的確定方法。使用深度優(yōu)先反向搜索有效路徑，有效的避免了大量的冗余計算。另外該算法可以迅速求解實際交通網(wǎng)絡(luò)中節(jié)點間其他有效阻抗值范圍內(nèi)的多條有效路徑集合，為路網(wǎng)交通分流路徑識別、交通流誘導(dǎo)等提供了方法。

筆者所提出的多條有效路徑搜索算法，找出的有效路徑集合隨路網(wǎng)規(guī)模的大小、路網(wǎng)的結(jié)構(gòu)形式變化而變化，但沒有考慮到路網(wǎng)的流量變化情況。在以后的研究中，若能結(jié)合路網(wǎng)流量的變化建立一種動態(tài)有效路徑搜索系統(tǒng)，必然更能適用于交通誘導(dǎo)、組織、導(dǎo)航等實際管理任務(wù)。

[1] Soo-young J,Chae Y L.Multipath selection and channel assignment in wirelessmesh networks[J].Wireless Netw,2011,17(4):1001-1014.

[2] 王英杰,程琳,王煒.基于有效路徑集合的節(jié)點間連通度估計方法研究[J].武漢理工大學(xué)學(xué)報:交通工程與科學(xué)版,2009,33(5):960-963. Wang Yingjie,Cheng Lin,Wang Wei.Researches on estimations of connectivity reliability of an OD pair based on the effective path sets[J].Journal of Wuhan University of Technology:Transportation Science & Engineering,2009,33(5):960-963.

[3] 楊信豐,劉蘭芬.基于影響度的有效路徑集合的確定[J].交通運輸系統(tǒng)工程與信息,2011,11(6):104-110. Yang Xinfeng,Liu Lanfen.Determining the efficient paths based on effect degree[J].Journal of Transportation Systems Engineering and Information Technology,2011,11(6):104-110.

[4] Lokshtanov D,Mnich M,Saurabh S.Planark-path in subexponential time and polynomial space[C]//Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science.Teplá-Klá?ter:Czech Republic,2011:262-270.

[5] 何勝學(xué),范炳全.隨機交通分配中有效路徑的定向樹搜索算法[J].交通與計算機,2005(5):38-41. He Shengxue,Fan Bingquan.Orientated tree algorithm of searching efficient paths in stochastic traffic assignment[J].Computer and Communications,2005(5):38-41.

[6] Leurent F.Curbing the computational difficulty of logit equilibrium assignment model[J].Transportation Research B:Methodological,1997,31(4):315-326.

[7] 李景,彭國雄,臧亦文.改進(jìn)型多路徑分配模型及算法設(shè)計[J].系統(tǒng)工程理論與實踐,2001(9):130-134. Li Jing,Peng Guoxiong,Zang Yiwen.An improved multi-path assignment model and algorithms design [J].Systems Engineering-Theory & Practice,2001(9):130-134.

[8] 李洪波,王茂波.Floyd最短路徑算法的動態(tài)優(yōu)化[J].計算機工程與應(yīng)用,2006(34):60-63. Li Hongbo,Wang Maobo.Dynamic optimum of shortest path’s algorithm devised by Floyd[J].Computer Engineering and Applications,2006(34):60-63.

[9] 嚴(yán)曉鳳,陸濟湘,唐雙平.基于Floyd算法的校園最短路徑問題分析與實現(xiàn)[J].武漢理工大學(xué)學(xué)報:信息與管理工程版,2012,34(6):695-703. Yan Xiaofeng,Lu Jixiang,Tang Shuangping.Analysis and implementation of campus shortest path based on Floyd algorithm[J].Journal of Wuhan University of Technology:Information & Management Engineering ,2012,34(6):695-703.

[10] 黃遠(yuǎn)春,胥耀方,潘海澤.城際公共交通系統(tǒng)最短路算法[J].重慶交通大學(xué)學(xué)報:自然科學(xué)版,2010,29(2):265-268. Huang Yuanchun,Xu Yaofang,Pan Haize.Algorithm for shortest path of intercity public transportation system[J].Journal of Chongqing Jiaotong University:Natural Science,2010,29(2):265-268.

[11] 黃美靈, 陸百川.考慮交叉口延誤的城市道路最短路徑[J].重慶交通大學(xué)學(xué)報:自然科學(xué)版,2009,28(6):1060-1063. Huang Meiling,Lu Baichuan.Determination of the shortest path considering delays at intersections[J].Journal of Chongqing Jiaotong University:Natural Science,2009,28(6):1060-1063.

[12] 賴樹坤,姚憲輝,彭愚.交通網(wǎng)絡(luò)中有效路徑確定方法的探討[J].交通標(biāo)準(zhǔn)化,2008(1):137-139. Lai Shukun,Yao Xianhui,Peng Yu.Determination of efficient path in traffic network[J].Communications Standardization,2008(1):137-139.

[13] Evangelista S,Laarman A,Petrucci L,et al.Improved multi-core nested depth-first search[C]∥Automated Technology for Verification and Analysis,Thiruvananthapuram.India:Springer Berlin Heidelberg,2012:269-283.

[14] Kozen D C.Depth-first and breadth-first search[M]//The Design and Analysis of Algorithms.New York:Springer Berlin Heidelberg,1992:19-24.

Determining Effective Paths Set Based on Reverse Depth-First Search Algorithm

Zhang Jianxu, Jiang Yan, Liu Xingguo

(School of Traffic & Transportation, Chongqing Jiaotong University, Chongqing 400074, China)

Based on the definition of alternative path, the range of effective path impedance values was identified. Adopting the depth-first algorithm and the idea of getting closer to the end from the effective path Dail algorithm, an effective paths search algorithm which starts from the end node to the front node was proposed. Numerical results show that, the effective path search algorithm not only identifies the impedance values range associated with the network structure automatically, but also finds the effective path sets quickly.

traffic engineering; graph theory; effective path; depth-first search algorithm; Floyd algorithm

10.3969/j.issn.1674-0696.2015.03.20

2013-12-11；

2014-02-22

國家自然科學(xué)基金項目(51308569)

張建旭(1978—)，男，河南許昌人，副教授，博士，主要從事綜合交通規(guī)劃與管理方面的研究。E-mail：jexu@qq.com。

U491.1+3

A

1674-0696(2015)03-093-06