葛長飛

(鹽城師范學(xué)院商學(xué)院，江蘇 鹽城 224051)

交通網(wǎng)絡(luò)最優(yōu)抗堵塞路徑的選擇模型與計算

葛長飛

(鹽城師范學(xué)院商學(xué)院，江蘇 鹽城 224051)

從交通網(wǎng)絡(luò)堵塞后替代路徑與原最短路徑之間關(guān)系出發(fā)，提出交通網(wǎng)絡(luò)的最優(yōu)抗堵塞路徑選擇模型，設(shè)計了最優(yōu)抗堵塞路徑選擇模型的算法，對算法的復(fù)雜性進行了分析，并以鹽城市實際局部路網(wǎng)為例進行了驗證，得出該區(qū)域的最優(yōu)抗堵塞路徑。

交通網(wǎng)絡(luò)；抗堵塞路徑；算法

隨著社會經(jīng)濟發(fā)展和汽車銷售量不斷增長，居民或者運輸車輛在行駛過程中，經(jīng)常遇到交通道路堵塞的情況，且這種堵塞在短時間是無法恢復(fù)。由于交通網(wǎng)絡(luò)中2點對之間存在多條路徑，且每條路徑上任意路段都可能堵塞，因此如何選擇一條盡可能降低由于堵塞帶來的損失，顯得尤為重要。

在以往對交通堵塞的研究工作中，主要有以下幾個方面：一是對最短路徑上和最長繞行關(guān)鍵邊的研究[1-2]；二是對不完全信息下實時關(guān)鍵邊和關(guān)鍵路徑的研究[3-4]；三是對交通網(wǎng)絡(luò)抗堵塞能力的研究[5]。但缺乏從抗堵塞能力角度對交通網(wǎng)絡(luò)網(wǎng)中任意點對間路徑選擇的研究。為此，筆者提出了一種最優(yōu)抗堵塞路徑選擇模型。

1 最優(yōu)抗堵塞路徑選擇模型

給定G(V,E),V={v1,v2,…,vn}為G(V,E)的節(jié)點集合，E為G(V,E)的集合。若s為出發(fā)節(jié)點，t為最終節(jié)點，則w(eij)為eij的權(quán)重。σk={pg(s,t)}為s到t的k條路徑的集合，dg(s,t)為pg(s,t)路徑的長度，假設(shè)交通網(wǎng)絡(luò)中只發(fā)生一次堵塞，且堵塞的位置和時間未知，居民和車輛應(yīng)當(dāng)如何選擇路徑使得損失最小化。

定義1任意一條I路徑上抗堵塞系數(shù)：

定義2最優(yōu)抗堵塞路徑為：

從定義2可知，計算出每條路徑的抗堵塞能力的最大值后，最優(yōu)抗堵塞路徑就轉(zhuǎn)化為最小最大的問題。即交通網(wǎng)絡(luò)中某條路徑出現(xiàn)堵塞后存在最短路徑與原最短路徑的最差替代效果，與其他路徑的堵塞后最短路徑和原最短路徑最差替代效果進行比較，最小值就是最優(yōu)的抗堵塞路徑。

2 最優(yōu)抗堵塞路徑算法與算法復(fù)雜性分析

2.1最優(yōu)抗堵塞路徑算法

步1 對于路徑pI(s,t)中起止點vs，利用Dijkstra標(biāo)號法計算vs計算出到任一節(jié)點vsu最短路徑長度dIp(s,su)，遍歷u=1,2,…,d(s)，其中,d(s)為節(jié)點vs的度數(shù)。

步2 去掉與vs相關(guān)聯(lián)邊es,su，再次使用利用Dijkstra標(biāo)號法計算vs計算出到節(jié)點vsu的最短路徑長度dIp-es,su(s,su)，即可以計算出所有的dIp-es,su(s,t)，其中,d(s)是vs的度數(shù)。

步5 重復(fù)步1到步4，計算出所有k條路徑的(χ1p,χ2p,…,χkp)。

2.2算法復(fù)雜性分析

對于頂點為n的網(wǎng)絡(luò)圖，k為(s,t)的路徑的條數(shù)，最優(yōu)抗堵塞路徑算法的算法復(fù)雜性如下：步1的計算次數(shù)為O(n2)；步2的計算次數(shù)為O(n2)*d(s)；步3的計算次數(shù)為O(d(s))；步4的計算次數(shù)為O(n4)；步5的計算次數(shù)為k*O(n4) ；步6的計算次數(shù)為O(k)。

3 實例分析

圖1 鹽城市局部交通網(wǎng)絡(luò)抽象

以江蘇省鹽城市實際交通網(wǎng)絡(luò)為例，進行最優(yōu)抗堵塞路徑選擇。首先將鹽城市局部地圖抽象成交通網(wǎng)絡(luò)圖(見圖1)。假設(shè)v1為出發(fā)節(jié)點，v6為目標(biāo)節(jié)點。

利用上述算法進行最優(yōu)抗堵塞路徑的選擇。由圖1可知點對間(v1，v6)最短路徑有3條：

路徑1：v1→v2→v3→v6;路徑2：v1→v2→v5→v6;路徑3：v1→v4→v5→v6。

通過以上分析可知，以v1為出發(fā)節(jié)點、v6為目標(biāo)節(jié)點的3條路徑中，交通網(wǎng)絡(luò)中路徑2出現(xiàn)堵塞后存在最短路徑與原最短路徑的最差的替代效果，比其他路徑1和路徑3的堵塞后最短路徑和原最短路徑最差替代效果要好，則路徑2就是最優(yōu)的抗堵塞路徑。

[1]蘇兵，肖鵬.交通網(wǎng)絡(luò)最優(yōu)安全路徑選擇模型與算法[J].西安交通大學(xué)學(xué)報,2008,42(4):395-398.

[2]劉明.不完全信息下交通網(wǎng)絡(luò)的關(guān)鍵路徑選擇問題[J].系統(tǒng)工程，2006，24(12)：17-20.

[3]蘇兵.連接網(wǎng)絡(luò)上的占線的可恢復(fù)加拿大旅行者問題[J].系統(tǒng)工程理論與實踐，2009，25(2):108-113.

[4]Corley H W,Asakura Y,Kashiwadani M.Road network reliability caused by daily fluctuation of traffic flow[A].Proceedings of the 19thPTRC summer annual Meeting Brighton[C].University of Brighton，2011：73-84.

[5]蘇兵，徐寅峰.交通網(wǎng)絡(luò)的抗堵塞能力分析與計算[J].系統(tǒng)工程，2005，23(6)：16-20.

[編輯] 洪云飛

10.3969/j.issn.1673-1409(N).2012.12.035

TB114.1

A

1673-1409(2012)12-N108-02