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

A Research on Road Capacity Optimization Based on Improved Network Maximum Flow

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

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.