一種基于分層交通網(wǎng)絡的動態(tài)路徑選擇算法

陳端芝

(福建財會管理干部學院 計算機系，福建 福州350001)

許多導航儀只能提供一種較為初級的出行者系統(tǒng).根本原因是所基于的信息是靜態(tài)交通網(wǎng).動態(tài)交通網(wǎng)與靜態(tài)交通網(wǎng)不同的表現(xiàn)在于每一時刻每條道路的阻抗不同，每一轉向延誤也不同.目前在國內外動態(tài)最短路徑研究主要有以下三類思想.

第一類是以傳統(tǒng)的靜態(tài)算法思想為基礎，通過引入時間要素，將其應用到動態(tài)的最優(yōu)路徑尋優(yōu)中來.如動態(tài)的 Dijksta 算法思想[1].

第二類是通過對道路交通流的建模，綜合考慮各種動態(tài)因素對最優(yōu)路徑選取的影響來選取實時的最優(yōu)路徑.如建立道路交通流的變分不等式模型[2]和隨機時間依賴網(wǎng)絡模型[3]等.

第三類是借助GIS 數(shù)據(jù)庫技術，結合 Dijkstra 算法來實時尋優(yōu)，如文獻[4，5]等.

本文結合我國國情，通過修改層次空間推理模型，構造監(jiān)控數(shù)據(jù)庫來反映時段數(shù)據(jù)，在計算時根據(jù)不同分區(qū)路段信息加載時段數(shù)據(jù)，然后依據(jù)所得網(wǎng)絡結構求解動態(tài)最短路徑.

1 層次空間路徑選擇算法

多數(shù)道路層次推理模型，如文獻[6][7]中提出的推理模型都是將路網(wǎng)結構分層次存儲，不斷運用平面算法求出從低層節(jié)點(不論起止點)所在層次求出上層網(wǎng)絡入口節(jié)點路徑，直到所求得的節(jié)點與目標節(jié)點在同一層次時，再運用一次平面算法獲得在該層次的路徑，最后將所得到的不同層次的路徑整合而得到解.這些模型在理論上具有一定可行性，但實際運用中有三個缺陷.

(1)道路是有方向性的，各方向路段費用不同，而且實際路網(wǎng)都存在交通控制信息.網(wǎng)絡結構隨時間變化.(2)實際上有時在某個片區(qū)內支路的平均流速比干路快得多，達到已經(jīng)可以忽略支路不良因素影響的程度，這時區(qū)內支路比干路更具優(yōu)勢.(3)實際道路并不能橫、縱分割形成標準網(wǎng)格，所能形成的是近似網(wǎng)格.網(wǎng)格相同、相鄰或相間的判斷就與網(wǎng)格編號有關.

本文結合福州道路網(wǎng)絡特點改造層次空間路徑選擇算法，采用節(jié)點、路段信息分兩層存儲，計算時合并計算，具體描述如下：

(1)決定起算節(jié)點(選擇層次較低的節(jié)點，即Bj為層次j的節(jié)點).

(2)提取Bj所在網(wǎng)格數(shù)據(jù)并入上層(層次k)網(wǎng)格數(shù)據(jù).

(3)若i=k，轉(4)否轉(5).

(4)判斷Ai和Bj所在的層次k網(wǎng)格是否相同、相鄰或相間，是則提取相應網(wǎng)格并入上層網(wǎng)格數(shù)據(jù)，后采用平面算法計算.相同、相鄰或相間的判斷改為判定提取的網(wǎng)格個數(shù)，相鄰判斷依據(jù)是橫向或縱向實際提取的網(wǎng)格個數(shù)為二，相間判斷依據(jù)是橫向或縱向實際提取的網(wǎng)格個數(shù)為三.否則，對所提取各個網(wǎng)格，判斷網(wǎng)格內四個方向流速與干路平均流速的比值是否大于預定的值(不同時段比值不同，通過對10條路段不同時刻交通流實驗，空閑時刻為1，交通擁堵時刻為1.15比較接近駕駛者心理)，若存在有一個以上的方向達到要求，則擴展該網(wǎng)格數(shù)據(jù)至上層數(shù)據(jù)，然后采用平面算法計算.

