時(shí)間依賴網(wǎng)絡(luò)中有效交通路由的仿真平臺(tái)

摘要：在理想的行駛條件下，經(jīng)典的Dijkstra最短路徑算法雖然可以計(jì)算出交通網(wǎng)絡(luò)中兩個(gè)任意節(jié)點(diǎn)的車輛行駛的最短路徑，但這樣做是沒有實(shí)際意義的，因?yàn)樵诂F(xiàn)實(shí)生活中交通流量會(huì)對(duì)最短路徑的求解產(chǎn)生影響。本文介紹的時(shí)間依賴有效交通路由仿真平臺(tái)，將每個(gè)節(jié)點(diǎn)的車流量信息轉(zhuǎn)換成在該節(jié)點(diǎn)需要等待的時(shí)間，等待時(shí)間又可以看成某車輛以車速v走過的一段距離s。在原來Dijkstra最短路徑算法的基礎(chǔ)上，通過這樣的等價(jià)變換，即可將現(xiàn)實(shí)生活中的交通流量考慮進(jìn)去，從而求出任意兩個(gè)節(jié)點(diǎn)的最優(yōu)有效路徑。

關(guān)鍵詞：時(shí)間依賴網(wǎng)絡(luò)；有效路由；仿真平臺(tái)

中圖分類號(hào)：TP3 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 22-0000-03

在以往有關(guān)控制堵塞的交通流量研究中，都有關(guān)于道路網(wǎng)結(jié)構(gòu)相似的假設(shè)[1]，特別是，一些針對(duì)真實(shí)路網(wǎng)流量控制的研究，例如Guimera等人利用平行交通系統(tǒng)中的搜尋功能和交通動(dòng)力學(xué)，建立了可以同時(shí)應(yīng)付交通變化的模型[3]，使用這個(gè)模型時(shí)，使用整個(gè)路網(wǎng)中的交通信息，根據(jù)比較簡單的本地搜索算法，找到路網(wǎng)中的可使用路徑。Zhao等人根據(jù)全局和動(dòng)力學(xué)搜尋算法，也借助最短路由算法，可以對(duì)交通容量進(jìn)行預(yù)估[4]。

在理想的行駛條件下，參考經(jīng)典的Dijkstra最短路徑算法即可以計(jì)算出交通網(wǎng)絡(luò)中兩個(gè)任意節(jié)點(diǎn)的車輛行駛的最短路徑，找出這樣的最短路徑就是最優(yōu)路徑了。但這樣做是沒有實(shí)際意義的，因?yàn)樵诂F(xiàn)實(shí)生活中交通流量會(huì)對(duì)最短路徑的求解產(chǎn)生影響[5]。本文介紹的方法，是將每個(gè)節(jié)點(diǎn)的車流量信息轉(zhuǎn)換成在該節(jié)點(diǎn)需要等待的時(shí)間，等待時(shí)間又可以看成某車輛以車速v走過的一段距離s。在原來參考Dijkstra最短路徑算法的基礎(chǔ)上，通過這樣的等價(jià)變換，即可將現(xiàn)實(shí)生活中的交通流量考慮進(jìn)去，從而求出任意兩個(gè)節(jié)點(diǎn)的最優(yōu)路徑。

由于現(xiàn)實(shí)生活中的交通流量是隨機(jī)不定的，根據(jù)每一車輛的出行需求產(chǎn)生。為了建立一個(gè)能夠盡可能地模仿現(xiàn)實(shí)生活中的交通流量的仿真平臺(tái)，本文也介紹了一個(gè)簡單的背景流量數(shù)據(jù)仿真模型，用來產(chǎn)生過程和獲取所有路口具體的相關(guān)流量信息。每個(gè)節(jié)點(diǎn)的車流量都由隨機(jī)函數(shù)產(chǎn)生，并存儲(chǔ)在相關(guān)文件里，同時(shí)也隨機(jī)產(chǎn)生每個(gè)節(jié)點(diǎn)產(chǎn)生的車流量中每一輛車的起點(diǎn)和終點(diǎn)，并按照最短路徑行駛。在某一規(guī)定的時(shí)間間隔內(nèi)定期更新每一個(gè)節(jié)點(diǎn)的流量信息，同時(shí)修改相關(guān)的存儲(chǔ)文件。這樣，一個(gè)簡單的流量背景仿真平臺(tái)就產(chǎn)生了。在這個(gè)平臺(tái)的基礎(chǔ)上便可按上述算法求出某一起點(diǎn)到終點(diǎn)的最優(yōu)路徑。

