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

葛長飛

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

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

葛長飛

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

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

交通網絡；抗堵塞路徑；算法

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

在以往對交通堵塞的研究工作中，主要有以下幾個方面：一是對最短路徑上和最長繞行關鍵邊的研究[1-2]；二是對不完全信息下實時關鍵邊和關鍵路徑的研究[3-4]；三是對交通網絡抗堵塞能力的研究[5]。但缺乏從抗堵塞能力角度對交通網絡網中任意點對間路徑選擇的研究。為此，筆者提出了一種最優(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的權重。σk={pg(s,t)}為s到t的k條路徑的集合，dg(s,t)為pg(s,t)路徑的長度，假設交通網絡中只發(fā)生一次堵塞，且堵塞的位置和時間未知，居民和車輛應當如何選擇路徑使得損失最小化。

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

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

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

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

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

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

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

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

2.2算法復雜性分析

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

3 實例分析

圖1 鹽城市局部交通網絡抽象

以江蘇省鹽城市實際交通網絡為例，進行最優(yōu)抗堵塞路徑選擇。首先將鹽城市局部地圖抽象成交通網絡圖(見圖1)。假設v1為出發(fā)節(jié)點，v6為目標節(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為目標節(jié)點的3條路徑中，交通網絡中路徑2出現堵塞后存在最短路徑與原最短路徑的最差的替代效果，比其他路徑1和路徑3的堵塞后最短路徑和原最短路徑最差替代效果要好，則路徑2就是最優(yōu)的抗堵塞路徑。

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

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

[3]蘇兵.連接網絡上的占線的可恢復加拿大旅行者問題[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]蘇兵，徐寅峰.交通網絡的抗堵塞能力分析與計算[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