鐘建新，王照生

(贛州師范高等?？茖W(xué)校，江西 贛州 341000)

社會(huì)經(jīng)濟(jì)的發(fā)展和城市化水平的不斷提高，對(duì)城市交通提出了越來(lái)越高的要求。目前，城市交通擁擠和交通事故頻發(fā)嚴(yán)重地困擾著交通管理部門(mén)和出行者，解決這些問(wèn)題成為緩解城市交通壓力的迫切需要，也是加快城市化進(jìn)程需要研究的一個(gè)重要課題。近年來(lái)，電子通信技術(shù)的飛速發(fā)展及智能運(yùn)輸系統(tǒng)的產(chǎn)生得到世界各國(guó)的普遍關(guān)注，借助這些技術(shù)，開(kāi)發(fā)城市汽車(chē)導(dǎo)航系統(tǒng)，實(shí)現(xiàn)路網(wǎng)信息的集成與共享，對(duì)改善路網(wǎng)擁擠與提高道路通行能力卓有成效。

目前，全球定位技術(shù)和雙向信息傳遞技術(shù)已經(jīng)趨向成熟，只需進(jìn)行相應(yīng)的改進(jìn)和有機(jī)結(jié)合，就可以實(shí)現(xiàn)車(chē)輛定位和各種信息的傳送和轉(zhuǎn)化。因此，在汽車(chē)導(dǎo)航系統(tǒng)中，尚未解決的是導(dǎo)航依據(jù)和方法問(wèn)題，即為用戶選擇怎樣的出行路徑才能滿足用戶的不同出行目的和需要，并且達(dá)到避免擁擠、提高整個(gè)路網(wǎng)使用效率的目的。如何在短時(shí)間內(nèi)獲取路網(wǎng)和用戶信息，以及如何根據(jù)這些信息快速確定出最優(yōu)出行路徑。這是運(yùn)輸領(lǐng)域的一個(gè)前沿理論問(wèn)題，即“動(dòng)態(tài)路徑選擇”問(wèn)題，其優(yōu)劣將直接影響汽車(chē)導(dǎo)航系統(tǒng)進(jìn)而整個(gè)系統(tǒng)的造價(jià)和功能。

近年來(lái)，世界各國(guó)在這個(gè)領(lǐng)域進(jìn)行了深入地研究，取得了比較可觀的成果，但所建模型普遍存在著約束條件苛刻、計(jì)算量大、優(yōu)化時(shí)間長(zhǎng)等問(wèn)題。最早的分配模型是以起訖點(diǎn)間路徑的長(zhǎng)短來(lái)選擇最短路徑的，這種方法顯然不符合復(fù)雜多變的城市交通流，傳統(tǒng)的動(dòng)態(tài)分配模型是根據(jù)已知路網(wǎng)系統(tǒng)的OD交通量預(yù)測(cè)出各路段的交通流量，這種模型也不能解決交通流隨時(shí)可能發(fā)生變化這一問(wèn)題實(shí)際；路徑選擇問(wèn)題是一個(gè)NP難問(wèn)題，隨著求解問(wèn)題規(guī)模的擴(kuò)大，現(xiàn)有的智能算法，例如蟻群算法在求解這類問(wèn)題的時(shí)候，難免會(huì)碰到陷入局部最優(yōu)解和收斂速度慢的問(wèn)題。因此，現(xiàn)有的求解模型和算法都難以滿足實(shí)際汽車(chē)導(dǎo)航的需要，而蜂群智能算法因?yàn)槠淇焖俚氖諗克俣群苓m合用來(lái)解決這類問(wèn)題?；谶@點(diǎn)，本文提出了一種城市道路汽車(chē)導(dǎo)航算法，建立了城市汽車(chē)導(dǎo)航系統(tǒng)路徑選擇分配模型，并且采用蜂群智能算法求解了該模型，仿真結(jié)果表明了算法的有效性和實(shí)用性。

