基于快速收敛牛顿算法的城市最短路径分析  

Study on shortest path analysis of urban road based on fast convergence newton algorithm

作　　者：孙威[1] 陈焱明 尚晓丽 SUN Wei1,CHEN Yan-ming1,SHANG Xiao-li2(1. School of Information Engineering, Suihua University, Suihua 152061, China;2. School of Education, Suihua University, Suihua 152061, China)

机构地区：[1]绥化学院信息工程学院,黑龙江绥化152061 [2]绥化学院教育学院,黑龙江绥化152061

出　　处：《哈尔滨商业大学学报（自然科学版）》2018年第2期195-199,208,共6页Journal of Harbin University of Commerce：Natural Sciences Edition

基　　金：黑龙江省大学生创新训练项目(201610236015);绥化学院科学技术研究项目(K1501002)

摘　　要：以城市道路交通网络为研究对象,采用快速收敛牛顿(RCN)算法获得城市道路网络最短路径,按照更快速度及均衡接近原则,得到迭代方向和优化步长.以三种不同类型的道路交通网络为案例,利用GP(梯度投影)算法和RCN算法的收敛速度来验证.结果表明,RCN算法在Nguyen网络下的运行时间为10 s,GP算法的运行时间为90 s;RCN算法在成都市网络下的运行时间为10 s,GP算法的运行时间为16 s.RCN算法精度较高,收敛速度更快.The iterative direction and step length optimization were got with urban road traffic network as the research object, using the fast convergence of Newton （ RCN） the shortest path algorithm for urban road network, in accordance with the principle of faster speed and equilibrium close. Three different types of road traffic network were taken as the case, the convergence speed of GP （gradient projection） algorithm and RCN algorithm was used to verify the case. The results showed that the running time of RCN algorithm was 10 s and the operation time of GP algorithm was 90 s. The operation time of RCN algorithm in Chengdu network was 10 s,and the operation time of GP algorithm was 16 s. RCN algorithm had higher accuracy and faster convergence.

关 键 词：路径 优化步长 RCN算法 收敛速度 流量 

分 类 号：O224[理学—运筹学与控制论]