迂回限制下城市交通网络最短路径算法优化设计

详细信息    查看全文 | 推荐本文 |

英文篇名：Optimization Design of Shortest Path Algorithm for Urban Traffic Network Under Circuitous Limitation 作者：刘昊 英文作者：LIU Hao;College of Information Engineering,Nanning University; 关键词：迂回限制 ; 城市交通网络 ; 最短路径 ; 优化算法 ; dijkstra算法 ; 二叉树 英文关键词：converse restrictions;;urban transport networks;;the shortest path;;optimization algorithm;;dijkstra algorithm;;binary tree 中文刊名：KJPL 英文刊名：Journal of China Academy of Electronics and Information Technology 机构：南宁学院信息工程学院; 出版日期：2019-04-20 出版单位：中国电子科学研究院学报 年：2019 期：v.14;No.84 基金：2017年度广西高校中青年教师科研基础能力提升项目(2017KY1435) 语种：中文; 页：KJPL201904015 页数：7 CN：04 ISSN：11-5401/TN 分类号：90-96

摘要

针对传统城市交通网络最短路径算法存在耗时长、准确率低、鲁棒性低的问题,设计一种迂回限制下城市交通网络最短路径优化算法,首先分析现实交通网络中交通分布特征规律,采用增量加载方法计算迂回限制下城市交通网络容量;然后依据该容量构建城市交通网络模型,采用优化dijkstra算法从城市交通网络模型中道路起点到道路终点;最后,利用二叉树方法按其方向性进行搜索,直至搜索到最短路径为止,获取最佳城市交通网络最短路径。实验结果表明,该算法在计算100个道路节点的最短路径仅用时0. 37 s,计算准确率高达99%,且具有较高的鲁棒性。该算法为城市交通网络路径规划技术的进一步发展奠定了基础。
        Aiming at the problem of long time consuming,low accuracy and low robustness of the shortest path algorithm in traditional urban traffic network,this paper designs a shortest path optimization algorithm for urban traffic network under circumlocution constraints. Firstly,the characteristics of traffic distribution in real traffic network are analyzed,and the capacity of urban traffic network under circumlocution constraints is calculated by incremental loading method; secondly,urban traffic is constructed according to the capacity. In the network model,the optimal Dijkstra algorithm is used to search from the road starting point to the road ending point in the urban traffic network model. Finally,the binary tree method is used to search according to its direction until the shortest path is found,and the shortest path of the urban traffic network is obtained. The experimental results show that the algorithm only takes 0. 37 seconds to calculate the shortest path of 100 road nodes,and the calculation accuracy is as high as 99%,and it has high robustness. This algorithm lays a foundation for the further development of urban traffic network path planning technology.

引文

[1]孙景昊,关楠,邓庆绪,等.城市交通网络信号控制系统的实时演算模型[J].软件学报,2016,27(3):527-546.
    [2]李畅,李桂娥,朱昱佳.城市交通网络分形维数的不确定性估计、控制与分析[J].遥感学报,2017,21(1):74-83.
    [3]何忠贺,王力,张玲玉,等.城市交通网络正系统模型与稳态信号控制[J].信息与控制,2016,45(4):499-505.
    [4]卫振林,甘杨杰,赵鹏.城市复合交通网络的若干特性研究[J].交通运输系统工程与信息,2015,15(1):106-111.
    [5]刘张,李坚,王超,等.基于复杂城市道路网络的交通拥堵预测模型[J].电子科技大学学报,2016,45(1):1-1.
    [6]孙威,陈焱明,尚晓丽.基于快速收敛牛顿算法的城市最短路径分析[J].哈尔滨商业大学学报(自然科学版),2018,v. 34; No. 151(02):71-75+84.
    [7]陈洁,陆锋.一种基于双端队列的交通网络最短路径Pallottino优化算法[J].中国图象图形学报,2018,11(3):419-424.
    [8]徐达,蔡满春,陈悦,等.基于改进Floyd算法的城市交通网络最短路径规划[J].电子科技,2017,32(7):17-20.
    [9]范炯,朱志宇.基于MapInfo的Dijkstra最短路径算法研究[J].江苏科技大学学报(自然科学版),2017,12(1):25-31.
    [10]范文博,王佳伟,杨成.随机交通网络连通可靠度改进算法[J].交通运输系统工程与信息,2015,15(6):197-204.
    [11]李成兵,魏磊,郝羽成.城市群复合交通网络特性研究[J].系统仿真学报,2016,28(12):2958-2965.
    [12]陆锋,卢冬梅,崔伟宏.交通网络限制搜索区域时间最短路径算法[J].中国图象图形学报,2018,4(10):849-853.
    [13]曾俊伟,张善富,钱勇生,等.基于复杂网络的城市公共交通网络连通可靠性分析[J].铁道运输与经济,2017,39(06):97-101.
    [14]段明义,张文.一种改进的交通网络路径选择算法[J].公路交通科技,2016,33(11):120-125.
    [15]龚勃文,林赐云.一种个性化城市多目标最短路径随机优化算法[J].中国科技论文,2016,11(7):828-834.