一、城市汽車(chē)導(dǎo)航路徑選擇模型

（一）汽車(chē)導(dǎo)航系統(tǒng)控制影響因素分析

城市交通流復(fù)雜多變，交通密度差別很大，以路徑長(zhǎng)短為唯一參變量進(jìn)行研究具有很大的局限性。因此，具有實(shí)際應(yīng)用價(jià)值的汽車(chē)導(dǎo)航系統(tǒng)必須綜合考慮復(fù)雜的交通影響因素。出行者根據(jù)道路交通實(shí)時(shí)情況，會(huì)對(duì)出行時(shí)間和出行路線進(jìn)行調(diào)整，以減少路上時(shí)間的消耗；起訖點(diǎn)間的最優(yōu)路徑將隨著交通流的實(shí)時(shí)變化而發(fā)生改變；高峰時(shí)段的交通流造成的交通擁堵在時(shí)空上具有不穩(wěn)定性。通過(guò)大量的文獻(xiàn)研究和調(diào)查，影響城市出行者出行時(shí)間的最主要因素不是路徑的長(zhǎng)短，而是起訖點(diǎn)間各路段的綜合通行能力。本文為了便于研究又不失一般性，選取兩個(gè)最主要的影響因素，即路徑長(zhǎng)短和交通擁擠程度進(jìn)行對(duì)比研究，給出模型并進(jìn)行仿真，得到了比較滿意的結(jié)果。

（二）模型建立

城市交通流狀況錯(cuò)綜復(fù)雜，并且始終都在變化。出行車(chē)輛根據(jù)出發(fā)時(shí)刻動(dòng)態(tài)交通網(wǎng)絡(luò)各條邊的權(quán)值來(lái)計(jì)算從第一個(gè)節(jié)點(diǎn)到終點(diǎn)的最佳路徑，到達(dá)第二個(gè)節(jié)點(diǎn)前，交通網(wǎng)絡(luò)里的各條邊的權(quán)值隨時(shí)間和交通流信息而發(fā)生了變化，相應(yīng)地，出行車(chē)輛的最優(yōu)路徑也會(huì)發(fā)生變化，因此，出行車(chē)輛在此時(shí)此刻以第二個(gè)節(jié)點(diǎn)為起點(diǎn)，重新組合優(yōu)化網(wǎng)絡(luò)，來(lái)計(jì)算從該節(jié)點(diǎn)到終點(diǎn)的最佳路徑，以決定車(chē)輛到達(dá)第二個(gè)節(jié)點(diǎn)時(shí)應(yīng)該向哪一條道路轉(zhuǎn)向，以此類推，在這種情況下，車(chē)輛到達(dá)終點(diǎn)時(shí)遍歷的路徑是最優(yōu)路徑。

模型中以出行時(shí)間為優(yōu)化目標(biāo)函數(shù)，將路段的擁擠程度分級(jí)，并對(duì)路段通行能力，即車(chē)流大小進(jìn)行賦權(quán)。把動(dòng)態(tài)交通網(wǎng)絡(luò)圖規(guī)范成為一個(gè)平面圖，研究時(shí)取東南西北四個(gè)方位，模型每一路段用坐標(biāo)表示。模型將出行者要到達(dá)目的地所經(jīng)過(guò)的路段分為三種，由信息搜集系統(tǒng)讀取當(dāng)前路段的位置(Cx,Cy)與當(dāng)前路段類型值N，根據(jù)路段類型值判斷該路段類型：當(dāng)N＝0時(shí)，當(dāng)前路段為較為擁擠路段；當(dāng)N＝1時(shí)，當(dāng)前路段為正常通行路段；當(dāng)N＝2時(shí)，當(dāng)前路段為交通事故路段或施工禁行路段。一般用戶出行優(yōu)先級(jí)P＝0，為低優(yōu)先級(jí)分組；軍用以及其他一些高優(yōu)先級(jí)用戶P＝1。

