基于CUDA的并行联程路径搜索算法

CUDA-based Parallel Interline Path-searched Algorithm

随着民航业的蓬勃发展,形成了庞大的航线网络,在众多城市间有很多航线可供选择。如何快速地从如此庞大的网络中得到K条最短路径(K-Shortest-Path,简称KSP)成了联程路径搜索的瓶颈。采用Yen算法求解航线网络中的KSP问题,并在CU-DA平台下实现其并行化。并行的基本策略是借助GPU平台并行的松弛每个节点的相关边。最后,通过在CUDA平台下的实验结果表明,与串行Yen算法计算相比,基于CUDA的并行Yen的计算速度得到了很大的提高。

With the vigorous development of the civil aviation industry, there has already formed an extensive route network, and there are many routes to choose from between the same cities taken-off and landed. How quickly to find K shortest paths （K-Shortest-Path, KSP） becomes a bottleneck of interline path-searched algorithm in such a large network. This article adopts the Yen algorithm to solve the KSP problem in the route network, and to achieve its parallelism in CUDA platform. The basic parallel strategy is to use the classic algorithm for finding the shortest path, then according to the Yen algorithm proposing restrictions to define.~leviated nodes, and finally departing from nodes parallel multi-core graphics to find candidate paths. On the basis of the aboved process, the experimental results show that compared with the serial Yen algorithm, calculation speed of parallel Yen based on the the CUDA greatly improves.