考慮道路擁堵程度的出行路徑規(guī)劃研究

楊曉穎 紀(jì)道元

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

引言

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

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

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

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

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

1 路段交通狀況判斷

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

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

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

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

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

（4）嚴(yán)重擁擠：城市主干道上機動車的平均速度低于10km/h。

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

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

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

（2）擁擠：城市主干道上機動車的平均速度低于15km/h。

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

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

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

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

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

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

2.2 Floyd算法的思想及過程

①Floyd算法的思路是：

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

②改進后的Floyd算法的步驟如下：

第一步：k = 0

第二步：k = k+1

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

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

2.3 實例分析

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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