為了盡可能地模仿現(xiàn)實(shí)生活中的交通流量的產(chǎn)生過程和獲取所有路口具體的相關(guān)流量信息，每個(gè)結(jié)點(diǎn)的車流量都由隨機(jī)函數(shù)產(chǎn)生，并存儲(chǔ)在相關(guān)文件里，同時(shí)也隨機(jī)產(chǎn)生每個(gè)結(jié)點(diǎn)產(chǎn)生的車流量中每一輛車的起點(diǎn)和終點(diǎn)，并按照最短路徑行駛。在某一規(guī)定的時(shí)間間隔內(nèi)定期更新每一個(gè)結(jié)點(diǎn)的流量信息，同時(shí)修改相關(guān)的存儲(chǔ)文件。這樣，一個(gè)簡單的流量背景仿真平臺(tái)就產(chǎn)生了。在這個(gè)平臺(tái)的基礎(chǔ)上便可按上述算法求出某一起點(diǎn)到終點(diǎn)的最優(yōu)路徑。

1 地圖信息的輸入

1.1 選取節(jié)點(diǎn)

將需要進(jìn)行路由最優(yōu)規(guī)劃的道路地圖導(dǎo)入AUTOCAD中，利用AUTOCAD中的標(biāo)記工具在地圖上的路口處隨機(jī)標(biāo)記出多個(gè)節(jié)點(diǎn)。

1.2 節(jié)點(diǎn)間距離的測(cè)算

利用多段線繪畫出所選節(jié)點(diǎn)間所有可以直接到達(dá)的路徑，并用AUTOCAD中的list函數(shù)進(jìn)行路徑長度信息的查詢。這樣就得到了節(jié)點(diǎn)間路徑長度的基本信息。將基本信息進(jìn)行保存，存入到記事本中。

2 背景交通流量的產(chǎn)生

2.1 隨機(jī)流量產(chǎn)生背景

當(dāng)然，導(dǎo)入到記事本中的信息只是一種理想狀態(tài)下的道路信息狀況，它只有單純的兩點(diǎn)之間的長度，如果在此狀態(tài)下，當(dāng)出行者需要出行時(shí)，只需選擇一條路程長度最短的道路即可，而選擇的最短路徑，也就是這中狀態(tài)下的最優(yōu)路徑。而實(shí)際道路中的交通狀況，要遠(yuǎn)比這個(gè)理想狀態(tài)復(fù)雜的多。在實(shí)際道路中，任意兩個(gè)節(jié)點(diǎn)間都會(huì)隨機(jī)的產(chǎn)生不確定數(shù)量的車流量，而其原本最短距離的路徑，也不一定是實(shí)際道路中的最優(yōu)的有效路徑了[6]。而路由有效路徑規(guī)劃程序就是為了在實(shí)際復(fù)雜道路狀況中選擇一條最優(yōu)的有效路徑，為出行者選擇一條效率最大化，最節(jié)省時(shí)間的道路。

2.2 隨機(jī)流量產(chǎn)生方法

首先需要出行者在實(shí)際地圖中選出作為起始點(diǎn)和終點(diǎn)的兩個(gè)節(jié)點(diǎn)。然后將記事本中理想狀態(tài)下的道路路程信息狀況導(dǎo)入有效路徑規(guī)劃程序中，利用srand（ ） 函數(shù)，設(shè)置任意數(shù)的種子，也稱為初始化隨機(jī)數(shù)產(chǎn)生器，將strand函數(shù)產(chǎn)生的隨機(jī)數(shù)據(jù)，加入到有效路徑規(guī)劃程序相應(yīng)節(jié)點(diǎn)間的路程信息中，作為在某一時(shí)刻隨機(jī)產(chǎn)生的兩節(jié)點(diǎn)之間的車流量。而每一個(gè)節(jié)點(diǎn)本身也利用srand（ ） 函數(shù)產(chǎn)生隨機(jī)數(shù)，作為該點(diǎn)在同一時(shí)刻產(chǎn)生的車流量。將k設(shè)為srand（）函數(shù)產(chǎn)生隨機(jī)數(shù)的一個(gè)上線，把在n個(gè)節(jié)點(diǎn)處及m個(gè)節(jié)點(diǎn)通路處產(chǎn)生的上限為k的隨機(jī)數(shù)加入到有效路徑規(guī)劃程序中。最終，這樣的方法就完成了類似于實(shí)際道路的仿真，在理想模型道路的基礎(chǔ)上產(chǎn)生隨機(jī)的車流量。

