一種考慮交通限制信息的道路網絡模型

摘要:隨著城市交通網絡的發展，實際道路中的交通限制信息使得道路網絡中的最優路徑規劃變得更加復雜，針對這一問題，筆者討論了一種考慮交通限制信息的道路網絡模型，并詳細闡述了該模型的存儲方法及各種常見交通限制信息的解決方案，然后給出了利用此模型求解最優路徑的改進的Diiktra算法描述。最后，筆者根據北京市道路數據建立道路網絡，通過實際數據進行驗證，實驗結果表明，該模型及算法能滿足實際道路網絡的最優路徑分析的需要，具有一定的應用價值。

關鍵字:道路網絡;交通限制;最優路徑規劃;Diiktra算法

A Model of Road Network with Traffic Limits

SUN Cun-qun

(Faculty of Information Engineering， China University of Geosciences， Wuhan 430074， China)

Abstract: The information of traffic limits make the shortest path analysis in road network become more complex， in order to solve this problem， the author discussed a model of road network with traffic limits， and next detailed the storage methods of this model and the solutions of common traffic limits， and then improved Diiktra algorithm using this model to analyze the shortest path. Finally， the author had verified by the actual data， the experimental results show that the model and algorithm can meet the needs of the shortest path analysis in actual road network.

Key words: road network; traffic limits; the shortest path analysis; Dijktra algorithm

隨著城市交通的發展，道路的數目不斷增加，交通管理也日趨復雜，如在道路上設置單行、禁行限制，發布動態交通信息等，這些措施有力地促進了交通合理分流，提高了交通的安全和效率，但同時也使出行者選擇并按最優路徑行駛變得更為復雜，所謂最優路徑不僅指出發地與目的地之間的距離最短，還包括行程時間最少、費用最少以及綜合費用最少等不同意義下的最短路徑。在實際道路條件下，最優路徑的求解并不能直接利用圖論中最短路徑算法，因為各種交通限制使得表面上連通的道路網絡實際上并不連通。針對這一問題，本文討論了一種考慮交通限制約束的道路網絡模型，并詳細闡述了該模型的存儲方法及常見交通限制信息的解決方案，然后給出了利用此模型求解最優路徑規劃的算法。

1 道路網存儲

道路網絡一般根據圖論的基本理論抽象為帶權有向圖，它有兩類基本要素:網絡結點元素和網絡邊線元素，其中網絡結點可以表示道路交叉口、公交站點、地鐵出入口、輕軌出入口等點狀要素，網絡邊線可以表示街道路段、公交路段、地鐵路段、輕軌路段等線狀要素。圖l所示的是一個具有7個結點和11條邊線的道路網絡G。其中，結點元素用圓圈表示，圓圈內的數字為結點序號;邊線元素用線段表示，線段上的數字為邊線序號，括號內的數字為邊線的權值。

帶權有向圖的存儲根據平面圖特性的存儲方式，常用的有鄰接矩陣、鄰接表、鄰接多重表和十字鏈表等。對于道路網絡這樣的大型稀疏圖，應用鄰接表來存貯數據已經成為業界的共識，其表示根據應用角度不同可以分為順序鄰接表(FS，Forward Star)和逆向鄰接表(BS，Backward Star)等[1]。圖l中道路網絡G的鄰接表如圖2所示。

Dijkstra算法是一個適用于所有邊線權值為非負的最短路算法，也是目前公認的求解最短路徑問題的經典算法，該算法采用了優化問題中常用的貪心技巧，是一種按路徑長度遞增序產生各頂點最短路徑的算法。該算法保存一個結點集合，結點相對于源結點的最小費用是已知的，開始時，這個集合僅包含源結點，其他結點為“剩余結點”。在每一步，向集合加入一個“剩余結點”，它的費用相對于源結點盡可能的小。對該算法進行分析發現，該算法對獲取結點的連接邊線以及獲取邊線的連接點的操作非常頻繁，而鄰接表的存儲方式只能快速獲取結點的連接邊線，對于獲取邊線的連接點則需要經過一系列復雜的步驟。

