城市動態時間最短路徑誘導系統實現研究
劉張雷，史忠科
（西北工業大學白動化學院，陜西西安71 0129）
摘 要：就城市路同動態時間最短路徑誘導系統的實現展開研究：針對鄰接表和鄰接矩陣在保存完整的路網信息時出現高冗余并導致算法計算時間成倍增加的現象，以改進的前向關聯邊結構作為路網的存儲結構，并依此對dijkstra算法進行改進，用于路網節點之間動態時間最短路徑的求取，在此基礎上，基于市區實時交通流數據和相位配時信息，結合高精度交通電子地圖，開發了東莞市動態路徑誘導系統進行實驗仿真。該系統針對改進后的算法與原算法的差異，設置了靜態和動態兩種最短路徑計算模式，對兩種模式的計算時間和計算結果進行了對比。結果表明改進算法能夠在不增加時間復雜度的前提下，充分考慮動態交通流狀況、交叉口限向和轉向延誤，有效解決城市路網動態時間最短路徑問題。
關鍵詞：動態時間最短路徑；前向關聯邊；dijkstra
申圖分類號：tp 27 文獻標識碼：a
1引言
城市路網動態時間最短路徑的計算，不僅要考慮交叉口之間路段上的行程時間，還需要考慮交叉口各轉向的信號相位延誤和轉向限制。因此，路網的存儲結構不僅要能夠存儲路段權重，還要體現交叉日節點自身的權重。
解決這個問題的一般思路是通過城市路網轉換模型，把節點權重轉換為邊的權重，從而實現城市路網圖向普通賦權有向圖的轉換，再利用鄰接矩陣或鄰接表存儲轉換后的有向圖。
本文首先就鄰接矩陣或鄰接表存儲轉換路網信息這一方法展開分析，指出了它容易造成存儲空間高冗余并導致算法汁算時間成倍增加的弊端。由此，本文采用一種改進的前向關聯邊結構作為存儲結構，同時依照此結構對dijkstra算法進行了改進，并開發了東莞市動態路徑誘導系統進行動態時間最短路徑求取的實驗，實驗結果表明改進算法能夠在不增加時間復雜度的前提下，充分考慮交叉口限向和轉向延誤，有效解決城市路網動態時間最短路徑問題。
2鄰接矩陣或鄰接表存儲轉換路網信息時的弊端
常用的路網模型轉換方法有兩種：增設虛擬邊法和對偶圖法。增設虛擬邊法根據交叉口實際構造（丁字路口、十字字路口或其他），將此交叉口節點進行一對多的擴展。并將各個可行的轉向以虛擬有向線段加以表示，該轉向的延誤對應于有向線段的權值。利用這種方法，可以從路網圖中清晰地看出，交叉口哪些入口禁止左轉，同時電能夠看到各個直行、左轉或右轉路線在此交叉口的延誤時間。但由于在交叉口進行節點擴展時，它將路網的節點數擴大了8倍。設城市路網包括n個交叉日，由上述分析中已知一個十字路口節點經增設虛擬邊處理后變成了8個節點表示，如圖l，圖2所示．
假設以鄰接表：3l存儲有向圖的方式存儲轉換后的路網信息，并采用算法復雜度的dijkstra算法進行時問最短路徑的計算，所需運算時間相應要擴大64倍。對偶圖法是一種新穎的路網結構表示形式，將路段以圖中節點表示，交叉日各個路口轉向以有向線段表示；路段的權重轉化為節點的權熏，交叉口各轉向延誤轉化為相應有向線段的權值。它同樣使得路網的節點數成倍地擴張，如果也以鄰接表作為存儲結構，也會導致計算時間的成倍增長。
3 改進的前向關聯邊結構
前向關聯邊結構最早由dial等人在1979年提出。對于n個交叉口，m條路段的城市路網。這種結構利用一個一維數組pointednodes，按n個節點的編號順序，依次保存從各個節點出發的有向線段的終止節點的編號，同時用另外一個一維數組traveltime來保存各條有向線段的相應權值（對于時問最短路徑問題，權值取該路段的行程時間），pointednodes數組和traveltime數組都占用了m個存儲單元。由每個節點出發的有向線段不止一條，即路網中各個節點的出度大于等于1，pointednodes數組中對應于每個節點的終止節點的個數也是大于等于1的。前向關聯邊結構用一維數組pointer，保存各個起始節點所指向的第一個終止節點在數組中的索引值，pointer數組占用的存儲單元數與路網節點數是相同的。
|
