雒 應(yīng),何 強(qiáng)

(長安大學(xué) 公路學(xué)院，陜西 西安 710064)

0 引 言

最短路徑算法是交通運(yùn)輸工程領(lǐng)域應(yīng)用最廣泛的算法之一，是智能交通分配、交通規(guī)劃和交通控制的基礎(chǔ)算法。最短路徑算法評估一條路徑是否為最短路徑的度量衡是該路徑的代價(jià)，一般為該路徑花費(fèi)的時(shí)間，或者該路徑的其他成本。一般的最短路徑算法在計(jì)算路徑代價(jià)時(shí)僅考慮路段的阻抗，這種情況對公路是適用的，因?yàn)楣仿范伍L度大而節(jié)點(diǎn)較少，路徑的路段行程時(shí)間一般遠(yuǎn)遠(yuǎn)大于節(jié)點(diǎn)消耗的時(shí)間，因而車輛的交叉口延誤可以忽略。但是城市道路路段長度一般較短，交叉口數(shù)量多，交叉口作為城市道路網(wǎng)絡(luò)中通行能力的瓶頸嚴(yán)重影響交通流的運(yùn)行，擁堵情況下車輛在交叉口處花費(fèi)的時(shí)間甚至可能超過在相鄰路段的行駛時(shí)間[1]。因此，應(yīng)用于城市路網(wǎng)的最短路徑算法應(yīng)該考慮交叉口延誤。

1 研究現(xiàn)狀分析

考慮交叉口延誤和轉(zhuǎn)向限制最短路徑問題(shortest path with turn penalties and prohibitions)的難點(diǎn)在于轉(zhuǎn)向路徑?jīng)]有很好的數(shù)學(xué)描述[1]，因而解決問題的關(guān)鍵在于如何表現(xiàn)轉(zhuǎn)向關(guān)系。目前國內(nèi)外學(xué)者對此問題的解決辦法按照對算法使用的網(wǎng)絡(luò)分類可分為直接法和間接法兩大類[2]。

1.1 間接法

間接法對原始網(wǎng)絡(luò)按照一定規(guī)則進(jìn)行變換， 將轉(zhuǎn)向延誤和限制直接體現(xiàn)在變換網(wǎng)絡(luò)中，然后在變換網(wǎng)絡(luò)中計(jì)算最短路徑，最后基于變化規(guī)則逆向轉(zhuǎn)換在變化網(wǎng)絡(luò)中得到的最短路徑，輸出原始網(wǎng)絡(luò)的最短路徑，包括擴(kuò)展網(wǎng)絡(luò)法、對偶網(wǎng)絡(luò)法等。

擴(kuò)展網(wǎng)絡(luò)法[3]將每個(gè)交叉口擴(kuò)展為一個(gè)子網(wǎng)絡(luò)， 通過增加虛擬節(jié)點(diǎn)和虛擬弧來表達(dá)原始轉(zhuǎn)向。擴(kuò)展網(wǎng)絡(luò)中一個(gè)虛擬節(jié)點(diǎn)表示原始交叉口的一個(gè)進(jìn)口或出口方向，連接虛擬節(jié)點(diǎn)的一條虛擬弧表示原始轉(zhuǎn)向，然后通過一般SP算法即可求解，如圖1。擴(kuò)展網(wǎng)絡(luò)法思路明確，易于操作，但大量虛擬節(jié)點(diǎn)和虛擬弧的添加導(dǎo)致問題規(guī)模劇增。

圖1 擴(kuò)展網(wǎng)絡(luò)法

對偶網(wǎng)絡(luò)法[4,5]通過以下轉(zhuǎn)換表達(dá)轉(zhuǎn)向延誤：對偶節(jié)點(diǎn)代表原網(wǎng)絡(luò)的弧，并且保持弧的所有特征(容量、交通量和零流行程時(shí)間等)；對偶弧代表原網(wǎng)絡(luò)的轉(zhuǎn)向行為，并且保持該轉(zhuǎn)向行為的所有特征 (起終點(diǎn)、轉(zhuǎn)向延誤大小)。由此得到的對偶網(wǎng)絡(luò)中不存在轉(zhuǎn)向延誤和限制，轉(zhuǎn)化為考慮弧權(quán)和節(jié)點(diǎn)權(quán)的最短路徑問題，可直接利用SP算法求解，如圖2。

