智能交通路径规划算法研究综述

doi:10.16180/j.cnki.issn1007-7820.2022.07.004

摘要/Abstract

摘要：

为了解决城市道路的交通拥堵、交通安全与环境污染等多种问题,路径规划算法及车辆自组织网等多种技术逐渐成为智能交通领域中的重要研究方向,并获得了大量关注。近年来,智能交通的应用和普及为路径规划算法提供了丰富多样的研究课题,而对路径规划算法的研究也有力地促进了智能交通的尖端技术的开发。文中回顾了多项路径规划算法,并总结了这些算法中存在的问题。在此基础上,深入梳理分析了静态与动态路径规划算法的优势和劣势,提出了智能交通中路径规划算法的未来研究趋势及方法。

关键词: 智能交通, 路径规划, 动态导航, 路网模型, 地图匹配, 静态约束, 车辆类别, 动态规划

Abstract:

In order to solve problems such as traffic congestion, traffic safety and environmental pollution of urban roads, a variety of technologies including path planning algorithm and vehicle self-organizing network have gradually become important research directions in the field of intelligent transportation and attracted a lot of attention. In recent years, the application and popularization of intelligent transportation provide rich and diverse research topics for the research of path planning algorithm, and the research of path planning algorithm also effectively promotes the development of cutting-edge technology of intelligent transportation. By reviewing the research of multiple path planning algorithms, this study summarizes the existing problems in the research of path planning algorithms. On this basis, this study deeply studies and analyzes the advantages and disadvantages of static and dynamic path planning algorithms, and puts forward the future research trend and methods of path planning algorithms in intelligent transportation.

Key words: intelligent transportation, path planning, dynamic navigation, road network model, map matching, static constraints, vehicles category, dynamic programming

中图分类号:

TP301.6

卢东祥. 智能交通路径规划算法研究综述[J]. 电子科技, 2022, 35(7): 22-27.

LU Dongxiang. A Survey of Intelligent Transportation Path Planning Algorithms[J]. Electronic Science and Technology, 2022, 35(7): 22-27.

参考文献 45

