城市路網(wǎng)交通流的數(shù)學(xué)模型及仿真

鐘建新，王照生

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

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

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

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

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

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

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

（二）模型建立

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

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

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

1.蜂群智能算法

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

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

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

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

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

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

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

c．如果N=2，為了模型普遍適用性，這里假設(shè)禁行路段附近不能通行的所有路段為一個禁行路段群。選取禁行路段群東北角路段坐標(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時，或者當(dāng) Cx=R′x，R′y〈Cy〈Ry且 Dx≥Rx，R′y〈Dy〈Ry時，如果 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時，或者當(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)時，執(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時，O={南}，當(dāng) Cx=Dx且 Cy〈Dy時，O={北}，當(dāng) Cy=Dy且 Cx〉Dx時，O={西}，當(dāng) Cy=Dy且 Cx〈Dx時，O={東}；執(zhí)行步驟(5)；

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

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

b．根據(jù)輸出端口對應(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)確定輸出端口：如果最短路徑輸出端口集合中僅存在一個輸出端口，選擇該端口作為輸出端口；如果最短路徑輸出端口集合中存在兩個輸出端口，選擇輸出端口選擇代價小的作為輸出端口。

二、計算機仿真研究

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

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

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

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

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

表1 在編路段長度

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

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

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

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

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

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

三、結(jié)論

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

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

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