交通信息网格中的最短出行路径并行算法

A Parallel Algorithm of the Shortest Travel Path in Traffic Information Grid

根据城市路网的特点,提出了一种新的路网图的分割方法;在此基础上,提出两种网格最短路径并行算法GPSPA1和GPSPA2.这两种算法克服了传统并行标签算法只适合在共享内存的并行机器上使用的缺点,适合网格环境下使用.实验结果表明:分割器不能完全分割源点和目标点时,GPSPA2比GPSPA1效率高;完全分割时,两种并行算法的加速比大约都是3.GPSPA2应用于交通信息服务网格系统2.0版中.

Two parallel algorithms of the shortest travel path, GPSPA1 and GPSPA2 are presented on the basis of a new partition method of road nets. The disadvantages of traditional parallel label algorithms are overcome and heterogeneous duster can be fit in. The experimental results show that the speedup ratios of the two algorithms are about 3 when a cutter can partition the O-D completely, and that GPSPA2 is better than GPSPA1 in other cases. GPSPA2 is applied in the version 2.0 of TIG.