綜合現有道路網絡存儲結構的優缺點，筆者采用兩個基本表和一個擴展表來存儲網絡數據，分別為邊線-結點拓撲表、結點-邊線拓撲表、結點-邊線拓撲擴展表。邊線-結點拓撲表用來存儲邊線相關的結點數據，包括邊線的起始結點(FNodID)和終止結點(TNodID)兩個字段，獲取邊線的連接結點時可根據邊線的序號得到偏移量直接獲取數據;結點-邊線拓撲表用來存儲結點的連接邊數據，有與該結點相鄰的邊線序號(EdgeID)和與該邊線相鄰的結點序號(CNodID)兩個字段，根據道路網絡分析發現，通常道路網絡結點的度大于4的占很小一部分，因此結點-邊線拓撲表的字段用固定長度來存儲，即4個一組，長度為兩個序號長度的四倍，結點的度數不足4的用0補齊，結點的度數大于4，則在第四組數據中與該結點相鄰的邊線序號字段中記錄標示-1，與該邊線相鄰的結點序號中記錄剩余連接邊在擴展表中的偏移位置，這樣獲取結點的連接邊時同樣可根據結點的序號得到偏移量直接獲取數據;結點-邊線拓撲擴展表用來存儲度數大于4的結點的連接邊數據，與結點-邊線拓撲表字段一樣，該表也將四組數據分為一組。表1、表2、表3分別為圖1道路網絡G的邊線-結點拓撲表、結點-邊線拓撲表、結點-邊線拓撲擴展表。

2 交通限制條件下的解決方案

現實城市道路網絡及其復雜，存在著大量的交通限制信息，交通管制信息的存在使得實體意義上的相鄰性與實際交通行為中的可達性是不一致的。根據限制信息的時效性可以分為兩類，一類是動態交通限制信息，例如發生在路段或交叉路口上的交通堵塞，其特點是隨時間變化較快;另一類是靜態的交通限制信息，例如設置在結點處的禁止通行標志，其特點是隨時間變化較慢[2]。由于進行最優路徑分析時主要考慮邊線與結點之間的關系，所以筆者將限制信息按照限制的類型分為兩類，一類是基于路段的限制信息，例如路段上的交通堵塞，單向行駛，禁止通行等;另一類是基于結點的限制信息，例如交叉路口上的交通堵塞，交叉口設置的禁止左轉或禁止右轉等。

2.1 基于邊線的限制

基于邊線的限制主要有某路段上的禁行，單向行駛等。上述道路網絡的存儲，把道路網絡看作是一個有向圖，比較容易解決基于邊線的限制，只需要把與某個結點相關聯的邊線去掉即可。具體實現方法為:對于每條路段根據其限制信息增加相應的屬性記錄，最優路徑規劃算法搜索每條路段時檢查相應的屬性信息，來判斷該路段是否可以通行。例如解決路段的單雙行限制可以給組成道路網絡的邊線增加一個表示單行線還是雙行線的字段，解決某個時段對于某車型禁行問題，可以增加兩個字段用來表示某時段某種類型的車可以通過該路段，在最優路徑規劃算法的搜索過程中，根據相應的限制信息來判斷邊線是否可以通過，若不符合通過的條件，則將該邊線舍棄。對于某路段的臨時禁行問題，可將禁行路段臨時存儲起來，在算法搜索過程中，進行相應判斷即可。

2.2 基于結點的限制

基于結點的限制主要有交叉口的禁行，及交叉口的禁止轉向問題，單純的交叉口的禁行問題與基于邊線的限制問題的解決方法類似，但是，由于在圖論的應用數學中沒有關于結點方位和路徑走向的數學描述，使得交叉口的禁止轉向問題的解決比較復雜。為了解決交叉口的禁止轉向問題，需要用一種能夠快速獲取路徑走向的方式來存儲轉向信息。筆者采用轉向表的方式來存儲轉向信息，對于每個結點及其所連接的邊線，記錄由該邊線經過該結點所能到達的相鄰邊線。連接邊之間的轉向關系，筆者采用char的8位來表示，將該邊線可以到達的相鄰邊線在結點-邊線表中的相對位置處標記為1，轉向表與結點-邊線拓撲表、結點-邊線拓撲擴展表的排列格式完全一樣，偏移位置根據結點-邊線拓撲表來獲取。

例如在圖1道路網絡G中的轉向限制為:結點1處禁止邊線2轉向邊線3，結點1處禁止邊線2轉向邊線2(即禁止掉頭)，結點4處禁止邊線3轉向邊線4，結點4處禁止邊線3轉向邊線9，其轉向表如表4和表5所示。在最優路徑規劃算法的搜索過程中，獲取結點的連接邊線時根據轉向表來判斷該邊線是否可以進行轉向，若不符合條件，則將該邊線舍棄。

3 最優路徑分析算法

Dijkstra系列算法是求解大規模稀疏網絡中一對一的最優路徑問題的最佳選擇，其可以從存儲結構和排序算法上對Dijkstra算法加以改進[3-5]，也可以引入啟發式函數，構建A*算法，還可以采用雙向搜索策略，甚至可以集成使用雙向策略和啟發式策略[6]。由于A*思想的估價函數不容易確定，所以筆者采用雙向搜索策略，并用堆存儲的方法對Dijkstra算法進行改進，結合本文所給出的道路網絡的存儲及各種交通限制條件下的解決方案，給出求解最優路徑規劃的算法，具體過程描述如下:

