陳端芝

(福建財(cái)會(huì)管理干部學(xué)院 計(jì)算機(jī)系，福建 福州350001)

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

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

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

第三類(lèi)是借助GIS 數(shù)據(jù)庫(kù)技術(shù)，結(jié)合 Dijkstra 算法來(lái)實(shí)時(shí)尋優(yōu)，如文獻(xiàn)[4，5]等.

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

1 層次空間路徑選擇算法

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

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

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

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

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

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

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

(5)若i

2 費(fèi)用計(jì)算公式與數(shù)據(jù)庫(kù)設(shè)計(jì)

2.1 費(fèi)用計(jì)算公式

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

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

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

(1)

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

(2)轉(zhuǎn)向延誤計(jì)算公式.采用美國(guó)《通行能力手冊(cè)》的延誤公式[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)絡(luò)上的節(jié)點(diǎn)，即交叉口；dijh：流向(i，j，h)的延誤時(shí)間；Xijh：從路段(i，j)流向h上的交通流量(含路段(i，j))；

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

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

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

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

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

表1為動(dòng)態(tài)路段費(fèi)用表.用于記錄各路段不同時(shí)段費(fèi)用.

表2為動(dòng)態(tài)轉(zhuǎn)向費(fèi)用表.用于記錄某轉(zhuǎn)向節(jié)點(diǎn)的轉(zhuǎn)向費(fèi)用，服務(wù)器端負(fù)責(zé)維護(hù)整個(gè)表.

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

表4為時(shí)段劃分說(shuō)明表.

表1 路段費(fèi)用庫(kù)

表2 轉(zhuǎn)向費(fèi)用庫(kù)

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

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

表4 時(shí)段劃分說(shuō)明表

3 帶轉(zhuǎn)向的路徑選擇求解算法設(shè)計(jì)

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

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

Cb=Ca+σab+Pb，

Pb=Pa，

同時(shí)將b加入Q.重復(fù)以上步驟，直到Q為空，這時(shí)得到了從r到所有弧的最短路徑.其中σab表示弧a到弧b的轉(zhuǎn)向費(fèi)用.

算法運(yùn)行過(guò)程中， 使用一個(gè)最小四叉堆Heap來(lái)存放標(biāo)記的弧段對(duì)象， 堆元素的關(guān)鍵字是起始點(diǎn)到該弧段的最小時(shí)間開(kāi)銷(xiāo).算法偽代碼如下:

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

Begin algorithm:

Heap設(shè)置為空;

k.m_V=0;

for (每個(gè)弧段標(biāo)號(hào)) { //初始化

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

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

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

i.turn=0; // i.trun 是弧段i的時(shí)間權(quán)值

i.P = K; }

Heap.Insert (k.m_V，k) ; //把弧段對(duì)象以當(dāng)前費(fèi)用為關(guān)鍵字插入最小四叉堆

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

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

double min;int arc；

Heap.ExtractMin (&min， arc);

//堆彈出元素當(dāng)前費(fèi)用最小的弧段arc及其費(fèi)用min;

if ( arc 的終點(diǎn)是b) { //目的弧段已被永久標(biāo)記

return arc;

Break; //算法結(jié)束， 搜索成功. }

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) ; //把該弧段對(duì)象插入堆 }

}

}

End algorithm

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

4 算法驗(yàn)證

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

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

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

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

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

圖2 轉(zhuǎn)身對(duì)路徑選取的影響

4.2 測(cè)試結(jié)果與Dijkstra算法對(duì)比

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

表5 運(yùn)行時(shí)間比較

注：本算法在給道路賦予實(shí)際權(quán)值后就“鼓樓區(qū)政府-西禪寺”、“鼓樓區(qū)政府-省政府”、“鼓樓區(qū)政府-倉(cāng)山區(qū)政府”等路徑誘導(dǎo)的測(cè)試結(jié)果和出租車(chē)司機(jī)的一般行駛路線(xiàn)較為一致.

5 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1]鄭大永，鄭宏劍.汽車(chē)無(wú)線(xiàn)通信平臺(tái)系統(tǒng)[J].中國(guó)無(wú)線(xiàn)電，2007(7):33-35.

[2]Shelley lee.國(guó)外智能交通系統(tǒng)簡(jiǎn)介[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ī)劃理論及其應(yīng)用[M].南京:東南大學(xué)出版社，1998 .

[6]李楷，鐘耳順，曾志明，等.基于分層網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的最優(yōu)路徑算法[J].中國(guó)圖象圖形學(xué)報(bào)，2006(7):1004-1009.

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

[8]美國(guó)交通研究委員會(huì).道路通行能力手冊(cè)[M].北京:人民交通出版社，2007.

[9]陳端芝.基于分層交通網(wǎng)絡(luò)的動(dòng)態(tài)路徑選擇模型研究 [D].福州:福州大學(xué)，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.