基于虚拟顶点最大流的城市路网通行能力算法

Algorithm of urban traffic network capacity based on virtual vertices max-flow

针对城市道路路网通行能力的确定问题,通过引入虚拟起、讫点改造路网。应用图论中最大流最小割定理,对最大流算法进行了改进;提出了一种在容量限制下确定路网通行能力的算法,使得多起点、多讫点的道路路网通行能力的确定得以简化。用算例验证了算法的正确性。

An algorithm is proposed to determine urban traffic network capacity with road sections capacity confined.The urban traffic network is transformed by adding virtual origin and destination,the max-flow min-cut theorem is used and the maximum flow algorithm is improved,the algorithm about urban traffic network capacity is simplified.Experiment shows that the algorithm is right.