圖2 對偶網(wǎng)絡(luò)法

對偶圖法的優(yōu)點(diǎn)是網(wǎng)絡(luò)節(jié)點(diǎn)和弧數(shù)量少，對內(nèi)存消耗較小，轉(zhuǎn)向延誤明確，但是原始網(wǎng)絡(luò)和對偶網(wǎng)絡(luò)轉(zhuǎn)化復(fù)雜并且需要轉(zhuǎn)化兩次。

1.2 直接法

直接法從算法本身入手，將轉(zhuǎn)向延誤通過節(jié)點(diǎn)或者弧的鄰接關(guān)系直接表達(dá)和求解，主要包括弧標(biāo)號算法、節(jié)點(diǎn)標(biāo)號算法等。

弧標(biāo)號算法[6-8]對弧進(jìn)行標(biāo)號。算法管理兩個(gè)弧集Q和R:弧集Q存儲(chǔ)已確定最短路徑的?。换〖疪存儲(chǔ)剩下的弧。任意弧a均有兩個(gè)標(biāo)號：距離標(biāo)號Ca表示起始弧段至弧段a終點(diǎn)的最短路徑長度；緊前弧標(biāo)號Pa表示a在當(dāng)前路徑中的緊前弧。算法的每一步， 從R中取出并刪除標(biāo)號值Ca最小的弧a，將其加入Q中，同時(shí)掃描a的每條鄰接弧b(b∈R)，若Cb大于通過Ca計(jì)算得到的C′b，則令Cb=C′b,Pb=a。重復(fù)以上步驟， 直到終點(diǎn)弧段進(jìn)入集合Q，這時(shí)得到了從起始弧段到終點(diǎn)弧段的最短路徑及其長度。

節(jié)點(diǎn)標(biāo)號算法[9]與弧標(biāo)號算法基本相同，通過兩個(gè)節(jié)點(diǎn)集分別儲(chǔ)存已確定最短路徑的節(jié)點(diǎn)和剩余其他的節(jié)點(diǎn)，并對每個(gè)節(jié)點(diǎn)設(shè)置距離標(biāo)號和緊前節(jié)點(diǎn)標(biāo)號，通過起點(diǎn)層層向外擴(kuò)展直至到達(dá)終點(diǎn)。唯一的不同之處是節(jié)點(diǎn)標(biāo)號算法在每一步的循環(huán)中掃描的是節(jié)點(diǎn)而不是弧。

上述方法中，擴(kuò)展網(wǎng)絡(luò)法因?yàn)榫W(wǎng)絡(luò)規(guī)模的擴(kuò)充導(dǎo)致過大的時(shí)間和空間開銷因而欠缺實(shí)用性。對偶網(wǎng)絡(luò)法、節(jié)點(diǎn)標(biāo)號法和弧標(biāo)號法的本質(zhì)相同，即求包含邊權(quán)和節(jié)點(diǎn)權(quán)的最短路徑問題?；?biāo)號算法盡管在表述上是對弧進(jìn)行標(biāo)號而不是對節(jié)點(diǎn)標(biāo)號，但弧標(biāo)號算法一樣對弧的標(biāo)號值實(shí)際上是對該弧的頭結(jié)點(diǎn)，即該弧沿前進(jìn)方向的終點(diǎn)的節(jié)點(diǎn)標(biāo)號值，因此弧標(biāo)號算法只是節(jié)點(diǎn)標(biāo)號算法的一種表現(xiàn)形式而已，并不是一種新算法[2]。筆者通過記錄前置節(jié)點(diǎn)完成交叉口處的轉(zhuǎn)向判別以及延誤計(jì)算，更能反映城市路網(wǎng)真實(shí)的交通狀況，同時(shí)保留了節(jié)點(diǎn)標(biāo)號算法的簡潔性和實(shí)用性，不需要像弧標(biāo)號算法對路網(wǎng)拓?fù)溥M(jìn)行預(yù)處理。 Dijkstra算法的復(fù)雜度較高，考慮轉(zhuǎn)向延誤后更會(huì)增加時(shí)間花費(fèi)。筆者選擇最小堆對其進(jìn)行優(yōu)化，將時(shí)間復(fù)雜度從O(n2)優(yōu)化為O(nlogn)，有利于提升動(dòng)態(tài)交通分配算法的準(zhǔn)確性、快速性。

2 考慮邊權(quán)和點(diǎn)權(quán)的Dijkstra算法

