一种适于车辆导航系统的快速路径规划算法  

A Quick Path-Planning Algorithm for Vehicle Navigation System

作　　者：毕军[1] 付梦印[1] 周培德[2] 

机构地区：[1]北京理工大学自动控制系,北京100081 [2]北京理工大学计算机科学与工程系,北京100081

出　　处：《北京理工大学学报》2002年第2期188-191,共4页Transactions of Beijing Institute of Technology

基　　金：兵科院预研项目

摘　　要：针对城市道路网图节点数较多 ,经典的求解最短路径的 Dijkstra算法存在计算时间较长的问题 .对矢量化的城市道路网图的特点进行分析 ,给出了道路网图的计算机存储结构 ,提出一种快速求解城市道路网两节点间的最短路径近似算法 .算法的实现采用双向式搜索法、投影法和夹角最小的方法 .理论分析和实验结果表明 ,和Dijkstra算法相比 ,该算法尽管有时得不到最优解 ,但能大大减小搜索空间 ,提高搜索速度 ,时间复杂性不超过O( N ) 。The computing time of the Dijkstra algorithm which is considered a typical algorithm for the shortest path computation is relatively long, if a city's road net map has many nodes. To improve the situation, the characteristics and data structure of the vector map of a city's road net are discussed, and then a quick approximate algorithm for the shortest path between two nodes in a city's road net is proposed. The algorithm takes advantage of the methods of bidirection, projection and minimum angle. Analysis in theory and experimental results show that compared with the Dijkstra algorithm, although the new algorithm cannot reach the optimum occasionally, it can greatly reduce the seeking space and increase the seeking speed. Its time complexity can not exceed O(N) , and can well be applied to vehicle navigation systems.

关 键 词：最短路径 车辆导航系统 快速路径规划算法 

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