交通运输系统工程与信息

交通运输系统工程与信息 ›› 2009, Vol. 9 ›› Issue (1): 99-103 .

• 系统工程理论与方法 • 上一篇    下一篇

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

李平生1,2;李斌*2;谢晓莉3;王猛2   

  1. 1东南大学 交通学院, 南京210096；
    2国家智能交通系统技术研究中心, 北京 100088；
    3北京工业大学, 北京 100022
  • 收稿日期:2008-03-17 修回日期:2008-05-06 出版日期:2009-02-25 发布日期:2009-02-25
  • 通讯作者: 李斌
  • 作者简介:李平生（1980-），男，河北威县人，博士生.

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

LI Ping-sheng 1,2; LI Bin 2; XIE Xiao-li3; WANG Meng2   

  1. 1 Transportation College of Southeast University, Nanjing 210096, China;
    2 National Intelligent Transport Systems Center of Engineering and Technology, Beijing 100088, China;
    3 Beijing University of Technology, Beijing 100022, China
  • Received:2008-03-17 Revised:2008-05-06 Online:2009-02-25 Published:2009-02-25
  • Contact: LI Bin

被引次数

25

摘要： 在路网规划中，路网关键断面的确定对于解决路网中的交通瓶颈问题有很大的帮助。路网关键断面问题可以转变为寻找路网最大流最小割的问题。本文首先对现有求解网络最大流的各种算法进行了分析和比较。然后，基于图论中的辅助图理论和求解最大流中的Dijkstra算法，得到了一种求解无向路网中最小割集较为简便的算法，即通过构造辅助路网，利用求辅助路网最短路的方法得到最小割集，即原始路网的最大流。在此基础之上，利用VC++计算机语言程序实现了该算法。最后通过对天津市公路网的分析，进一步对本算法进行了说明。通过比较可知，这种方法是一种确定网络关键断面较为简便的算法，并且会对交通规划与管理提供重要的理论依据和数据支持。

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

Abstract: 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.

Key words: network capacity, key section, auxiliary graph, shortest path algorithm

中图分类号: