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

雩风三日

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

关键词:图论;网络最大流;A*算法;有效路径;通行能力
4 _0 f3 r2 Y- b5 E9 S8 w; b3 o