（三）算法實(shí)現(xiàn)步驟

1.蜂群智能算法

蜂群算法是一種新型的元啟發(fā)式仿生算法。它是模仿蜜蜂行為提出的一種優(yōu)化方法，是集群智能思想的一個(gè)具體應(yīng)用，它的主要特點(diǎn)是不需要了解問(wèn)題的特殊信息，只需要對(duì)問(wèn)題進(jìn)行優(yōu)劣的比較，通過(guò)各人工蜂個(gè)體的局部尋優(yōu)行為，最終在群體中使全局最優(yōu)值突現(xiàn)出來(lái)，有著較快的收斂速度。將蜂群算法做一改進(jìn)，運(yùn)用到本模型中，提高了全局搜索能力，具有較快的收斂速度。

2．蜂群算法實(shí)現(xiàn)步驟

（1）讀取當(dāng)前路段的坐標(biāo)(Cx,Cy)與當(dāng)前路段類型值N；

（2）讀取用戶目的路段坐標(biāo)(Dx,Dy)與該用戶的優(yōu)先級(jí)值P；根據(jù)該優(yōu)先級(jí)值判斷分組優(yōu)先級(jí)：當(dāng)P=0時(shí)，分組為低優(yōu)先級(jí)分組，當(dāng)P=1時(shí)，分組為高優(yōu)先級(jí)分組；

（3）根據(jù)當(dāng)前路段坐標(biāo)(Cx,Cy)、目的路段坐標(biāo)(Dx,Dy)、當(dāng)前路段類型和分組優(yōu)先級(jí)確定最短路徑輸出端口集合：O={o|o?(東，南，西，北，本地)}：

a．如果 Cx=Dx且 Cy=Dy，則 O={本地}，執(zhí)行步驟(5)，否則執(zhí)行步驟b；

b．如果 N=0，當(dāng)時(shí) P=0，執(zhí)行步驟 c；當(dāng) P=1 時(shí)，執(zhí)行步驟d；

c．如果N=2，為了模型普遍適用性，這里假設(shè)禁行路段附近不能通行的所有路段為一個(gè)禁行路段群。選取禁行路段群東北角路段坐標(biāo)(Rx，Ry)和西南角路段坐標(biāo)(R′x，R′y)；根據(jù)當(dāng)前路段坐標(biāo)（Cx，Cy）、目的路段坐標(biāo)（Dx，Dy）、禁行或者擁擠路段的東北角路段坐標(biāo)（Rx，Ry）和西南角路段坐標(biāo)（R′x，R′y）確定最短繞道路徑的輸出端口：

(a) 當(dāng) Cx=Rx，R′x〈Cy〈Ry且 Dx≤R′x,R′y〈Dy〈Ry時(shí)，或者當(dāng) Cx=R′x，R′y〈Cy〈Ry且 Dx≥Rx，R′y〈Dy〈Ry時(shí)，如果 Cy+Dy-Ry-R′x≥0，則 O={北}，否則 O={南}；

(b)．當(dāng) Cy=R′y，R′x〈Cy〈Ry且 Dy≤R′y，R′x〈Dx〈Rx時(shí)，或者當(dāng) Cy=Ry，R′x〈Dx〈Rx且 Dy≤R′y，R′x〈Dx〈Rx是，如果 Cx+Dx-Rx-R′x≥0，則 O={東}，否則 O={西}；

滿足上述(a)或(b)時(shí)，執(zhí)行步驟(5)；其它情況下執(zhí)行步驟d；

d．如果 N=1，根據(jù)當(dāng)前路段坐標(biāo)（Cx，Cy）和目的路段坐標(biāo)（Dx，Dy）確定最短路徑輸出口集合O={o|o?(東，南，西，北，本地)}：

