两种策略下的最短路径并行算法研究与实现

随着智能交通运输系统的研究与应用,对在大规模交通网络上求解最短路径的实时性提出了更高的要求。为了找出适用于实际交通网络的高效最短路径并行算法,首先选取了3种最短路径标号串行算法,以此为基础分别实现了网络复制及网络分割两种策略下求解最短路径的并行算法。最后,从基于G IS的交通规划软件T ransCAD中提取了实际交通路网数据,同时还随机产生了不同规模的稀疏格网,在这些网络中对并行算法的性能进行了测试和分析。结果表明,在8台机器上求解含5 181个节点的实际交通网络中32个源点的最短路径时,基于网络分割的双队列标号修正并行算法的加速比可达到6.32,在其他网络中也表现出较好的加速比及可扩展性。

Study and Implement of Shortest Path Parallel Algorithms with Two Strategies

With the research and application of Intelligent Transportation System,there is a higher requirement for solving the shortest path problem in large scale transportation networks in real time.To find out the effective shortest path parallel algorithms for the actual transportation networks,three labeling shortest path algorithms are firstly chosen to be parallelized.The parallel shortest path algorithms are then implemented based on both network duplication strategy and network partition strategy.The speed-up ratio and efficiency of parallel algorithms are then tested and analyzed in both actual road networks which are obtained from the transportation planning software based on GIS,TransCAD,and grid networks of different scales which are generated randomly.From the results,it is concluded that the speed-up ratio of two-queue label-correcting parallel algorithm with the strategy of network partition can reach(6.32),when solving the shortest path problem of 32 sources in actual transportation network including (5 181) nodes on eight computers.It also shows similar excellent speed-up and scalability in other test networks.