一种基于SuperMap GIS的改进Dijkstra算法

为提高传统Dijkstra算法的搜索效率,满足车载导航中路径规划实时性的要求,本文利用SuperMapGIS平台的网络编辑功能,设计了一种基于SuperMap的改进Dijkstra算法。首先,结合道路网络的空间分布特性,在SuperMap中构建了道路网络;其次,设计算法,根据起止节点合理限制算法的搜索区域,并以经典Dijkstra为理论基础实现最短路径的求解;最后,结合需要设计了约束条件下的路径规划算法。在城市道路网络中的应用实例验证了算法的有效性。

An Improved Dijkstra Algorithm Based on SuperMap GIS

Path planning is a process to find the optimal path from the starting node to the destination node.Tens of algorithms have been designed to resolve the shortest path problem,in which the Dijkstra algorithm is always thought to be the most mature and classical one.However,its higher time complexity greatly restricts its practical application.Besides,for most path planning algorithms,the road network is considered as an ordinary plane network and the spatial distribution characteristics are ignored,therefore,the path planning algorithm can not do well in real road network.In order to improve the searching efficiency of the traditional Dijkstra algorithm and to meet the requirement of real-time vehicle navigation,a path planning algorithm based on SuperMap is designed by utilizing the network editing function of SuperMap GIS platform.Firstly,with the spatial distribution characteristics,a road network is built in SuperMap.In this process,we take three-dimensional transport and one-way road network into consideration,making the road network built in SuperMap able to reproduce the real road network.For three-dimensional transport,we set the parameters of non-broken lines and make sure the roads not in the same plane have no intersections;for one-way roads,the forward resistance and reverse resistance are set with different weights.Secondly,in order to improve the searching efficiency of the traditional Dijkstra algorithm,we propose a method to restrict the searching area.According to the coordinate relationships of the starting node and the destination node,we create a hexagon area,which contains the staring node and the destination node,as the restricted searching area,and make the algorithm able to search the shortest path within the restricted searching area on the theoretical basis of the classic Dijkstra algorithm.Thirdly,based on the actual needs,the path planning algorithm with certain constraints is designed.The constraints are prohibit a certain way and must pass through a certain point.At last,we apply the algorithm proposed in this paper to urban road network and compare it with traditional Dijkstra algorithm.The results show that,due to the searching area is restricted reasonably,the two algorithms get the same shortest path,but the time spent by the algorithm proposed in this paper is much less.Besides,the algorithm proposed in this paper can do well in path planning with constraints.Thus,the improved Dijkstra algorithm based on SuperMap GIS has a strong practicability,and can be used in real-time vehicle navigation.