楊曉穎 紀(jì)道元

（1 北京交通大學(xué),北京 100044；2 雅各布大學(xué)，不來(lái)梅 28719）

引言

隨著社會(huì)的發(fā)展，汽車給人類的出行帶來(lái)了非常大的便捷，但是由于車輛數(shù)量的快速增加使得城市中交通擁堵成了常態(tài)。人們常因不熟悉道路交通狀況、交通擁擠和道路堵塞，導(dǎo)致時(shí)間延誤、疲勞駕駛甚至是交通事故的發(fā)生，這無(wú)疑產(chǎn)生了極大的交通安全隱患，甚至影響了社會(huì)經(jīng)濟(jì)的發(fā)展和人們的日常生活。

幾十年來(lái)國(guó)內(nèi)外的科學(xué)家提出了多種路徑規(guī)劃的求解方法，比如Floyd算法、Dijkstra算法等。其中，F(xiàn)loyd算法易于理解且設(shè)計(jì)方便，在城市最短路徑規(guī)劃中使用非常普遍。國(guó)內(nèi)外學(xué)者對(duì)Floyd算法進(jìn)行了深入的研究[1-5]。徐達(dá)、蔡滿春等人通過(guò)去除中間非必要節(jié)點(diǎn)路徑對(duì)Floyd算法進(jìn)行了改進(jìn)，有效提高了Floyd算法的計(jì)算效率；左秀峰、沈萬(wàn)杰研究了基于Floyd算法的無(wú)相連通圖中多重等價(jià)最短路徑算法；張德全等提出了Floyd加速算法及優(yōu)化方法。

通過(guò)分析發(fā)現(xiàn)，隨著城市道路交通網(wǎng)絡(luò)各種基礎(chǔ)設(shè)施的不斷完善以及現(xiàn)代科技的不斷進(jìn)步與發(fā)展，最優(yōu)路徑規(guī)劃算法也從傳統(tǒng)的靜態(tài)最優(yōu)路徑規(guī)劃向著動(dòng)態(tài)最優(yōu)路徑規(guī)劃方向發(fā)展。但目前的路徑引導(dǎo)系統(tǒng)多是從道路利用者的角度出發(fā)，即使道路利用者的自身出行成本最小，而忽略了道路網(wǎng)絡(luò)的系統(tǒng)平衡。

若從全局角度出發(fā)，即從決策者的角度出發(fā)，先對(duì)道路網(wǎng)的運(yùn)行信息加以分析處理，得到已陷入或即將陷入擁堵的路段信息，在進(jìn)行路徑規(guī)劃時(shí)回避掉這些路段，既能提高道路利用率又能在一定程度上緩解道路網(wǎng)上的交通壓力，加速擁堵路段的疏通。

基于上述考慮，本文將Floyd算法與道路擁擠程度相結(jié)合，得到一種改進(jìn)的最優(yōu)路徑算法。經(jīng)過(guò)算法的編程實(shí)現(xiàn)，得到一條規(guī)避掉擁擠路段的最優(yōu)路徑，比較符合實(shí)際。

1 路段交通狀況判斷

在路徑規(guī)劃中考慮道路擁擠問(wèn)題，必須將道路擁擠這一因素進(jìn)行量化。車輛行駛過(guò)程中，路段上的行車速度是與行車效率最密切相關(guān)的一個(gè)指標(biāo)。若路段上行車速度相對(duì)平時(shí)快，則通過(guò)該路段的時(shí)間相對(duì)少。

根據(jù)我國(guó)公安部2002年公布的相關(guān)標(biāo)準(zhǔn)，目前我國(guó)相關(guān)交通管理部門對(duì)城市道路交通狀態(tài)的量化定義主要運(yùn)用主干道上的機(jī)動(dòng)車平均速度大小來(lái)描述其擁擠程度[6]，具體定義如下：

（1）暢通：城市主干道上機(jī)動(dòng)車的平均速度不低于30km/h。

（2）輕度擁擠：城市主干道上機(jī)動(dòng)車的平均速度低于30km/h，但高于20km/h。

（3）擁擠：城市主干道上機(jī)動(dòng)車的平均速度低于20km/h，但高于10km/h。

（4）嚴(yán)重?fù)頂D：城市主干道上機(jī)動(dòng)車的平均速度低于10km/h。

公安部關(guān)于交通擁擠的定量描述具有較高的可操作性，可直接用于道路交通狀態(tài)的判別。

由于本文在進(jìn)行路徑規(guī)劃時(shí)只考慮路段是否已經(jīng)陷入擁擠或即將陷入擁擠，故而將上述交通狀態(tài)的量化定義重新定義為：

（1）不擁擠：城市主干道上機(jī)動(dòng)車的平均速度不低于15km/h。

（2）擁擠：城市主干道上機(jī)動(dòng)車的平均速度低于15km/h。

本文所需的速度需從車聯(lián)網(wǎng)系統(tǒng)中直接獲得，且根據(jù)路段距離和速度獲得仿真中所需的時(shí)間。

2 最優(yōu)路徑規(guī)劃的算法設(shè)計(jì)

2.1 道路網(wǎng)絡(luò)的抽象化及其數(shù)學(xué)模型描述

