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

盧志明

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

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

中圖分類號：U491 文獻標識碼：A

0 引言

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

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

1 固定瓶頸識別方法

1.1 基本定義

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

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

1.2 最大流最小割原理

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

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

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

2 實例

2.1 研究對象

本文選取重慶江北區(qū)部分區(qū)域為研究對象，包括盤溪路、余松路、百靈路、龍山路、景輝路、龍園路、天竺路、盤溪四支路、武江東路，如圖1所示。

2.2 道路參數(shù)

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

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

2.3 固定瓶頸識別

將道路網(wǎng)抽象成拓撲圖。因此將江北區(qū)實例區(qū)域道路網(wǎng)抽象為圖2。

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

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

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

3 結語

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

參考文獻：

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

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

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

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

[5]李石.網(wǎng)絡連接可靠性評估研究[D].北京：北京交通大學，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.