葛長(zhǎng)飛

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

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

葛長(zhǎng)飛

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)例分析

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

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

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

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

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

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

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

[3]蘇兵.連接網(wǎng)絡(luò)上的占線(xiàn)的可恢復(fù)加拿大旅行者問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐，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ì)算[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