2.1 相關(guān)符號定義

用網(wǎng)絡(luò)中的節(jié)點(diǎn)表示交叉口及出行起訖點(diǎn)，用弧表示相鄰交叉口之間的路段，則城市道路網(wǎng)可用賦權(quán)有向網(wǎng)絡(luò)G=(V,E,D,T) 表示，其中：V={vi|i=1,2,…,n}為節(jié)點(diǎn)集合，V中節(jié)點(diǎn)數(shù)量為n；E={eij|i,j=1,2,…,m,i≠j}為弧集合，E中弧的數(shù)量為m；D={dijk|i,j,k=1,2,…,n,i≠j≠k} 為節(jié)點(diǎn)權(quán)重集合，表示行駛在弧eij的車輛轉(zhuǎn)向弧ejk在節(jié)點(diǎn)j處產(chǎn)生的延誤，可采用延誤模型計(jì)算的數(shù)據(jù)或者實(shí)際調(diào)查的數(shù)據(jù)；T={tij|i,j=1,2,…,n,i≠j}為邊權(quán)集合，表示車輛在弧eij上的行程時(shí)間費(fèi)用。

對?eij∈E,稱節(jié)點(diǎn)i和j分別為弧eij的尾節(jié)點(diǎn)(tail node)和頭結(jié)點(diǎn)(head node)；對?j∈V，稱以其為頭節(jié)點(diǎn)的弧如eij為j的入弧，稱以其為尾節(jié)點(diǎn)的弧如ejk為j的出弧。

2.2 算法流程

引入兩個(gè)集合X和Y,X集合儲(chǔ)存最短路徑已經(jīng)明確的節(jié)點(diǎn)，Y集合儲(chǔ)存剩余的最短路徑未明確的節(jié)點(diǎn)。Y中的每個(gè)節(jié)點(diǎn)v有2個(gè)對應(yīng)的量v.cost、v.pre、v.adjList：v.cost是起點(diǎn)到v(并且只經(jīng)由X中的節(jié)點(diǎn))的最短路徑費(fèi)用。v.pre是v的緊前節(jié)點(diǎn)，表示從起點(diǎn)到v(并且只經(jīng)由X中的節(jié)點(diǎn))最短路徑的前一個(gè)節(jié)點(diǎn)；v.adjList是v的鄰接節(jié)點(diǎn)集合。

求OD對S—E間最短路徑流程如下：

步驟1：將所有節(jié)點(diǎn)v∈V加入Y集合,并設(shè)置：v.cost=inf(inf為一足夠大正整數(shù))，v.pre=nullptr，并根據(jù)路網(wǎng)數(shù)據(jù)初始化v.adjList。設(shè)置路徑起點(diǎn)S.cost=0。

步驟2：若Y≠?且終點(diǎn)E不在X中，進(jìn)行以下循環(huán)：

1)從Y中選出cost值最小的節(jié)點(diǎn)vj，將其從Y移入X。

2)對vj的所有鄰接節(jié)點(diǎn)vk∈vj,adjList，通過式(1)計(jì)算通過vj到達(dá)vk的newCost：

(1)

若newCost

步驟3：從終點(diǎn)根據(jù)pre指針回溯路徑至起點(diǎn)，輸出最短路徑。

2.3 時(shí)間復(fù)雜度分析與優(yōu)化

在筆者算法中，根據(jù)節(jié)點(diǎn)標(biāo)號的類型，所有的結(jié)點(diǎn)可以分為3種，分別是已標(biāo)記節(jié)點(diǎn)(集合X中的節(jié)點(diǎn))、未標(biāo)記節(jié)點(diǎn)(集合Y中cost屬性為inf的節(jié)點(diǎn))和臨時(shí)標(biāo)記節(jié)點(diǎn)(即集合Y中cost屬性為有限值的節(jié)點(diǎn))。在2.2節(jié)算法中，步驟2中第1步較為關(guān)鍵，需要從臨時(shí)標(biāo)記節(jié)點(diǎn)和未標(biāo)記節(jié)點(diǎn)中尋找cost值最小的節(jié)點(diǎn)。若將這些節(jié)點(diǎn)保存在一般的未排序的數(shù)據(jù)結(jié)構(gòu)中，那么每次進(jìn)行步驟2中第1步時(shí)，均需要在儲(chǔ)存數(shù)據(jù)中查找最小值，均需使用遍歷算法。對于一般的線性數(shù)據(jù)結(jié)構(gòu)如數(shù)據(jù)、鏈表和隊(duì)列等，遍歷算法的時(shí)間復(fù)雜度為O(n)，則該步驟的時(shí)間復(fù)雜度為O(n2)。步驟2中第2步在最壞情況下對每個(gè)節(jié)點(diǎn)均運(yùn)算一次，考慮到交通網(wǎng)絡(luò)節(jié)點(diǎn)的入度一般為小于等于4的常數(shù)，所以該步驟其時(shí)間復(fù)雜度為O(n)。因此一般情況下，相加得到Dijkstra算法的時(shí)間復(fù)雜度是為O(n2)[10]。

