Dynamic Optimal Path Planning Based on Trajectory Big Data

Abstract

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

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

References ［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.