基于最大流最小割原理的交通網(wǎng)絡(luò)瓶頸識別方法研究

盧志明

摘 要：交通擁擠已經(jīng)成為城市發(fā)展的障礙，交通擁擠主要由交通瓶頸引發(fā)的。因此，通過對交通網(wǎng)絡(luò)瓶頸識別方法研究，找出交通網(wǎng)絡(luò)瓶頸所在的位置，能有助于解決交通擁擠問題。本文以重慶市江北區(qū)部分路網(wǎng)交通數(shù)據(jù)為基礎(chǔ)，基于最大流最小割定理對固定瓶頸進(jìn)行識別。

關(guān)鍵詞：交通擁擠;交通網(wǎng)絡(luò)瓶頸;最大流最小截斷定理

中圖分類號：U491 文獻(xiàn)標(biāo)識碼：A

0 引言

隨著機(jī)動車越來越多，交通需求越來越大，受城市空間的限制，交通供給不能無限增長。當(dāng)路網(wǎng)無法滿足交通需求時，交通擁擠現(xiàn)象就會發(fā)生，阻礙城市的持續(xù)發(fā)展[1]。

據(jù)美國公路協(xié)會調(diào)查顯示，導(dǎo)致交通擁擠的主要原因是交通瓶頸[2]。對城市交通網(wǎng)絡(luò)瓶頸識別方法研究，找出路網(wǎng)的問題所在，通過交通管理、交通控制、交通組織等措施疏導(dǎo)交通流，解決交通擁擠問題[3-6]。

1 固定瓶頸識別方法

1.1 基本定義

起點(diǎn)在V1，終點(diǎn)在V2中的全體有向邊的集合K=（V1，V2）稱為割集。定義流fst滿足以下條件，則fst為網(wǎng)絡(luò)G中一個流。

流量最大的流為最大流，記fmax。

1.2 最大流最小割原理

fmax等于Kmin，即為最大流最小割原理，存在fmax的充要條件是網(wǎng)絡(luò)不存在增流鏈。通過標(biāo)記算法來找尋增流鏈，通過Ford-Fulkerson算法對網(wǎng)絡(luò)流量進(jìn)行調(diào)整。

1.3 交通網(wǎng)絡(luò)瓶頸識別

最小割都是流量等于容量的邊集，在道路網(wǎng)中就是交通量達(dá)到通行能力的路段，即瓶頸路段。因此，交通網(wǎng)絡(luò)瓶頸識別就是找到路網(wǎng)上最小割集。

2 實(shí)例

2.1 研究對象

本文選取重慶江北區(qū)部分區(qū)域?yàn)檠芯繉ο?，包括盤溪路、余松路、百靈路、龍山路、景輝路、龍園路、天竺路、盤溪四支路、武江東路，如圖1所示。

2.2 道路參數(shù)

3.5 m車道的理想通行能力可以達(dá)到1 900 pcu/h～2 000 pcu/h，由于交叉口、車道數(shù)、交通管理等因素影響，道路通行能力需降低。

實(shí)例區(qū)域道路通行能力如表1所示。

2.3 固定瓶頸識別

將道路網(wǎng)抽象成拓?fù)鋱D。因此將江北區(qū)實(shí)例區(qū)域道路網(wǎng)抽象為圖2。

將道路通行能力數(shù)據(jù)加載拓?fù)鋱D中，得到實(shí)例區(qū)域路網(wǎng)通行能力圖，如圖3所示。

將道路通行能力數(shù)據(jù)、實(shí)際交通量加載進(jìn)路網(wǎng)中，通過Ford-Fulkerson算法進(jìn)行流量調(diào)整。實(shí)例區(qū)域固定瓶頸識別結(jié)果如圖4所示。

黃色虛線通過的城市路段通行能力達(dá)到飽和。因此此三條路段為固定瓶頸路段，余松路（龍山路至龍園路）、天竺路（龍山路至龍園路）、盤溪路（龍園路至盤溪四支路）。

3 結(jié)語

基于最大流最小割集定理，研究了交通網(wǎng)絡(luò)瓶頸識別方法，并將此方法應(yīng)用于重慶市江北區(qū)部分區(qū)域瓶頸識別。

參考文獻(xiàn)：

[1]陸華普.交通規(guī)劃理論與方法[M].北京：清華大學(xué)出版社，2007.

[2]American Highway Users Alliance.Unclogging America’s Arteries： Prescriptions for Healthier Highways，www.highways.org，1999，11（12）.

[3]宋杰，李英杰.城市基礎(chǔ)設(shè)施網(wǎng)絡(luò)災(zāi)后連通性和通行能力的快速隨機(jī)評[C].生命線地震《多危險環(huán)境中的工程》，2009（357）：110.

[4]徐亮，高自友.基于出行時間可靠性的城市交通網(wǎng)絡(luò)設(shè)計[J].系統(tǒng)仿真雜志，2009（20）：494-498.

[5]李石.網(wǎng)絡(luò)連接可靠性評估研究[D].北京：北京交通大學(xué)，2009.

[6]Edmonds，Jack，and Karp，Richard M.Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.Journal of the ACM，1972，l（19）：248-264.