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

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

作　　者：章昭辉[1] 闫春钢[1] 丁志军[1] 蒋昌俊[1] 

机构地区：[1]同济大学计算机科学与技术系

出　　处：《同济大学学报（自然科学版）》2006年第12期1606-1611,共6页Journal of Tongji University:Natural Science

基　　金：国家"九七三"重点基础研究发展计划资助项目(2003CB316902);上海市重大科技攻关资助项目(05DZ15007)

摘　　要：根据城市路网的特点,提出了一种新的路网图的分割方法;在此基础上,提出两种网格最短路径并行算法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.

关 键 词：交通信息网格 最短路径 并行算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]