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

張建旭，蔣 燕, 劉興國(guó)

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

?

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

張建旭，蔣 燕, 劉興國(guó)

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

對(duì)有效路徑新定義有以下說(shuō)明：

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

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

圖1 定義1說(shuō)明簡(jiǎn)單路網(wǎng)

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

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

例如圖1中，根據(jù)定義1，v2至v4間，v2→B→v4不是節(jié)點(diǎn)對(duì)(v2,v4)的有效路徑。但對(duì)于節(jié)點(diǎn)對(duì)(v1,v4)間，v1→v2→B→v4是有效路徑。這與起終點(diǎn)距離越大，出行者可接受的相對(duì)距離也越大的出行心理相符，也是因?yàn)樽杩狗秶S路網(wǎng)結(jié)構(gòu)變大而增大的結(jié)果。

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

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

圖2 定義3示例說(shuō)明

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

證明：對(duì)于某路徑i，在計(jì)算中間節(jié)點(diǎn)vk的臨界阻抗值(urk)i時(shí)，令節(jié)點(diǎn)vk至終點(diǎn)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最短路徑及在計(jì)算中間節(jié)點(diǎn)vk的臨界阻抗值(urk)i時(shí)，節(jié)點(diǎn)vk至終點(diǎn)vs在路徑i上所有路段組成。

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

2 有效路徑搜索算法

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

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

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

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

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

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

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

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

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

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

2)：計(jì)算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)行下一步前先定義幾個(gè)存儲(chǔ)空間。

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

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

建立臨時(shí)路徑存儲(chǔ)矩陣q,令q(1,1)=s。該矩陣記錄每一次搜索訪問(wèn)過(guò)的所有節(jié)點(diǎn)編號(hào)。當(dāng)該矩陣當(dāng)前行最后一個(gè)元素為vr時(shí)(或urS(p)-dhS(p)

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

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

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

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

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

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

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

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

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

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

3 算例說(shuō)明

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

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

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

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

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

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

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

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

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

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

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

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

搜索7：從有效路徑6回溯，直至終點(diǎn)節(jié)點(diǎn)v10，沒(méi)能找到與v10反向相連且沒(méi)有訪問(wèn)過(guò)的節(jié)點(diǎn)。此時(shí)搜索結(jié)束。

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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

筆者所提出的多條有效路徑搜索算法，找出的有效路徑集合隨路網(wǎng)規(guī)模的大小、路網(wǎng)的結(jié)構(gòu)形式變化而變化，但沒(méi)有考慮到路網(wǎng)的流量變化情況。在以后的研究中，若能結(jié)合路網(wǎng)流量的變化建立一種動(dòng)態(tài)有效路徑搜索系統(tǒng)，必然更能適用于交通誘導(dǎo)、組織、導(dǎo)航等實(shí)際管理任務(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é)點(diǎn)間連通度估計(jì)方法研究[J].武漢理工大學(xué)學(xué)報(bào):交通工程與科學(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].交通運(yùn)輸系統(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ī)交通分配中有效路徑的定向樹(shù)搜索算法[J].交通與計(jì)算機(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] 李景,彭國(guó)雄,臧亦文.改進(jìn)型多路徑分配模型及算法設(shè)計(jì)[J].系統(tǒng)工程理論與實(shí)踐,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最短路徑算法的動(dòng)態(tài)優(yōu)化[J].計(jì)算機(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)曉鳳,陸濟(jì)湘,唐雙平.基于Floyd算法的校園最短路徑問(wèn)題分析與實(shí)現(xiàn)[J].武漢理工大學(xué)學(xué)報(bào):信息與管理工程版,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é)報(bào):自然科學(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é)報(bào):自然科學(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] 賴樹(shù)坤,姚憲輝,彭愚.交通網(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

國(guó)家自然科學(xué)基金項(xiàng)目(51308569)

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

U491.1+3

A

1674-0696(2015)03-093-06