路網(wǎng)通常被抽象為圖論中的“圖”，可構(gòu)建一個(gè)路網(wǎng)模型[7]如下:

其中，V表示節(jié)點(diǎn)集；E表示邊集，且〈vi，vj〉和〈vj，vi〉屬于不同的邊；W表示權(quán)重集，可選擇不同的標(biāo)準(zhǔn)作為權(quán)重，例如時(shí)間、距離等；wij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的權(quán)重。對(duì)于實(shí)際的道路網(wǎng)絡(luò)，一般情況下同一路段兩個(gè)方向的交通信息是不相同的，因此使用有向圖來(lái)表達(dá)實(shí)際路網(wǎng)，單行道中不可行車方向的距離（行駛時(shí)間）可設(shè)置為最大值。

道路權(quán)重也稱道路交通阻抗或路阻，它的確定與計(jì)算是最優(yōu)路徑規(guī)劃算法優(yōu)化目標(biāo)的依據(jù)。路阻一般選擇距離或時(shí)間，由于出行者出行時(shí)大多希望在最短時(shí)間內(nèi)到達(dá)目的地，故本文采用時(shí)間作為路徑規(guī)劃的依據(jù)且在設(shè)置各路段路阻值時(shí)，若某一路段為擁擠路段，則該路段路阻值記為最大值，如1000。

2.2 Floyd算法的思想及過(guò)程

①Floyd算法的思路是：

設(shè)vi，vj是網(wǎng)絡(luò)G（V，E，W ）中點(diǎn)的集合V中的任意兩點(diǎn)。令為vi到vj不經(jīng)過(guò)中間點(diǎn)的最短路路長(zhǎng)，顯然。

②改進(jìn)后的Floyd算法的步驟如下：

第一步：k = 0

第二步：k = k+1

第三步：當(dāng)k=n時(shí)算法結(jié)束

Dn=()n×n,n是vi到vj的最短路路長(zhǎng); Sn=(S)n×n,是vi到vj的最短路的第一條弧的終點(diǎn)。

2.3 實(shí)例分析

① 以山東省青島市黃島區(qū)一實(shí)際路網(wǎng)為例，抽象成路網(wǎng)圖，如附圖所示。圖中所有路段均為雙向路段；圖中各節(jié)點(diǎn)均為十字路口，圖中所標(biāo)距離均為路口與路口之間的路段長(zhǎng)度，如路口1和路口2之間的路段長(zhǎng)度為1190m。

文中要搜索節(jié)點(diǎn)1到節(jié)點(diǎn)12的最短路徑。

② 文中所采用的初始數(shù)據(jù)見(jiàn)表1。

附圖 路網(wǎng)抽象圖

表1 初始數(shù)據(jù)

上述數(shù)據(jù)觀察得知節(jié)點(diǎn)2與節(jié)點(diǎn)3之間、節(jié)點(diǎn)2與節(jié)點(diǎn)6之間、節(jié)點(diǎn)7與節(jié)點(diǎn)8之間以及節(jié)點(diǎn)10與節(jié)點(diǎn)11之間的路段運(yùn)行速度均小于15km/h，由1給出的路段擁擠程度判斷標(biāo)準(zhǔn)得知上述四條路段為擁擠路段。

文中所采用轉(zhuǎn)換后最終數(shù)據(jù)見(jiàn)表2（考慮到程序的運(yùn)行，擁擠路段時(shí)間記為1000s）。

表2 最終數(shù)據(jù)

③ 根據(jù)2.2所述算法，編制出Floyd算法程序代碼，在Codeblocks平臺(tái)上運(yùn)行該程序代碼得到節(jié)點(diǎn)1到節(jié)點(diǎn)12的不含擁擠路段的最優(yōu)路徑為1 →5→6→7→11→12。若不考慮所得路徑是否含有擁擠路段，則得到節(jié)點(diǎn)1到節(jié)點(diǎn)12的最優(yōu)路徑為1→5→6→10→11→12（其中10→11為擁擠路段）。

兩條路徑相比，第二條路徑經(jīng)過(guò)了擁堵路段10→11，對(duì)整個(gè)道路網(wǎng)而言加劇了道路擁堵?tīng)顩r；而第一條路徑雖對(duì)出行者個(gè)人來(lái)說(shuō)并非是出行成本最小的路徑，但從整個(gè)道路網(wǎng)絡(luò)來(lái)說(shuō)，可以使得道路網(wǎng)絡(luò)趨于平衡并將擁擠路段的道路交通壓力分散到臨近非擁擠路段上去，從而提高了道路利用率。

3 結(jié)束語(yǔ)

從決策者角度出發(fā)的最優(yōu)路徑規(guī)劃考慮了整個(gè)道路網(wǎng)的平衡，在考慮擁擠路段的影響后，使用Floyd算法，使得求出的最優(yōu)路徑更加符合實(shí)際情況，且能有效地避免出行者陷入交通擁擠，在一定程度上解決交通擁堵問(wèn)題。在路徑規(guī)劃中還可以將交叉口紅綠燈的延誤、所含交叉口個(gè)數(shù)、彎道長(zhǎng)度等因素考慮進(jìn)去，以使求得的最優(yōu)路徑更加符合實(shí)際情況。