(a)當(dāng) Cx=Dx且 Cy〉Dy時(shí)，O={南}，當(dāng) Cx=Dx且 Cy〈Dy時(shí)，O={北}，當(dāng) Cy=Dy且 Cx〉Dx時(shí)，O={西}，當(dāng) Cy=Dy且 Cx〈Dx時(shí)，O={東}；執(zhí)行步驟(5)；

(b)當(dāng) Cx〉Dx且 Cy〈Dy時(shí)，O={西，南}，當(dāng) Cx〉Dx且Cy〉Dy時(shí)，O={西，北}，當(dāng) Cx〈Dx且 Cy〈Dy時(shí)，O={西，南}，當(dāng) Cx〉Dx且 Cy〉Dy時(shí)，O={東，北}；執(zhí)行步驟(4)，從當(dāng)前路段讀取輸出端口對(duì)應(yīng)下一路段的狀態(tài)參數(shù)并計(jì)算輸出端口的選擇代價(jià)：

(4)a．根據(jù)當(dāng)前路段坐標(biāo)（Cx，Cy）和輸出端口判斷輸出端口對(duì)應(yīng)的下一路段坐標(biāo)（Nx，Ny）：當(dāng)輸出端口為東時(shí)，（Nx，Ny）=（Cx+1，Cy），輸出端口為西時(shí)，（Nx，Ny）=（Cx-1，Cy），當(dāng)輸出端口為南時(shí)，當(dāng) （Nx，Ny）=（Cx1，Cy-1）輸出端口為北時(shí)，（Nx，Ny）=（Cx，Cy+1）；

b．根據(jù)輸出端口對(duì)應(yīng)的下一路段坐標(biāo)（Nx，Ny）、禁行路段的東北角路段坐標(biāo)（Rx，Ry）和西南角路段坐標(biāo)（R′x，R′y），判斷下一路段是否屬于禁行路段：當(dāng)R′x〈Nx〈Rx且 R′y〈Ny〈Ry，下一路段為禁行路段，令w3=9999，否則，令 w3=1；

(5)確定輸出端口：如果最短路徑輸出端口集合中僅存在一個(gè)輸出端口，選擇該端口作為輸出端口；如果最短路徑輸出端口集合中存在兩個(gè)輸出端口，選擇輸出端口選擇代價(jià)小的作為輸出端口。

二、計(jì)算機(jī)仿真研究

城市汽車(chē)導(dǎo)航系統(tǒng)路徑選擇分配優(yōu)化程序采用C語(yǔ)言程序運(yùn)行通過(guò)。為驗(yàn)證模型的實(shí)用價(jià)值，選擇贛州市章貢區(qū)作為仿真研究的對(duì)象，贛州市章貢區(qū)的交通地圖，如圖1所示。

模型假設(shè)出行者從圖1右上角贛南醫(yī)學(xué)院出發(fā)，目的地是左下角的贛州黃金機(jī)場(chǎng)。地圖優(yōu)化函數(shù)為出行者從出發(fā)點(diǎn)到達(dá)目的地所需花費(fèi)的總時(shí)間，要求出行者根據(jù)當(dāng)前的實(shí)時(shí)交通狀況，選擇一條最短時(shí)間到達(dá)的路線。

實(shí)際交通圖路況復(fù)雜，且不便于量化研究。為了方便研究，將交通圖進(jìn)行簡(jiǎn)化，省去車(chē)輛不可能行駛的路段，將車(chē)輛首先選取章貢區(qū)某個(gè)交通流量時(shí)段的交通進(jìn)行研究，對(duì)該時(shí)段各條路段上的交通流大小進(jìn)行賦權(quán)，仿真得到最短時(shí)間的路線比較圖見(jiàn)圖2。實(shí)線箭頭代表的是最短路徑到達(dá)，虛線是仿真程序得到的最優(yōu)路徑，通過(guò)對(duì)比到達(dá)時(shí)間可以發(fā)現(xiàn)，仿真得到的路線優(yōu)于最短路徑。