2.3 隨機(jī)流量增加的時(shí)間

對(duì)于每個(gè)路口來說，不同的時(shí)刻產(chǎn)生隨機(jī)流量的多少應(yīng)該有所不同，在早高峰以及晚高峰時(shí)期，車輛在路口隨機(jī)產(chǎn)生的密集程度應(yīng)當(dāng)相高一些，而在其他時(shí)刻應(yīng)當(dāng)相對(duì)低一些。其一天當(dāng)中對(duì)于某一路口在不同時(shí)段隨機(jī)產(chǎn)生的隨機(jī)流量密度，如圖1所示：

而對(duì)于我們所采納的隨機(jī)流量的數(shù)據(jù)則是某個(gè)路口車流量的平均值。根據(jù)我們?cè)诼房诘膶?shí)際測(cè)量，每個(gè)路口在不同時(shí)段每分鐘的車流量統(tǒng)計(jì)如下表1：

2.4 道路擁堵情況的統(tǒng)計(jì)

3 時(shí)間依賴下的有效路徑的計(jì)算

3.1 時(shí)間依賴下的有效路徑的引入

如圖2所示，靜態(tài)的路徑網(wǎng)絡(luò)加入時(shí)間之后，就形成了一個(gè)具有時(shí)間依賴性的路徑網(wǎng)絡(luò)的一個(gè)例子[2]。

從節(jié)點(diǎn)1 在4 時(shí)刻出發(fā)到節(jié)點(diǎn)4 的最優(yōu)路徑，按照傳統(tǒng)Dijkstra 方法或者標(biāo)設(shè)置算法是（1， 3， 4） ，走行時(shí)間是5； 但是加入時(shí)間元素后（1， 2， 3， 4） ，具有最小走行時(shí)間是4。所以當(dāng)時(shí)間元素加入靜態(tài)的路徑網(wǎng)絡(luò)之后，傳統(tǒng)的Dijkstra算法得出的最短路徑，不一定就是時(shí)間依賴網(wǎng)絡(luò)下的最短路徑了，因此，我們需要一種新的算法來得出一條有效路徑，從而解決在時(shí)間影響下網(wǎng)絡(luò)路徑問題[8]。

3.2 時(shí)間依賴下的有效路徑的算法原理

3.3 時(shí)間依賴下的有效路徑的具體實(shí)現(xiàn)

由于在前面已經(jīng)形成了一個(gè)類似于實(shí)際道路的仿真，所以我們只需將仿真的道路與時(shí)間依賴下的有效路徑的的算法原理相結(jié)合，便能選擇出一條最優(yōu)的有效路徑，從而給出行者帶來最大的利益。如上面所說，由表1的統(tǒng)計(jì)值和公式1的計(jì)算結(jié)果，我們可以得出，隨機(jī)函數(shù)在路口每產(chǎn)生一輛車，我們就把對(duì)應(yīng)的行駛路程時(shí)間增加三秒，而終點(diǎn)產(chǎn)生隨機(jī)車輛增加的相應(yīng)時(shí)間也將包含在內(nèi)。同時(shí)，假設(shè)出行者車輛以10m/s的速度在道路上運(yùn)行，通過算法將產(chǎn)生的有效路徑長度與行駛速度相除，便得出選擇有效路徑情況下出行者需要行駛的時(shí)間。由算法得出的有效路徑是類似仿真實(shí)際道路的最優(yōu)化、最大利益的路徑，而得出的時(shí)間則是在有效路徑情況下從起點(diǎn)到終點(diǎn)所需的最小時(shí)間。

3.4 時(shí)間依賴下的有效路徑的記錄