(5)若i

2 費用計算公式與數(shù)據(jù)庫設計

2.1 費用計算公式

我國的許多交通系統(tǒng)模擬軟件(如“運交之星”等)大都借用美國《通行能力手冊》中的計算公式來估算道路阻抗和轉向延誤.實際道路監(jiān)控系統(tǒng)能提供的各道路流量和各轉向流量，因此將二者聯(lián)系起來，計算各路段和各轉向的費用.

(1)道路阻抗計算公式.用美國公用道路局于1964年提出的BPR模型[8]是最具代表性的研究成果，其形式如下：

t(q)=t0[1+α(qS)β]

(1)

式中t(q)為流量為q時路段上行駛時間；t0為零流量時的行駛時間；S為路段實用通行能力；可以用飽和流量公式計算；α，β為模型參數(shù)，常取α=0.9，β=4.0；t0的計算可采用道路的路段長度除以最大限速，實際流量q由監(jiān)控系統(tǒng)給出，路段實用通行能力S，一般說明為路段設計時所確定的通行能力.

(2)轉向延誤計算公式.采用美國《通行能力手冊》的延誤公式[8]作為交叉口延誤dijh(Xijh)，就有

dijh(xijh)=0.38SijhCjSijh-xijh(1-λijh)2+173(xijhSijhλijh)2

[(xijhSijhλijh-1)+(xijhSijhλijh-1)2+16xijhSijh2λijh]

(2)

上式中，h、i、j:道路網(wǎng)絡上的節(jié)點，即交叉口；dijh：流向(i，j，h)的延誤時間；Xijh：從路段(i，j)流向h上的交通流量(含路段(i，j))；

Sijh:表示進口道(i，j，h)的飽和流量；本計算中Sijh=2000(PCU/h)(對?i、j、h)；

λijh：流向(i，j，h)上的綠信比；十字交叉路口：左轉=0.9，直行=0.30，右轉=1.0；三岔路口：左轉=0.45，右轉=1.0；

Cj：交叉口j的信號周期時間；一般可根據(jù)交叉口路燈的相位來獲得，兩相位40s，三相位60s，四相位80s.

2.2 GIS數(shù)據(jù)庫擴展

為計算動態(tài)最優(yōu)路徑所需的路段權值(路段阻抗和轉向阻抗)可以通過一種查表結合計算的方式來獲得.因此在交管中心要維護這兩個表，要提供給車載設備在某時刻各路段的通行時間以及轉向延誤時間的估計值.為了維護分層模型的運算，實際還要維護分區(qū)時段車流狀態(tài)表.下面列舉了三個表.

表1為動態(tài)路段費用表.用于記錄各路段不同時段費用.

表2為動態(tài)轉向費用表.用于記錄某轉向節(jié)點的轉向費用，服務器端負責維護整個表.

表3為分區(qū)時段車流狀態(tài)表.

表4為時段劃分說明表.

表1 路段費用庫

表2 轉向費用庫

表3 分區(qū)車流狀態(tài)表

注：時段劃分采用非均等時段劃分，對福州市交通監(jiān)控信息處理，將一天的交通狀況劃分為四種情況，具體如下表所示.時段編號是根據(jù)時段劃分從0：00開始進行編號.

表4 時段劃分說明表

3 帶轉向的路徑選擇求解算法設計

分層最短路徑的計算，最終要轉化為平面算法求解.本系統(tǒng)采用十字鏈表分別表示節(jié)點與節(jié)點的鏈接構成路段，再用路段與路段的鏈接構成轉向表示.具體形式可參見文獻[9].