圖1 贛州市章貢區(qū)交通地圖

在編各路段的長(zhǎng)度根據(jù)地圖比例尺計(jì)算得出如表1。

表1 在編路段長(zhǎng)度

B2C4 500 C4D1 100 D2E4 100 B3C5 500 C5D2 100 D3E5 200 F4F5 200 A3C6 800 C6D3 100 F1F2 200

單一實(shí)例不具有說(shuō)服力，對(duì)一天當(dāng)中16個(gè)不同車(chē)流量時(shí)段各條道路上的車(chē)流分別賦權(quán)，仿真程序在靜態(tài)網(wǎng)絡(luò)的最短距離下和動(dòng)態(tài)網(wǎng)絡(luò)的路徑最優(yōu)兩種情況下，得出結(jié)果如圖3所示。

圖3橫坐標(biāo)為起訖點(diǎn)間所選路段集合的一個(gè)交通流權(quán)值平均，縱坐標(biāo)為通過(guò)總時(shí)間，單位為分鐘。利用Excel軟件，菱形線表示靜態(tài)交通網(wǎng)絡(luò)下的最短路徑通過(guò)時(shí)間，隨著交通流的增大時(shí)間也相應(yīng)增大；方形線表示動(dòng)態(tài)交通流下最優(yōu)路徑通過(guò)時(shí)間，隨著交通流的增大時(shí)間也相應(yīng)增大。X－交通流，Y－最短路徑。

圖2 贛州市章貢區(qū)交通簡(jiǎn)化圖

圖3 動(dòng)態(tài)優(yōu)化路徑選擇情況

通過(guò)仿真可以發(fā)現(xiàn)，在相同交通流權(quán)值平均下，選擇最小交通流下最優(yōu)路徑所需的通過(guò)時(shí)間要小于選擇靜態(tài)交通網(wǎng)絡(luò)下最短路徑所需的通過(guò)時(shí)間。實(shí)驗(yàn)結(jié)果表明：對(duì)于城市交通而言，最優(yōu)路徑并不是距離最短路徑，而應(yīng)該是最不擁擠的路徑，本質(zhì)上是時(shí)間最省路徑。本文的優(yōu)化模型與算法是在每下一路段前通過(guò)雙向信息傳輸技術(shù)得到的車(chē)流信息進(jìn)行一次比較計(jì)算，具有實(shí)際應(yīng)用價(jià)值。對(duì)本文的仿真來(lái)說(shuō)，車(chē)輛的行駛速度與實(shí)際是一樣的，并且簡(jiǎn)化的贛州市章貢區(qū)交通圖也與實(shí)際基本相符，對(duì)于更大規(guī)模的交通網(wǎng)絡(luò)同樣適用。利用本算法，對(duì)城市交通網(wǎng)絡(luò)的路徑優(yōu)化是有效的。

三、結(jié)論

在動(dòng)態(tài)城市交通網(wǎng)絡(luò)里，靜態(tài)網(wǎng)絡(luò)下的最短路徑并不一定是最優(yōu)路徑，在擁擠的城市交通網(wǎng)絡(luò)中，出行車(chē)輛從距離最短路徑的起點(diǎn)到終點(diǎn)花費(fèi)的時(shí)間往往要大于交通順暢的距離較長(zhǎng)路徑。同時(shí)，也說(shuō)明交通網(wǎng)絡(luò)里，節(jié)點(diǎn)之間靜態(tài)距離越短，車(chē)流量越大，就越容易造成車(chē)流堵塞，不利于車(chē)輛快速通行。

[1]楊兆升,姜桂艷．城市交通流誘導(dǎo)系統(tǒng)結(jié)構(gòu)框架研究[J]．公路交通科技,2007,(4)：15－17．

[2]許倫輝．基于最短路徑算法的用戶最優(yōu)動(dòng)態(tài)配流模型[J]．暨南大學(xué)學(xué)報(bào),2008,(19)：23－26．