基于路径和模拟退火的交通网络优化算法研究

Path-based and SA-based Algorithm for Transportation Network Design Problem

针对以交通规划网络方案作为上层规划,而在给定路网结构下的交通平衡分配作为下层规划的离散交通网络设计双层规划模型,设计了基于模拟退火算法和路径搜索算法的SA-GP求解算法。相对传统基于路段搜索的平衡配流算法,采用路径的搜索算法抓住了Wardrop平衡的本质特征,采用逐步增加路径的方式,取得了较好的运算效率。最后使用算例对算法和模型进行了计算分析,计算的结果表明,模型和算法都是有效的,上下层算法均具有良好的收敛速度和求解效率,能够很好地解决大规模的路网规划设计问题。

Based on the analysis of the transportation network design problem,the discrete transportation network design problem was discussed.The bi-level programming model was used to describe the problem,and the upper model considered the point of view of the transportation planner,in order to design the optimal network structure and achieve system optimal based on the restriction of budget,the lower model considered the user of the network and in order to attain the user optimal.The simulated annealing algorithm（SA） was used to solve the upper model and the gradient projection algorithm（GP） was used based on the path search to solve the lower model.The simulated annealing algorithm designed obtains satisfying result and has strongly robustness,which can solve large scale traffic network design problem.GP algorithm meets the essential characters of Wardrop equilibrium and gains more efficient by steady adding path.Application denoted the optimization method was rational,the result can improve the transportation status evidently,and the convergence speed of the algorithm is extraordinary rapid,so it provided scientific guidance for the decision-making of the transportation network planning.