步驟1:處理起始網標。若給定的起始網標為線上網標，則將邊線的起始結點和終止結點ID添加入最小堆heapFrom中;若為點上網標，則直接將該結點的ID添加入最小堆heapFrom中。

步驟2:處理終止網標。若給定的終止網標為線上網標，則將邊線的起始結點和終止結點ID添加入最小堆heapTo中;若為點上網標，則直接將該結點的ID添加入最小堆heapTo中。

步驟3:從起始網標開始擴展。

1) 若最小堆heapFrom為空，則轉到步驟4;否則將當前處理結點置為堆heapFrom的堆頂元素，即從起始網標開始的權值最小路徑的最末結點ID，并刪除堆頂元素，判斷該結點是否為終止網標，或者為終止網標所在邊線的起始或終止結點，若成立，則路徑規劃成功;判斷該結點是否也被從終止網標擴展的路徑所經過，若成立，則路徑規劃成功。

2) 根據結點-邊線拓撲表和結點-邊線拓撲擴展表來獲取當前處理結點的連接邊，根據交通限制信息依次判斷所有的連接邊是否可以通行，若可以通行，則判斷該連接邊所相鄰的結點是否已經存在于最小堆heapFrom中，若不存在，則將連接邊的連接結點及其相關信息添加到最小堆heapFrom中;若存在，則判斷當前處理結點的路徑權值是否小于已經存在于最小堆heapFrom中的結點的路徑權值，若小于，則用當前處理結點的相關信息替換已經存在的結點的相關信息。

步驟4:從終止網標開始擴展，其擴展方式與從起始網標擴展相似。

1) 若最小堆heapTo為空，則轉到步驟5;否則將當前處理結點置為堆heapTo的堆頂元素，即從終止網標開始的權值最小路徑的最末結點ID，并刪除堆頂元素，判斷該結點是否為起始網標，或者為起始網標所在邊線的起始或終止結點，若成立，則路徑規劃成功;判斷該結點是否也被從起始網標擴展的路徑所經過，若成立，則路徑規劃成功。

2) 根據結點-邊線拓撲表和結點-邊線拓撲擴展表來獲取當前處理結點的連接邊，根據交通限制信息依次判斷所有的連接邊是否可以通行，若可以通行，則判斷該連接邊所相鄰的結點是否已經存在于最小堆heapTo中，若不存在，則將連接邊的連接結點及其相關信息添加到最小堆heapTo中;若存在，則判斷當前處理結點的路徑權值是否小于已經存在于最小堆heapTo中的結點的路徑權值，若小于，則用當前處理結點的相關信息替換已經存在的結點的相關信息。

3) 轉到步驟3。

步驟5:路徑規劃失敗。

4 結束語

基于以上理論分析，筆者在Visual Studio6.0環境下，利用文件作為道路網絡數據的存儲方式，實現了最優路徑規劃算法，為了驗證該道路網絡模型及算法的正確性及可行性，筆者在處理器AMD SempronTM 2500+ 1.41GHz，內存為448MB的硬件配置環境下，根據北京市道路數據建立道路網絡，共包含34265條邊線和22889個結點，并進行單對結點間的最優路徑分析實驗，運行時間一般為0.2秒左右，時間性能參數說明本文提出的道路網絡模型及最優路徑規劃算法具有可行性，可滿足一般基于道路網絡的最優路徑分析的需要，并且該模型考慮了實際道路中的交通限制信息，使得得到的路徑規劃結果更符合人們的實際需要和思維方式，具有一定的應用價值。

參考文獻:

[1] 許志海，張昭云.交通限制條件下的最短路徑算法分析與優化[J].測繪學院學報，2005，22(1):22-68.

[2] 鄒旭東，鄭四發，班學鋼，等.具有交通限制約束的道路網絡最優路徑算法[J].公路交通科技，2002，19(4):82-84.

[3] 陸鋒，盧冬梅，崔偉宏.基于四叉堆優先級隊列及逆鄰接表的改進型Dijkstra算法[J].中國圖象圖形學報，1999，4A(12):1044-1050.

[4] 樂陽，龔健雅.Dijkstra最短路徑算法的一種高效率實現[J].武漢測繪科技大學學報，1999，24(3):209-212.

[5] 王杰臣，毛海城，楊得志.圖的節點-弧段聯合結構表示法及其在GIS最優路徑選取中的應用[J].測繪學報，2000，29(1):47-51.

[6] 鄭年波，李清泉，徐靜海，等.基于轉向限制和延誤的雙向啟發式最短路徑算法[J].武漢大學學報:信息科學版，2006，31(3):256-259.