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

摘要：

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

关键词：多线程、并行计算、路径规划、启发式搜索

所属期刊栏目：20

资助基金：国家自然科学基金项目61432016、61303047;广东省普通高校国家级重大培育项目2014GKXM054;广东省普及型高性能计算机重点实验室2017B030314073

在线出版日期：2018-07-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：753-761