帶轉向的路徑求解算法可以有節(jié)點標號法和弧標號法.本系統(tǒng)選用弧標號算法，弧標號算法的框架由文獻[10]給出.該算法需要管理一個候選弧集Q：對?a∈Q，它的鄰接弧的標號有進一步改進的可能.算法的每一步根據(jù)一定的策略從Q中取出一條弧a對其進行掃描，即檢查a的每條鄰接弧b是否滿足式Cb<=Ca+σab+Pb，若不滿足，則置

Cb=Ca+σab+Pb，

Pb=Pa，

同時將b加入Q.重復以上步驟，直到Q為空，這時得到了從r到所有弧的最短路徑.其中σab表示弧a到弧b的轉向費用.

算法運行過程中， 使用一個最小四叉堆Heap來存放標記的弧段對象， 堆元素的關鍵字是起始點到該弧段的最小時間開銷.算法偽代碼如下:

int SearchRoute ( a， b，e ，tr)//a表示起始點，b表示結束點，e表示弧段集合，tr表示轉向集合，函數(shù)返回與終點相連的路段ID

Begin algorithm:

Heap設置為空;

k.m_V=0;

for (每個弧段標號) { //初始化

double i.m_V= maxValue; //記錄弧段當前最小初始化為最大值

CString i.P = k; //弧段的父親弧段為空 }

for (與起點a直接相連的出度弧段i) {

i.turn=0; // i.trun 是弧段i的時間權值

i.P = K; }

Heap.Insert (k.m_V，k) ; //把弧段對象以當前費用為關鍵字插入最小四叉堆

while (1) { //繼續(xù)搜索

if (Heap為空) return; //搜索失敗， 算法結束

double min;int arc；

Heap.ExtractMin (&min， arc);

//堆彈出元素當前費用最小的弧段arc及其費用min;

if ( arc 的終點是b) { //目的弧段已被永久標記

return arc;

Break; //算法結束， 搜索成功. }

for (弧段arc的所有出度弧段) {

if (min +N.Turn + j .cost

j .m_ V = min + N.Turn + j.cost;

j .P = arc;

Heap.Insert (j.m_V ，j) ; //把該弧段對象插入堆 }

}

}

End algorithm

算法執(zhí)行前要先對數(shù)據(jù)進行處理，對節(jié)點數(shù)據(jù)、路段數(shù)據(jù)、路段——轉向數(shù)據(jù)采用按分區(qū)形式排序，對時段數(shù)據(jù)也如此，不同的是同時按時段排序相同時段數(shù)據(jù)集中存儲，這樣方便連續(xù)讀取數(shù)據(jù).

4 算法驗證

本文采用福州市區(qū)地圖和交通監(jiān)控數(shù)據(jù)信息進行驗證，地圖經(jīng)轉化后并設定分區(qū)如圖1所示.

圖1 福州市區(qū)道路網(wǎng)路

圖1中粗線條為主要干道，細線條為主要支道路，以粗線劃分交通區(qū).交通區(qū)中包含編號信息(兩個數(shù)字分別表示橫縱向編號)，其區(qū)間編號如圖1所示.

4.1 交通網(wǎng)絡轉向引起的路徑的選取變化

圖2列舉了由于引入有向線表示路徑后，基于相同的道路延誤數(shù)據(jù)(白天非交通高峰期)，西禪寺-鼓樓區(qū)政府，將起點和終點互換，最短路徑的結果不一致.而一般導航地圖結果是一致的(求得是最短路徑).圖中線路1描繪的是從西禪寺到鼓樓區(qū)政府的路徑，全程4.1公里，路上行程約9.5分鐘，經(jīng)過5個路口，轉向時間花費3.5分鐘；線路2描繪的是鼓樓區(qū)政府到西禪寺的路徑，全程4.6公里，路上行程也大約11分鐘，經(jīng)過7個路口轉向花費約5.2分鐘.線路3表示一般地圖的最短路徑，路徑長度3.4公里，但經(jīng)過8個路口(西禪寺-鼓樓區(qū)政府)或11個路口(鼓樓區(qū)政府-西禪寺)，可見時間上肯定開銷大.線路1，2兩條路徑所經(jīng)過的路口時最少的，也就是轉向費用是最低的，這也與出租車的駕駛員觀點是一致的.

圖2 轉身對路徑選取的影響

4.2 測試結果與Dijkstra算法對比

模擬試驗共提取交叉點513個，路段數(shù)據(jù)2128個，設定轉向點費用數(shù)據(jù)239014條，道路阻抗數(shù)據(jù)102144條.交叉點中位于主干路的有302個，其中主干路與主干路的交叉點只有49個，有198個屬于干路與支路的三叉型交叉點采用兩相位信號燈機制，城市中一般都采用干路優(yōu)先的管理策略，三叉路口上大多禁止左轉彎，故直行車輛延誤可看作為0，因此，實際在干路進行路徑選擇時大大減少了無謂的計算次數(shù)與比較次數(shù)，優(yōu)化了時間復雜度.由于沒有同類算法，因此本算法僅與Dijkstra算法(取起終點間所有各區(qū)域子層與上層圖合并構成網(wǎng)絡模型)進行比較(見表5).

表5 運行時間比較

注：本算法在給道路賦予實際權值后就“鼓樓區(qū)政府-西禪寺”、“鼓樓區(qū)政府-省政府”、“鼓樓區(qū)政府-倉山區(qū)政府”等路徑誘導的測試結果和出租車司機的一般行駛路線較為一致.

5 結語

隨著我國 ITS水平的不斷提高，最優(yōu)路徑的計算將會逐漸向中心型計算方式轉變.交管中心掌握了關于路網(wǎng)的更多信息，可由交管部門對動態(tài)最優(yōu)路徑問題建立分層搜索數(shù)學模型，再根據(jù)該模型對實時最優(yōu)路徑求解.需要導航的出行者僅需向交通管理中心發(fā)送他在路網(wǎng)中的位置、時間和交通工具的類型等特征參數(shù)，交管中心就可以依據(jù)相應時刻路網(wǎng)和出行者兩方面的信息，選出一條最接近真實情況的最優(yōu)路徑提供給出行者作路徑?jīng)Q策.隨著我國交通智能化水平的提高，新的更符合實際交通狀況的動態(tài)最優(yōu)路徑算法也必將不斷涌現(xiàn).

參考文獻：

[1]鄭大永，鄭宏劍.汽車無線通信平臺系統(tǒng)[J].中國無線電，2007(7):33-35.

[2]Shelley lee.國外智能交通系統(tǒng)簡介[J].數(shù)字社區(qū)&智能—家居，2007(5):76-80.

[3]Wardrop j g .some theoretical aspects of road traffic research[J]. proceeding of institution of civil engineers，1952，11(1).325-378.

[4]Chen H K ， Hsueh C F.A model and an algorithm for the dynamic user-optimal route choice problem[J]. Transportation research，1998，32B(3).219-234.

[5]王煒，徐吉謙，楊濤，等.城市交通規(guī)劃理論及其應用[M].南京:東南大學出版社，1998 .

[6]李楷，鐘耳順，曾志明，等.基于分層網(wǎng)絡拓撲結構的最優(yōu)路徑算法[J].中國圖象圖形學報，2006(7):1004-1009.

[7]李建元，師軍.基于層次空間推理模型的交通網(wǎng)絡最優(yōu)路徑算法[J].計算機工程，2006，32(20):207-209.

[8]美國交通研究委員會.道路通行能力手冊[M].北京:人民交通出版社，2007.

[9]陳端芝.基于分層交通網(wǎng)絡的動態(tài)路徑選擇模型研究 [D].福州:福州大學，2009:30-36.

[10] KIRBY R F，POTTS R B. The minimum route problem for networks with turn penalties and prohibitions[J].Transportation Research，1969，3:397-408.