SA*：一种多线程路径规划算法

路径规划问题是路网交通应用中的一个基础问题。A*算法是一个求解点到点最短路径问题的高效算法。但随着路网数据规模的增长,A*难以保证求解的实时性。利用并行计算进行加速是常用的算法性能提高手段,然而A*算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化。本文提出一种分段化搜索的改进A*算法（SA*）。该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解。分段搜索本身可以减少路径规划的搜索空间,借助多线程并行则可以进一步提高求解速度。实验结果表明,在真实路网数据上,利用16核的机器,SA*的性能可以达到A*算法的10-30倍。

SA*: A Multi-thread Path Routing Algorithm

Path routing problem is a fundamental problem in many applications on road networks. The A* algorithm is an efficient method to find the point-to-point path. Road networks with Cartesian coordinates can provide Euclidean distance as a heuristic function to guide the search direction of A*, then A* can simply and intuitively outperforms the classic Dijkstra's algorithm. However, Euclidean distance is a fairly relaxed lower bound of the real distance. It limits the potential of pruning more search space of A* on road networks. Higher performance is needed to fit the real-time requirement in the application on large-scale networks. Parallel computing is an effective approach to accelerate many algorithms. However, there are strong data dependencies between iterations of A*, and each iteration has little potential parallelism because of the low-dimensional property of road network. Thus, it is difficult to efficiently exploit the availability of multiple cores with the standard A* algorithm. In this paper, we propose Segmented A* (SA*) algorithm, which is more adaptable to modern multi-core CPU platform than A*. It selects some waypoints that split the required shortest path into several segments, then it searches on each segment separately and concatenates these segments as an approximate result. SA* performs better than A* on account of two factors. One is that sequential SA* can prune more search space than A*. The other is that the searches of SA* on segments can be parallelized, so SA* can make better use of multi-core CPU. The selection of waypoints has a key impact on both calculation performance and the accuracy of path. To exploit the benefit from segmented search and meanwhile reduce the performance overhead from this selection, we consider using some low-cost heuristic strategies to select the waypoints before handling each path routing sub-problem. At first, we rapidly calculate a rough path as a guidance, then select the nodes in this rough path that uniformly split the path to several segments. We can easily guarantee that each segment has the same number of nodes. This split has more possibility to lead to a balanced search space in parallel calculating each segment. In our experiments, using 16 cores, SA* can be 30 times faster than A* on a large-scale real-world road network with a loss of path accuracy less than 10%.