基于云计算的大规模交通路网的最短路径算法

作者：张东波; 林永杰^*; 卢凯; 首艳芳; 徐建闽

来源：华南理工大学学报(自然科学版), 2018, 46(12): 139-146.

• 最短路径
• 大规模路网
• 并行计算
• 子图分割

针对大规模路网路径搜索算法计算量大、耗时长、效率低等问题,采用MapRe-duce并行编程模型计算框架,利用网络中大量不同位置的计算机进行集群式海量数据计算,解决基于大规模路网分割成若干子图并行计算问题.本文基于MapReduce构建一个新的计算框架,建立了基于子图分割的并行搜索方法,实现超大规模真实交通路网中最短路径搜索.案例分析证明:该方法能够在可接受的计算时间内提供高质量的最短路径搜索服务.

• 单位
  华南理工大学; 广州现代产业技术研究院; 广东省智能制造研究所