基于改进A*算法的高速公路互联网地图最短路径搜索研究  

Shortest Path Search of Expressway Internet Map Based on Improved A* Algorithm

作　　者：聂易彬 谭明军[2] 刘刚 马璐[2] NIE Yibin;TAN Mingjun;LIU Gang;MA Lu(China Merchants Expressway Network&Technology Holdings Co.,Ltd.,Beijing 100022,China;China Merchants Chongqing Communications Technology Research&Design Institute Co.,Ltd.,Chongqing 400067,China)

机构地区：[1]招商局公路网络科技控股股份有限公司,北京100022 [2]招商局重庆交通科研设计院有限公司,重庆400067

出　　处：《公路交通技术》2020年第4期110-114,共5页Technology of Highway and Transport

摘　　要：为解决高速公路互联网地图中最短路径的搜索问题,根据高速公路互联网地图的特点,对传统A*算法中的网络节点、数据库、启发式函数进行了改进,并通过重庆市高速公路互联网地图实例对改进A*算法进行了应用验证。结果表明,采用改进A*算法可找到高速公路互联网地图中的最短路径,且最短路径的搜索时间控制在毫秒级,能够满足大区域高速公路互联网地图最短路径的搜索要求。In order to solve the problem of searching for the shortest path in the Internet map of expressways,this paper improves the network nodes,databases,and heuristic functions in the traditional A*algorithm according to the characteristics of the expressway internet map.Then,the application and verification of the improved A*algorithm are carried out through the example of the internet map of Chongqing Expressway.The results show that the improved A*algorithm can be used to find the shortest path in the expressway internet map,and the search time of the shortest path is controlled in milliseconds,which can meet the shortest path search requirements of large area expressway internet map.

关 键 词：A*算法 高速公路 互联网地图 最短路径 启发式函数 

分 类 号：U495[交通运输工程—交通运输规划与管理]