基于轨迹大数据的动态最优路径规划

计算机与现代化 ›› 2021, Vol. 0 ›› Issue (11): 82-88.

基于轨迹大数据的动态最优路径规划

（西北师范大学数学与统计学院，甘肃兰州730070）

出版日期:2021-12-13 发布日期:2021-12-13
作者简介:张小芳(1995—),女,甘肃陇南人,硕士研究生,研究方向：统计学习及大数据分析，E-mail: 1774547602@qq.com；通信作者：冯慧芳(1971—),女,甘肃古浪人，教授，硕士生导师，博士,研究方向:车载自组织网络,统计学习及大数据分析，E-mail： hffeng@nwnu.edu.cn。
基金资助:
国家自然科学基金资助项目（71761031）

Dynamic Optimal Path Planning Based on Trajectory Big Data

(College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China)

Online:2021-12-13 Published:2021-12-13

摘要/Abstract

摘要： 以轨迹大数据为基础，结合城市交通状态与用户个性化需求，提出一种基于改进Viterbi算法的动态最优路径规划算法。首先融合交通状态和真实路网拓扑结构，构建基于有向多重加权复杂网络的交通网络模型。采用基于层次分析法和熵权法相结合的综合赋权法对交通网络模型的多权重属性进行权重分配，得到新的有向加权复杂网络模型。进一步采用改进的Viterbi算法求解最优路径。最后，以兰州市为例，对最优路径规划进行分析，并将该算法与静态规划方法进行比较，验证城市最优路径规划算法的有效性与实时性。实验结果表明，结合城市交通状态与用户偏向的路径规划更加科学合理，能够为兰州市驾车出行、交通管理部门决策提供决策支持和参考。

关键词: 动态路径规划, 综合赋权法, Viterbi算法, GPS轨迹大数据, 有向多重加权复杂网络

Abstract: Based on trajectory big data, combined with urban traffic status and user personalized needs, a dynamic optimal path planning algorithm is proposed based on improved Viterbi algorithm. First, a traffic network model based on directed complex network with multi-weights is constructed by combining the traffic state with the real road network topology. The multi-weight attributes of the transportation network model are assigned by using the comprehensive weighting method based on the coalition of the analytic hierarchy process and the entropy weight method. Then, a new directed weighted complex network model is obtained. Further, the optimal path is solved by the improved Viterbi algorithm. Finally, taking Lanzhou as an example to analyze the optimal path planning, the effectiveness of the urban optimal path planning algorithm is verified by comparing the proposed algorithm with the static planning method. The experimental results show that path planning that combines urban traffic conditions with user preferences is more scientific and reasonable, and can provide decision-making support and reference for drivers and traffic management departments.

Key words: dynamic path planning, comprehensive weighting method, Viterbi algorithm, GPS trajectory big data, directed complex network with multi-weights

张小芳, 冯慧芳. 基于轨迹大数据的动态最优路径规划[J]. 计算机与现代化, 2021, 0(11): 82-88.

ZHANG Xiao-fang, FENG Hui-fang. Dynamic Optimal Path Planning Based on Trajectory Big Data[J]. Computer and Modernization, 2021, 0(11): 82-88.

参考文献［23］

［1］	LAVALLE S M. Planning Algorithms［M］. New York: Cambridge University Press, 2006.
［2］	陈亮，何为，韩力群. 城市交通最优路径算法［J］. 智能系统学报, 2012,7(2):167-173.
［3］	FAN D K， SHI P. Improvement of Dijkstra’s algorithm and its application in route planning［C］// The 7th International Conference on Fuzzy Systems and Knowledge Discovery. New York: IEEE Journal of Oceanic Engineering, 2010:1901-1904.
［4］	吴红波，王英杰，杨肖肖. 基于Dijkstra算法优化的城市交通路径分析［J］. 北京交通大学学报， 2019，43(4):116-121.
［5］	WEI K C， GAO Y, ZHANG W， et al. A modified Dijkstra’s algorithm for solving the problem of finding the maximum load path［C］// 2019 IEEE International Conference on Information and Computer Technologies. 2019:10-13.
［6］	GUO D， WANG J， ZHAO J， et al. A vehicle path planning method based on a dynamic traffic network that considers fuel consumption and emissions［J］. Science of the Total Environment， 2019，663:935-943.
［7］	HUANG M， DING P. An improved ant colony algorithm and its application in vehicle routing problem［J］. Mathematical Problems in Engineering， 2013.DOI:10.1155/2013/785383.
［8］	马荣贵，崔华，薛世焦，等. 改进蚁群算法的多约束质量最优路径选择［J］. 西安电子科技大学学报（自然科学版）， 2016，43(3):185-189.
［9］	LIU L J， LUO S N， GUO F， et al. Multi-point shortest path planning based on an improved discrete bat algorithm［J］. Applied Soft Computing， 2020,95:Article ID 106498.〖HJ1.4mm〗
［10］	ZHANG J D， MENG W B, LIU Q Q， et al. Efficient vehicles path planning algorithm based on taxi GPS big data［J］. Optik， 2016，127(5):2579-2585.
［11］	ZHAO D B， STEFANAKIS E. Mining massive taxi trajectories for rapid fastest path planning in dynamic multi-level landmark network［J］. Computers, Environment and Urban System， 2018，72:221-231.
［12］	YAN L P， HU W B， HU S. SALA: A self-adaptive learning algorithm—towards efficient dynamic route guidance in urban traffic networks［J］. Neural Processing Letters， 2019，50(1):77-101.
［13］	KONG J T， HUANG J， YU H K， et al. RNN-based default logic for route planning in urban environments［J］. Neurocomputing， 2019，338:307-320.
［14］	王润泽，王亮，刘涛，等. 考虑实时路况反馈的动态路径规划算法研究［J］. 测绘科学， 2020，45(7):163-169.
［15］	张喜平，李永树，刘刚，等. 城市复杂交通网络道路重要性评估方法［J］. 复杂系统与复杂性科学, 2015,12(3):7-13.
［16］	姜桂艳，郭海锋，孟志强，等. 基于实时信息的城市道路交通状态评价指标体系研究［J］. 交通与计算机， 2007，25(5):21-24.
［17］	胡小文，杨东援. 城市快速道路交通流密度的估计［J］. 交通运输系统工程与信息， 2008，8(3):79-82.
［18］	臧广智,徐猛. 考虑多类型通勤者的高占有率车道均衡分析［J］. 交通运输系统工程与信息, 2020,20(3):150-155.
［19］	许华，王明刚. 基于组合权重灰色关联分析的城市循环经济发展评价［J］. 科学技术与工程， 2012,12(10):2499-2504.
［20］	SAATY T L， KEARNS K P. The analytic hierarchy process［J］. Analytical Planning， 1985，19-62. DOI:10.1016/B978-0-08-032599-6.50008-8
［21］	林克正，张元铭，李昊天. 信息熵加权的HOG特征提取算法研究［J］. 计算机工程与应用， 2020，56(6):147-152.
［22］	陈旭，陆丽丽，曹祖，等. 道路阻抗函数研究综述［J］. 交通运输研究, 2020,6(2):30-39.
［23］	FORNEY G D. The Viterbi algorithm［J］. Proceedings of the IEEE, 1973,61(3):268-278.