根據(jù)上述所說的有效路徑的算法，得出了最優(yōu)的有效路徑以及在最有效徑情況下所需的最短時(shí)間，但是并沒有明確的將出行者應(yīng)該按照何種路徑行駛顯示出來。所以我們就需要一個(gè)函數(shù)將利用有效路徑算法得出的路徑中的每個(gè)節(jié)點(diǎn)信息記錄下來，在最后直觀的提供給出行者，在結(jié)果中顯示出所走過的節(jié)點(diǎn)。

4 時(shí)間依賴網(wǎng)絡(luò)下的有效路徑與最短路徑優(yōu)越性的比較

最后我們應(yīng)該將有效路徑得出的結(jié)果，與理想狀態(tài)下最短路徑以及仿真狀態(tài)下的最短路徑進(jìn)行比較，從而驗(yàn)證路由有效路徑規(guī)劃下程序的正確性，以及有效路徑規(guī)劃程序相對(duì)于簡單最短路徑優(yōu)越性。這樣便需要兩個(gè)函數(shù)來記錄理想狀態(tài)下最短路徑的相關(guān)信息。其實(shí)一個(gè)函數(shù)負(fù)責(zé)選擇出從起點(diǎn)到終點(diǎn)的最短路徑，另一個(gè)函數(shù)負(fù)責(zé)記錄選出的最短路徑的節(jié)點(diǎn)信息，并最終直觀的顯示出來。選擇從起點(diǎn)到終點(diǎn)最短路徑的算法與最優(yōu)算法大致相同，只不過最優(yōu)算法中的c[][]增加了strand函數(shù)產(chǎn)生的隨機(jī)數(shù)，而該算法將c[][]替換成d[][]，d[][]記錄的只是單純的連接點(diǎn)之間的道路信息。而仿真狀態(tài)下的最短路徑的計(jì)算方法與理想狀態(tài)下的計(jì)算方法基本相同，因?yàn)槎呤褂玫氖峭粭l路徑，只不過需將隨機(jī)函數(shù)產(chǎn)生的隨機(jī)流量加入到所選的路徑中。這樣就分別得到了三者從起點(diǎn)到終點(diǎn)所需的具體時(shí)間，將三者進(jìn)行比較，體會(huì)有效路徑的優(yōu)越性。

5 仿真實(shí)驗(yàn)及結(jié)果

5.1 舉例地圖

我們選取奧利匹克中心附近某一地區(qū)的地圖作為實(shí)例，將其導(dǎo)入AUTOCAD中，其效果截圖如下圖3：

5.2 節(jié)點(diǎn)的選擇及信息記錄

我們?cè)诘貓D中的路口處隨機(jī)選取了十個(gè)節(jié)點(diǎn)，利用多段線繪畫出所選節(jié)點(diǎn)間所有可以直接到達(dá)的路徑，將結(jié)點(diǎn)以及路徑的信息轉(zhuǎn)化為以及道路信息的二維表格。轉(zhuǎn)化的結(jié)果事例如下圖所示：

事例地圖的道路信息二維表格，如下表2：

地圖道路信息二維表格的建立，使得道路信息的狀況更加的清晰化，簡潔化和明了化。根據(jù)地圖道路信息的二維表格，將其內(nèi)容轉(zhuǎn)換到一個(gè)名為input的記事本中，以便后面路由最優(yōu)規(guī)劃的使用。

當(dāng)然，導(dǎo)入到input記事本中的信息只是一種理想狀態(tài)下的道路信息狀況，它只有單純的兩點(diǎn)之間的長度，如果在此狀態(tài)下，當(dāng)出行者需要出行時(shí)，只需選擇一條路程長度最短的道路即可，而選擇的最短路徑，也就是這種狀態(tài)下的有效路徑。而實(shí)際道路中的交通狀況，要遠(yuǎn)比這個(gè)理想狀態(tài)復(fù)雜的多。在實(shí)際道路中，任意兩個(gè)節(jié)點(diǎn)間都會(huì)隨機(jī)的產(chǎn)生不確定數(shù)量的車流量，而其原本的最短路徑，也不一定是實(shí)際道路中的最優(yōu)的有效路徑了。而路由有效路徑規(guī)劃程序就是為了在實(shí)際復(fù)雜道路狀況中選擇一條最優(yōu)的有效路徑，為出行者選擇一條效率最大化，最節(jié)省時(shí)間的道路。

