基于改进网络最大流的道路通行能力优化研究

doi:10.3969/j.issn.1007-7375.2020.05.013

摘要/Abstract

摘要： 基于图论网络最大流理论基础，建立了一种改进的网络最大流模型。首先，根据最基本的网络最大流模型，采用Ford-Fulkerson算法求解出理论最大通行能力为46人/s；其次，考虑通行的道路选择性，建立最短路模型，利用Dijkstra算法计算各个单源到各个单汇的最短路径，并通过A*算法排除与最短距离相差较大的路径，从而筛选出有效路径；然后，利用最短路模型结果加强原模型中的约束条件，利用单纯形法求解出实际最大通行能力为23人/s；最后，建立以道路扩宽成本最低为目标函数的线性规划模型对道路进行优化改造。研究结果表明，现有道路设计能够满足道路通行需求，若需提高道路通行能力且要求道路改造最小，可以适当扩宽路网中的关键道路。

关键词: 图论, 网络最大流, A*算法, 有效路径, 通行能力

Abstract: A mathematical model of improved network maximum flow is established to study campus road planning in the research background of a domestic university. Firstly, according to the basic network maximum flow model, Ford-Fulkerson algorithm is used to solve the theoretical maximum capacity of 46 person/s. Secondly, considering the road selectivity, the shortest path model is established. Dijkstra algorithm is used to calculate the shortest path from each single source to each single sink, and A* algorithm is used to exclude the path with a large difference from the shortest distance, so as to screen out the effective path. Using the results of the shortest path model to strengthen the constraints in the original model, the simple method is used to solve the actual maximum capacity of 23 person/s. Finally, a linear programming model with the lowest cost of road widening as the objective function is established to optimize the road. The results show that the existing road design can meet the road traffic demand. If the road capacity needs to be improved and the change of the road is minimum, the key roads in the road network can be expanded appropriately.

Key words: graph theory, network maximum flow, A* algorithm, effective path, road capacity

中图分类号:

U491

廖晔, 王顺意. 基于改进网络最大流的道路通行能力优化研究[J]. 工业工程, 2020, 23(5): 96-102.

LIAO Ye, WANG Shunyi. A Research on Road Capacity Optimization Based on Improved Network Maximum Flow[J]. Industrial Engineering Journal, 2020, 23(5): 96-102.

参考文献

