基于辅助图理论的路网最大流改进算法  

Improved Arithmetic about the Maximum Flow in Road Network Using Auxiliary Graph Theory

作　　者：李平生[1,2] 李斌 谢晓莉[3] 王猛 

机构地区：[1]东南大学交通学院,南京210096 [2]国家智能交通系统技术研究中心,北京100088 [3]北京工业大学,北京100022

出　　处：《交通运输系统工程与信息》2009年第1期99-103,共5页Journal of Transportation Systems Engineering and Information Technology

摘　　要：在路网规划中,路网关键断面的确定对于解决路网中的交通瓶颈问题有很大的帮助.路网关键断面问题可以转变为寻找路网最大流最小割的问题.本文首先对现有求解网络最大流的各种算法进行了分析和比较.然后,基于图论中的辅助图理论和求解最大流中的Dijkstra算法,得到了一种求解无向路网中最小割集较为简便的算法,即通过构造辅助路网,利用求辅助路网最短路的方法得到最小割集,即原始路网的最大流.在此基础之上,利用VC++计算机语言程序实现了该算法.最后通过对天津市公路网的分析,进一步对本算法进行了说明.通过比较可知,这种方法是一种确定网络关键断面较为简便的算法,并且会对交通规划与管理提供重要的理论依据和数据支持.in road network planning, locating the key sections is very useful to solve the traffic bottleneck. Locating the key sections is equal to finding the maximum flow. To begin with, this paper analyzed and compared kinds of methods solving the network maximum flow problem. Secondly, this paper pointed out a convenient method based on the auxiliary graph theory and Dijkstra method. That is to say, the method could be used to get the minimum cutset and the maximum flow using the shortest path algorithm, and the VC ＋ ＋ program was also used. Finally, based on the road network of Tianjin, an example was given for further explanation. Through comparison, it can be found that it is a convenient method to locate the key sections, and can support the transportation planning and management with theoretical basis and data.

关 键 词：路网容量 关键断面 辅助图 最短路算法 

分 类 号：U491[交通运输工程—交通运输规划与管理]