5.3 節(jié)點(diǎn)信息記錄

我們?nèi)我膺x出六組起始和終結(jié)節(jié)點(diǎn)，計(jì)算通過它們之間使用各種路經(jīng)所需花費(fèi)的時(shí)間。其中包括通過有效路徑、無背景交通傳統(tǒng)最短路徑，和有交通背景流量的最短路徑，在不同時(shí)間點(diǎn)所需要的時(shí)間。

很明顯，傳統(tǒng)的Dijkstra最短路徑算法無法反映具有真實(shí)交通流量背景的路由，而基于時(shí)間依賴有效交通路由所耗費(fèi)的時(shí)間，總是少于按照傳統(tǒng)最短路徑算法計(jì)算出來的時(shí)間。尤其在一些交通流量大的時(shí)段，有效路由計(jì)算出來的路由結(jié)果，所花費(fèi)的時(shí)間明顯少于傳統(tǒng)最短路徑的路由。

另外，這個(gè)仿真平臺(tái)也可以計(jì)算任何節(jié)點(diǎn)中在不同時(shí)刻節(jié)點(diǎn)的車輛。考慮到隨機(jī)函數(shù)在某時(shí)刻在節(jié)點(diǎn)產(chǎn)生的隨機(jī)流量以及節(jié)點(diǎn)在某時(shí)刻的通過量，我們對(duì)于其中五個(gè)節(jié)點(diǎn)在5：10—5：16的流量統(tǒng)計(jì)狀況，繪制流量函數(shù)如下圖7：

根據(jù)流量統(tǒng)計(jì)圖，我們便可判斷出哪個(gè)節(jié)點(diǎn)出于擁堵狀況，哪個(gè)節(jié)點(diǎn)出于暢通狀況。

6 結(jié)束語

由于傳統(tǒng)Dijkstra最短路徑無法為時(shí)間依賴的交通網(wǎng)計(jì)算最優(yōu)的有效路由，而時(shí)間依賴的交通網(wǎng)模型與傳統(tǒng)的模型相比，具有更普遍的意義，而建立一個(gè)能夠?qū)r(shí)間依賴交通網(wǎng)絡(luò)的性能進(jìn)行監(jiān)測(cè)的仿真平臺(tái)具有很高的必要性。我們建立的這種基于時(shí)間依賴網(wǎng)絡(luò)模型的智能交通仿真平臺(tái)，能夠反映復(fù)雜的交通網(wǎng)絡(luò)中的普遍情況，仿真結(jié)果可以與傳統(tǒng)網(wǎng)絡(luò)的最短路徑算法進(jìn)行比較，得到了符合實(shí)際交通網(wǎng)情況的結(jié)果，有比較高的實(shí)用性。

參考文獻(xiàn)：

[1]Gao Yan， Tao Zhou， Bo Hu， Zhong-Qian Fu， and Bing-hong Wang. Efficient routing on complex networks，Physics Review Letters. 94， 218701（2005），2005.

[2]譚國真，高文.時(shí)間依賴的網(wǎng)絡(luò)中最小時(shí)間路徑算法[J].計(jì)算機(jī)學(xué)報(bào)，2002，25（2）：165 – 171.

[3]R. Guimeia， A. Diaz-Guilera， F. Vega-Redondo， A. Cabrales， and A. Arenas， Physics Review Letters.89， 248701，2002.

[4]L. Zhao， Y.-C. Lai， K. Park， and N. Ye. Physics Review. E71， 026125 2005.

[5]張勇.隨機(jī)時(shí)間依賴網(wǎng)絡(luò)中的自適應(yīng)K期望最短路徑.大連理工大學(xué)，碩士學(xué)位論文，2005.

[6]譚國真，柳亞玲，高文.隨機(jī)時(shí)間依賴網(wǎng)絡(luò)中的K期望最短路徑.計(jì)算機(jī)學(xué)報(bào)，2003，26（3）：323-331.

[7]Yang By， Miller_Hooks E D. Adaptive routing considering delays due to signal operations. Transportation Research Part B： Methodogical. N 5， 2004， v38： 385-400

[8]Ahuja R K， Orlin J B， Pallottino S. Dynamic shortest paths minimizing travel times and costs. Networks， 2003， 41（4）： 197-205