考慮轉向延誤的最短路徑的節點標號算法

雒 應,何 強

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

0 引 言

最短路徑算法是交通運輸工程領域應用最廣泛的算法之一，是智能交通分配、交通規劃和交通控制的基礎算法。最短路徑算法評估一條路徑是否為最短路徑的度量衡是該路徑的代價，一般為該路徑花費的時間，或者該路徑的其他成本。一般的最短路徑算法在計算路徑代價時僅考慮路段的阻抗，這種情況對公路是適用的，因為公路路段長度大而節點較少，路徑的路段行程時間一般遠遠大于節點消耗的時間，因而車輛的交叉口延誤可以忽略。但是城市道路路段長度一般較短，交叉口數量多，交叉口作為城市道路網絡中通行能力的瓶頸嚴重影響交通流的運行，擁堵情況下車輛在交叉口處花費的時間甚至可能超過在相鄰路段的行駛時間[1]。因此，應用于城市路網的最短路徑算法應該考慮交叉口延誤。

1 研究現狀分析

考慮交叉口延誤和轉向限制最短路徑問題(shortest path with turn penalties and prohibitions)的難點在于轉向路徑沒有很好的數學描述[1]，因而解決問題的關鍵在于如何表現轉向關系。目前國內外學者對此問題的解決辦法按照對算法使用的網絡分類可分為直接法和間接法兩大類[2]。

1.1 間接法

間接法對原始網絡按照一定規則進行變換， 將轉向延誤和限制直接體現在變換網絡中，然后在變換網絡中計算最短路徑，最后基于變化規則逆向轉換在變化網絡中得到的最短路徑，輸出原始網絡的最短路徑，包括擴展網絡法、對偶網絡法等。

擴展網絡法[3]將每個交叉口擴展為一個子網絡， 通過增加虛擬節點和虛擬弧來表達原始轉向。擴展網絡中一個虛擬節點表示原始交叉口的一個進口或出口方向，連接虛擬節點的一條虛擬弧表示原始轉向，然后通過一般SP算法即可求解，如圖1。擴展網絡法思路明確，易于操作，但大量虛擬節點和虛擬弧的添加導致問題規模劇增。

圖1 擴展網絡法

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

圖2 對偶網絡法

對偶圖法的優點是網絡節點和弧數量少，對內存消耗較小，轉向延誤明確，但是原始網絡和對偶網絡轉化復雜并且需要轉化兩次。

1.2 直接法

直接法從算法本身入手，將轉向延誤通過節點或者弧的鄰接關系直接表達和求解，主要包括弧標號算法、節點標號算法等。

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

節點標號算法[9]與弧標號算法基本相同，通過兩個節點集分別儲存已確定最短路徑的節點和剩余其他的節點，并對每個節點設置距離標號和緊前節點標號，通過起點層層向外擴展直至到達終點。唯一的不同之處是節點標號算法在每一步的循環中掃描的是節點而不是弧。

上述方法中，擴展網絡法因為網絡規模的擴充導致過大的時間和空間開銷因而欠缺實用性。對偶網絡法、節點標號法和弧標號法的本質相同，即求包含邊權和節點權的最短路徑問題。弧標號算法盡管在表述上是對弧進行標號而不是對節點標號，但弧標號算法一樣對弧的標號值實際上是對該弧的頭結點，即該弧沿前進方向的終點的節點標號值，因此弧標號算法只是節點標號算法的一種表現形式而已，并不是一種新算法[2]。筆者通過記錄前置節點完成交叉口處的轉向判別以及延誤計算，更能反映城市路網真實的交通狀況，同時保留了節點標號算法的簡潔性和實用性，不需要像弧標號算法對路網拓撲進行預處理。 Dijkstra算法的復雜度較高，考慮轉向延誤后更會增加時間花費。筆者選擇最小堆對其進行優化，將時間復雜度從O(n2)優化為O(nlogn)，有利于提升動態交通分配算法的準確性、快速性。

2 考慮邊權和點權的Dijkstra算法

2.1 相關符號定義

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

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

2.2 算法流程

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

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

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

步驟2：若Y≠?且終點E不在X中，進行以下循環：

1)從Y中選出cost值最小的節點vj，將其從Y移入X。

2)對vj的所有鄰接節點vk∈vj,adjList，通過式(1)計算通過vj到達vk的newCost：

(1)

若newCost

步驟3：從終點根據pre指針回溯路徑至起點，輸出最短路徑。

2.3 時間復雜度分析與優化

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

在選取合適的數據結構對Dijkstra算法進行時間復雜度優化時，選擇哪種數據結構不僅取決于操作，還取決于每種操作執行的次數。算法中主要有兩種操作：更新集合Y中節點的cost值；集合Y中循環訪問最好的節點并刪除它。可以發現，如果邊數遠小于n2，對此可以考慮用堆這種數據結構進行優化，把網絡中所有節點均壓入一個最小堆(即根節點值最小的堆)中，每次可以直接取堆頂元素入最短路，取節點的時間復雜度為O(1)，但維護最小堆的時間復雜度為O(logn)。那么步驟2第1步中，最小堆的初始化和排序的時間為O(nlogn)，循環刪除最好節點的時間亦為O(nlogn)，那么步驟2第1步的時間復雜度為O(nlogn)。步驟2第2步中節點的每次松弛都會導致堆的重新排序，最壞情況下每個節點均松弛，那么時間復雜度為O(nlogn)。所以采用堆優化后，算法的時間復雜度為O(nlogn)。

2.4 算法的數據結構

2.4.1 原始路網數據存儲

原始路網數據的存儲采用鄰接表(adjacent list)的形式儲存，其一般形式如表1。

表1 原始路網的鄰接表儲存方式

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

轉向延誤參數采用表的形式儲存，一般形式如表2(限制轉向將其轉向延誤設為無窮大)。

表2 轉向延誤參數表一般形式

2.4.2 程序的數據結構

定Node類如表3。name表示節點編號；cost表示節點路徑代價；pre表示節點的前置節點的編號；adjNodeList為儲存該節點鄰接節點的數組。

表3 Node類屬性

X集合采用靜態一維數組。Y集合采用最小堆數據結構，如圖3。

圖3 Y集合采用的最小堆結構

3 算法應用

3.1 原始網絡參數

以重慶地區某城市交通網絡為例(圖4)，其中網絡節點代表交叉口，弧代表連接交叉口的路段，路段容量與自由流時間見表4。

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

圖4 城市道路網絡拓撲圖

3.2 交通網絡阻抗

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

(2)

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

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

(3)

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

表4 路段單向容量與自由流時間

表5 轉向延誤

3.3 應用分析

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

表6 最短路徑對比

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

圖5 最短路徑對比

4 結 論

基于前置節點法提出了考慮交叉口延誤的改進Dijkstra算法，并選用最小堆數據結構將算法的時間復雜度從O(n2)優化為O(nlogn)，最后使用不考慮交叉口延誤的最短路徑算法和筆者改進算法對重慶某城市路網的最短路徑進行了對比計算，驗證了改進算法的有效性。結果表明，在考慮交叉口延誤后，城市路網最短路徑會發生變化，以往的最短路徑可能由于某個交叉口處的延誤而變為非最短路徑。研究結果更能反映真實的城市道路網交通狀態。同時經過堆優化后算法的時間復雜度下降，有利于設計準確、高效的動態交通分配算法，以供交通管理部門更快捷地舒緩交通擁堵。