基于二维有向集合扩散的公交网路径搜索算法研究  

Research on Bus Exchanging Route Searching Algorithm Based on Orderly Spreaded Two-dimensional Set

作　　者：陆悠[1] 华泽[1] 张妮[1] 

机构地区：[1]苏州科技学院电子与信息工程学院,江苏苏州215000

出　　处：《计算机与现代化》2009年第12期25-28,32,共5页Computer and Modernization

摘　　要：公交网络路径搜索是智能交通系统中一个关键问题,传统的基于图论的路径算法有不易实现、大规模环境下时空开销大等缺点,本文将公交网络的路径本质归结为逻辑关系,路径的搜索归结为集合的运算,针对公交路径搜索的评价体系特点,在集合运算中添加方向的约束并以此评价路径,设计了二维有向集合扩散算法,借助关系代数和关系型数据库来实现该算法,经验证,本算法易实现、易扩充,在大规模公交网络和高并发查询情况下性能良好,有较高的实用价值。Route searching in the public transit network is a key matter for the intelligent transportation system. Traditional complicated Graph Theory-based algorithm costs too much on space and time within a big scale public transportation network. The public transit network can be reduced to the logic relation, and the route searching can be reduced to the set algorithm. Thinking about the route searching system characteristics, the algorithm is based on the direction. This searching algorithm based on order- ly spreaded two-dimensional set can be implemented by the means of the relational database, in conclusion, this algorithm is eas- y, flexible, effective in big scale network and with high practical value.

关 键 词：集合扩散算法 关系代数 公交网络 路径搜索 

分 类 号：TP274[自动化与计算机技术—检测技术与自动化装置]