[1] 向红艳, 张邻, 杨波. 基于最大流的路网结构优化[J]. 西南交通大学学报, 2009, 44(02): 284-288
XIANG Hongyan, ZHANG Lin, Yang Bo. Optimization of road network structure based on maximum flow theory[J]. Journal of Southwest Jiaotong University, 2009, 44(02): 284-288
[2] 郑龙, 周经伦, 潘正强. 基于广义割集算法的军事运输路径优化[J]. 计算机工程, 2007, 33(11): 4-6+9
ZHENG Long, ZHOU Jinglun, PAN Zhengqiang. Optimization of military transportation path based on generalized cut set algorithm[J]. Computer Engineering, 2007, 33(11): 4-6+9
[3] 刘小莽, 李兰, 代荣霞, 等. 最小费用最大流理论在防洪物资运输中的应用[J]. 人民长江, 2007, 38(05): 141-143
LIU Xiaomang, LI Lan, DAI Rongxia, et al. Application of minimum cost maximum flow theory in flood control material transportation[J]. Yangtze River, 2007, 38(05): 141-143
[4] 海军, 侯远达. 战时动态交通网络最大能力路径问题算法研究[J]. 国防交通工程与技术, 2008(02): 19-22
HAI Jun, HOU Yuanda. Study of maximal capacity-path algorithm of the dynamic traffic networks[J]. Traffic Engineering and Technology for National Defence, 2008(02): 19-22
[5] 卜祥涛. 新增路段对道路交通网络性能的影响研究[D]. 西安: 西安工业大学, 2013.
BU Xiangtao. The influence of edge addition on the properties of transportation network[D]. Xi'an: Xi'an Technological University, 2013.
[6] 郭波, 张凤林, 范英飚, 等. 多源单汇网络资源调度路径优化探讨[J]. 数学的实践与认识, 2005, 35(03): 89-98
GUO Bo, ZHANG Fenglin, FAN Yingbiao, et al. Discussion on resource scheduling path optimization of multi-source and single-sink networks[J]. Mathematics in Practice and Theory, 2005, 35(03): 89-98
[7] 詹雯. 网络增广链的最优路径选择模型仿真分析[J]. 计算机仿真, 2015, 32(12): 259-262
ZHAN Wen. Simulation analysis of optimal path selection model on network augmented chain[J]. Computer Simulation, 2015, 32(12): 259-262
[8] 高明霞, 洪娃艺, 司倩倩. 基于最大流增流关键边的疏散逆向路段优化[J]. 交通运输系统工程与信息, 2016, 16(3): 194-199
GAO Mingxia, HONG Wayi, SI Qianqian. Optimization of contra-flow links in traffic evacuation based on the critical edge for improving maximum flow of a network[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(3): 194-199
[9] 李运, 潘应久, 侯礼兴. 基于最小费用最大流算法的冲突车流分配[J]. 山东交通学院学报, 2015, 23(2): 25-30
LI Yun, PAN Yingjiu, HOU Lixing. Conflict traffic flow distribution based on minimum cost maximum flow algorithms[J]. Journal of Shandong Jiaotong University, 2015, 23(2): 25-30
[10] 栗雪娟. 路网容量与交通流量预测算法研究[D]. 西安: 长安大学, 2007.
LI Xuejuan. Study on the arithmetic of the road networks capacity and traffic volume forecast[D]. xi'an: Chang’an University, 2007.
[11] 李玉兰, 李耀堂. 城市道路网容量的对偶图算法[J]. 云南大学学报(自然科学版), 2006, 28(4): 293-297
LI Yulan, LI Yaotang. Maximum flow control of traffic network based on niche hybrid genetic algorithms[J]. Journal of Yunnan University (Natural Sciences Edition), 2006, 28(4): 293-297
[12] 杨晓萍, 杨国志. 基于网络最大流的城市道路网容量计算[J]. 上海公路, 2005(2): 53-56+6
YANG Xiaoping, YANG Guozhi. Calculating capacity of urban road network on the basis of maximum flow of network[J]. Shanghai Highways, 2005(2): 53-56+6
[13] 孙同江, 黄圣国. 运输网络最大流的Petri网图仿真算法[J]. 交通运输工程学报, 2002, 2(3): 76-80
SUN Tongjiang, HUANG Shengguo. Petri net simulation algorithm of maximum flow in transportation network[J]. Journal of Traffic and Transportation Engineering, 2002, 2(3): 76-80
[14] 苏镇洪, 赵文秀, 龙科军. 道路网络容量的多端最大流算法[J]. 交通科学与工程, 2012, 28(1): 84-88
SU Zhenhong, ZHAO Wenxiu, LONG Kejun. Analyzing road network capacity based on multi-terminal network maximum flow algorithm[J]. Journal of Transport Science and Engineering, 2012, 28(1): 84-88
[15] 何家莉, 宣士斌. 基于小生境混合遗传算法的交通网络最大流控制[J]. 交通信息安全, 2008, 26(2): 41-44
HE Jiali, XUAN Shibin. Maximum flow control of traffic network based on niche hybrid genetic algorithms[J]. Journal of Transport Information and Safety, 2008, 26(2): 41-44
[16] 胡适军, 钱琳, 朱曼, 等. 基于网络流割集理论的水网航道交通容量计算[J]. 武汉理工大学学报, 2014, 36(4): 86-91
HU Shijun, QIAN Lin, ZHU Man, et al. Calculating traffic capacity of water-network channel based on cut set method[J]. Journal of Wuhan University of Technology, 2014, 36(4): 86-91
[17] 李冬梅, 李文权. 道路通行能力的计算方法[J]. 河南大学学报(自然科学版), 2002, 32(2): 24-27
LI Dongmei, LI Wenquan. The method of calculating the road capacity[J]. Journal of Henan University (Natural Science), 2002, 32(2): 24-27
[18] 罗文, 袁林旺, 易琳, 等. 多条件约束最大流分析的几何代数方法[J]. 武汉大学学报(信息科学版), 2013, 38(7): 862-868
LUO Wen, YUAN Linwang, YI Lin, et al. Geometric algebraic method for maximum flow analysis with multiple constraints[J]. Geomatics and Information Science of Wuhan University, 2013, 38(7): 862-868