在選取合適的數(shù)據(jù)結(jié)構(gòu)對Dijkstra算法進(jìn)行時(shí)間復(fù)雜度優(yōu)化時(shí)，選擇哪種數(shù)據(jù)結(jié)構(gòu)不僅取決于操作，還取決于每種操作執(zhí)行的次數(shù)。算法中主要有兩種操作：更新集合Y中節(jié)點(diǎn)的cost值；集合Y中循環(huán)訪問最好的節(jié)點(diǎn)并刪除它?？梢园l(fā)現(xiàn)，如果邊數(shù)遠(yuǎn)小于n2，對此可以考慮用堆這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化，把網(wǎng)絡(luò)中所有節(jié)點(diǎn)均壓入一個(gè)最小堆(即根節(jié)點(diǎn)值最小的堆)中，每次可以直接取堆頂元素入最短路，取節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)，但維護(hù)最小堆的時(shí)間復(fù)雜度為O(logn)。那么步驟2第1步中，最小堆的初始化和排序的時(shí)間為O(nlogn)，循環(huán)刪除最好節(jié)點(diǎn)的時(shí)間亦為O(nlogn)，那么步驟2第1步的時(shí)間復(fù)雜度為O(nlogn)。步驟2第2步中節(jié)點(diǎn)的每次松弛都會(huì)導(dǎo)致堆的重新排序，最壞情況下每個(gè)節(jié)點(diǎn)均松弛，那么時(shí)間復(fù)雜度為O(nlogn)。所以采用堆優(yōu)化后，算法的時(shí)間復(fù)雜度為O(nlogn)。

2.4 算法的數(shù)據(jù)結(jié)構(gòu)

2.4.1 原始路網(wǎng)數(shù)據(jù)存儲(chǔ)

原始路網(wǎng)數(shù)據(jù)的存儲(chǔ)采用鄰接表(adjacent list)的形式儲(chǔ)存，其一般形式如表1。

表1 原始路網(wǎng)的鄰接表儲(chǔ)存方式

表1中“鄰接點(diǎn)屬性”包括每個(gè)鄰接點(diǎn)的零流行程時(shí)間，s、路段通行能力，pcu/h、以及路段交通量，pcu/h。

轉(zhuǎn)向延誤參數(shù)采用表的形式儲(chǔ)存，一般形式如表2(限制轉(zhuǎn)向?qū)⑵滢D(zhuǎn)向延誤設(shè)為無窮大)。

表2 轉(zhuǎn)向延誤參數(shù)表一般形式

2.4.2 程序的數(shù)據(jù)結(jié)構(gòu)

定Node類如表3。name表示節(jié)點(diǎn)編號；cost表示節(jié)點(diǎn)路徑代價(jià)；pre表示節(jié)點(diǎn)的前置節(jié)點(diǎn)的編號；adjNodeList為儲(chǔ)存該節(jié)點(diǎn)鄰接節(jié)點(diǎn)的數(shù)組。

表3 Node類屬性

X集合采用靜態(tài)一維數(shù)組。Y集合采用最小堆數(shù)據(jù)結(jié)構(gòu)，如圖3。

圖3 Y集合采用的最小堆結(jié)構(gòu)

3 算法應(yīng)用

3.1 原始網(wǎng)絡(luò)參數(shù)

以重慶地區(qū)某城市交通網(wǎng)絡(luò)為例(圖4)，其中網(wǎng)絡(luò)節(jié)點(diǎn)代表交叉口，弧代表連接交叉口的路段，路段容量與自由流時(shí)間見表4。

假設(shè)路段交通量為其容量的0.5倍，車輛到達(dá)率服從平均到達(dá)率(300 pcu/h, Webster公式已考慮車輛到達(dá)率服從泊松分布)，則根據(jù)式(1)編程計(jì)算得到轉(zhuǎn)向延誤計(jì)算表。為檢驗(yàn)算法的靈敏性，只在節(jié)點(diǎn)7和節(jié)點(diǎn)9兩處交叉口布置紅綠燈，同時(shí)不考慮其他節(jié)點(diǎn)的轉(zhuǎn)向延誤。表5為兩個(gè)節(jié)點(diǎn)處的轉(zhuǎn)向延誤。

圖4 城市道路網(wǎng)絡(luò)拓?fù)鋱D

3.2 交通網(wǎng)絡(luò)阻抗

節(jié)點(diǎn)阻抗主要是指交叉口處車輛由于信號燈等產(chǎn)生的延誤。筆者參照文獻(xiàn)[11]的方法，根據(jù)路段飽和度選擇交叉口延誤模型：飽和度x<1時(shí)選用Webster模型；x≥1時(shí)選用瞬時(shí)延誤模型(Akcelik模型)，如式(2)：

(2)

式中:d為單車道每車的平均延誤;c為信號周期;λ為綠信比;q為該車道車輛到達(dá)率;x為飽和度；x0是飽和度臨界值。

路段阻抗使用BPR函數(shù)，如式(3)：

(3)

式中:t為兩交叉口間的路段行程時(shí)間;t0為交通量為零時(shí)的路段行程時(shí)間;Q為路段交通量;C為路段通行能力；α、β為阻抗影響參數(shù)，采用美國公路局推薦值α=0.15和β=4。

表4 路段單向容量與自由流時(shí)間

表5 轉(zhuǎn)向延誤

3.3 應(yīng)用分析

分別用普通的不考慮交叉口延誤的Dijkstra算法和筆者改進(jìn)的考慮交叉口延誤的Dijkstra算法進(jìn)行最短路徑的求解，結(jié)果見表6。

表6 最短路徑對比

由表6可知：OD點(diǎn)對1→5、1→16的最短路徑在不考慮交叉口延誤和考慮交叉口延誤兩種情況下未發(fā)生變化，原因是本次試驗(yàn)中假設(shè)除了節(jié)點(diǎn)7、9以外的節(jié)點(diǎn)均無節(jié)點(diǎn)延誤；OD點(diǎn)對1→18在兩種情況下的最短路徑為1→6→7→12→13→18，路徑經(jīng)過節(jié)點(diǎn)7時(shí)，轉(zhuǎn)向6→7→12是右轉(zhuǎn)方向，而試驗(yàn)假設(shè)右轉(zhuǎn)不設(shè)限，根據(jù)延誤模型計(jì)算的右轉(zhuǎn)延為3 s，所以兩種情況下最短路徑長度發(fā)生了變化(即使考慮該處轉(zhuǎn)向延誤，該路徑仍是最短路徑)；OD對5→11和1→10的最短路徑發(fā)生了變化，不考慮交叉口延誤的Dijkstra算法得到的最短路徑在考慮交叉口延誤后已不是最短路徑，其最短路徑對比如圖5。

圖5 最短路徑對比

4 結(jié) 論

基于前置節(jié)點(diǎn)法提出了考慮交叉口延誤的改進(jìn)Dijkstra算法，并選用最小堆數(shù)據(jù)結(jié)構(gòu)將算法的時(shí)間復(fù)雜度從O(n2)優(yōu)化為O(nlogn)，最后使用不考慮交叉口延誤的最短路徑算法和筆者改進(jìn)算法對重慶某城市路網(wǎng)的最短路徑進(jìn)行了對比計(jì)算，驗(yàn)證了改進(jìn)算法的有效性。結(jié)果表明，在考慮交叉口延誤后，城市路網(wǎng)最短路徑會(huì)發(fā)生變化，以往的最短路徑可能由于某個(gè)交叉口處的延誤而變?yōu)榉亲疃搪窂?。研究結(jié)果更能反映真實(shí)的城市道路網(wǎng)交通狀態(tài)。同時(shí)經(jīng)過堆優(yōu)化后算法的時(shí)間復(fù)雜度下降，有利于設(shè)計(jì)準(zhǔn)確、高效的動(dòng)態(tài)交通分配算法，以供交通管理部門更快捷地舒緩交通擁堵。