[1]	宋锋. 基于蚁群算法-有限元的结构优化方法研究[D]. 南京: 南京航空航天大学, 2007.
	Song Feng. Research on structural optimization method based on ant colony algorithm-FEM[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2007.
[2]	郝伟. 蚁群最短路径算法优化及其在GIS中的应用研究[D]. 西安: 西北大学,2009.
	Hao Wei. Shortest path algorithm of ant colony optimzation and its application in GIS reseach[D]. Xi’an: Northwestern University, 2009.
[3]	杨玉红. 城市车辆动态诱导系统关键技术研究[D]. 沈阳: 沈阳大学, 2013.
	Yang Yuhong. Research on the key technology of the urban vehicle dynamic guidance system[D]. Shenyang: Shenyang University, 2013.
[4]	Colorni A. Distributed optimization by ant colonies[C]. Boston: Proceedings of the First European Conference on Artificial Life, 1991.
[5]	Dorigo M, Gambardella L M. Ant colony system:a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997(1):53-66.
[6]	朱庆保, 张玉兰. 基于栅格法的机器人路径规划蚁群算法[J]. 机器人, 2005, 27(2):132-136.
	Zhu Qingbao, Zhang Yulan. An ant colony algorithm based on grid method for mobile robot path planning[J]. Robot, 2005, 27(2):132-136.
[7]	柳长安, 鄢小虎, 刘春阳, 等. 基于改进蚁群算法的移动机器人动态路径规划方法[J]. 电子学报, 2011, 39(5):1220-1224.
	Liu Changan, Yan Xiaohu, Liu Chunyang, et al. Dynamic path planning for mobile robot based on improved ant colony optimization algorithm[J]. Acta Electronica Sinica, 2011, 39(5):1220-1224.
[8]	史恩秀, 陈敏敏, 李俊, 等. 基于蚁群算法的移动机器人全局路径规划方法研究[J]. 农业机械学报, 2014, 45(6):53-57.
	Shi Enxiu, Chen Minmin, Li Jun, et al. Research on method of global path-planning for mobile robot based on ant-colony algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2014, 45(6):53-57.
[9]	Fan X, Xiong L, Sheng Y, et al. Optimal path planning for mobile robots based on intensified ant colony optimization algorithm[C]. Shanghai: International Conference on Robotics,IEEE, 2003.
[10]	Hsiao Y T, Chuang C L, Chien C C. Ant colony optimization for best path planning[C]. Tokoyo: IEEE International Symposium on Communications & Information Technology, 2004.
[11]	Yi W, Kumar A. Ant colony optimization for disaster relief operations[J]. Transportation Research Part E:Logistics and Transportation Review, 2007, 43(6):660-672. doi: 10.1016/j.tre.2006.05.004
[12]	Attiratanasunthron N, Fakcharoenphol J. A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs[J]. Information Processing Letters, 2008, 105(3):88-92. doi: 10.1016/j.ipl.2007.08.013
[13]	Gajpal Y, Abad P L. Multi-ant colony system(MACS) for a vehicle routing problem with backhauls[J]. European Journal of Operational Research, 2009, 196(1):102-117. doi: 10.1016/j.ejor.2008.02.025
[14]	Duan P, Xiong S, Jiang H. Multi-objective optimization model based on heuristic ant colony algorithm for emergency evacuation[C]. Nanjing: International IEEE Conference on Intelligent Transportation Systems, 2012.
[15]	Song F, Wang L. Application of improved ant colony optimization in intelligent transportation[J]. Mathematics in Practice and Theory, 2013, 43(3):66-72.
[16]	Ma J, Tan X, Xu W. Study on VRP based on improved ant colony optimization and internet of vehicles[C]. Bismarck: Transportation Electrification Asia-pacific, 2014.
[17]	Katona G, Lenart B, Juhasz J. Compare Ant-colony and Genetic algorithm for shortest path problem and introduce their parallel implementations[C]. Chicago: International Conference on Models & Technologies for Intelligent Transportation Systems, 2015.
[18]	Mouhcine E, Mansouri K, Mohamed Y. An improved swarm optimization algorithm for vehicle path planning problem[C]. Cincinati: The Fourth IEEE International Colloquium on Information Science and Technology, 2016.
[19]	Zuo L, Lei S, Dong S, et al. A Multi-objective optimization scheduling method based on the ant colony algorithm in cloud computing[J]. IEEE Access, 2017, 3(1):2687-2699. doi: 10.1109/ACCESS.2015.2508940
[20]	Cheng R, Y Song, Chen D, et al. Intelligent positioning approach for high speed trains based on ant colony optimization and machine learning algorithms[J]. IEEE Transactions on Intelligent Transportation Systems, 2019, 20(10):3737-3746. doi: 10.1109/TITS.2018.2878442
[21]	Lin C, Han G, Du J, et al. Spatiotemporal congestion-aware path planning toward intelligent transportation systems in software-defined smart city IoT[J]. IEEE Internet of Things Journal, 2020, 7(9):8012-8024. doi: 10.1109/JIOT.2020.2994963
[22]	Xiang X, Tian Y, Zhang X, et al. A pairwise proximity learning-based ant colony algorithm for dynamic vehicle routing problems[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 1(2):1-12
[23]	Goldberg D E, Richardson J. Genetic algorithms with sharing for multimodal function optimization[C]. Agris: Proceedings of the Second International Conference on Genetic Algorithms, 1987.
[24]	Holland, John H.Genetic algorithms and the optimal allocation of trials[J]. Siam Journal on Computing, 1973, 2(2):88-105. doi: 10.1137/0202009
[25]	Parker J K, Khoogar A R, Goldberg D E. Inverse kinematics of redundant robots using genetic algorithms[C]. Frankfort: IEEE International Conference on Robotics and Automation, 1989.
[26]	Juidette H, Youlal H. Fuzzy dynamic path planning using genetic algorithms[J]. Electronics Letters, 2000, 36(4):374-376. doi: 10.1049/el:20000314
[27]	Pernas F, Higuera J, Rondón F J. Route optimization for intelligent transport system using genetic algorithms[C]. Houston: Automotive and Transportation Technology Congress and Exposition, 2001.
[28]	张飞舟, 晏磊, 范跃祖, 等. 智能交通系统中的运营车辆优化调度研究[J]. 北京航空航天大学学报, 2002, 28(6):707-710.
	Zhang Feizhou, Yan Lei, Fan Yuezu, et al. Optimizing dispatching of public traffic vehicles in intelligent transport system[J]. Journal of Beijing University of Aeronautics and Astronautics, 2002, 28(6):707-710.
[29]	Chan W T, Tao F. Using GIS and genetic algorithm in highway alignment optimization[C]. Tianjin: Intelligent Transportation Systems, 2003.
[30]	Xie S Y, Gao S, Xu B. Study of an optimum scheduling algorithm about buses in city intelligent transport systems[C]. Kansas City: International Conference on Machine Learning & Cybernetics, 2004.
[31]	Garzia F, Perna C, Cusani R. UMTS network planning using genetic algorithms[C]. Rome: WIT Transactions on the Biomedicine and Health, 2005.
[32]	Yu L, Gong J, Zhang J, et al. Genetic-algorithm-based path optimization methodology for spatial decision[C]. Los Angeles: Geoinformatics,Geospatial Information Science. International Society for Optics and Photonics, 2006.
[33]	Mahjoubi H, Bahrami F, Lucas C. Path planning in an environment with static and dynamic obstacles using genetic algorithm:a simplified search space approach[C]. Memphis: IEEE Congress on Evolutionary Computation, 2006.
[34]	Li Q, Liu G, Wei Z, et al. A specific genetic algorithm for optimum path planning in intelligent transportation system[C]. Lincoln: International Conference on Its Telecommunications, 2007.
[35]	Arunadevi J, Johnsanjeevkumar A, Sujatha N. Intelligent transport route planning using parallel genetic algorithms and MPI in high performance computing cluster[C]. Miami: Proceedings of the Fifteenth International Conference on Advanced Computing and Communications, 2007.
[36]	Mohamed M. Generic parallel genetic algorithms framework for optimizing intelligent transportation systems[D]. Toronto: University of Toronto, 2007.
[37]	Lin C, Yu J, Liu J, et al. Genetic algorithm for shortest driving time in intelligent transportation systems[C]. Dallas: International Conference on Multimedia and Ubiquitous Engineering, 2008.
[38]	Kumar A, Arunadevi J, Mohan V. Intelligent transport route planning using genetic algorithms in path computation algorithms[J]. European Journal of Scientific Research, 2009, 25(3):463-468.
[39]	Zou G, Kulkani R. A systematic genetic algorithm based framework to optimize intelligent transportation system(ITS) strategies[C]. Houston: ITS America's Twenty-third Annual Meeting & Exposition, 2013.
[40]	张礼华, 廖闻剑, 彭艳兵. 求解物流路径优化的改进遗传算法研究[J]. 电子设计工程, 2016, 24(10):13-16,20.
	Zhang Lihua, Liao Wenjian, Peng Yanbing. Research on improved genetic algorithm for solving optimization of logistics distribution route[J]. Electronic Design Engineering, 2016, 24(10):13-16,20.
[41]	刘艳秋, 刘博. 交通拥堵下基于实时交通信息的路径选择模型[J]. 沈阳工业大学学报, 2014, 36(4):426-430.
	Liu Yanqiu, Liu Bo. Route selection model based on real-time traffic information under traffic congestion[J]. Journal of Shenyang University of Technology, 2014, 36(4):426-430.
[42]	Souza A M, Yokoyama R S, Maia G, et al. Real-time path planning to prevent traffic jam through an intelligent transportation system[C]. Honolulu: International Conference on Computers & Communication,IEEE, 2016.
[43]	Han Z, Wang D, Feng L, et al. Multi-AGV path planning with double-path constraints by using an improved genetic algorithm[J]. Plos One, 2017, 12(7):1747-1765.
[44]	Yang S, Ou J, Feng Y, et al. Freeway travel time estimation based on the general motors model: a genetic algorithm calibration framework[J]. IET Intelligent Transport Systems, 2019, 13(7):1154-1163. doi: 10.1049/iet-its.2018.5540
[45]	Zha Z, Li C, Xiao J, et al. An improved adaptive clone genetic algorithm for task allocation optimization in ITWSNs[J]. Journal of Sensors, 2021, 2(4):1-12.