基于节点可达度的公交多路径搜索算法  

Multi-path search algorithm in public transportation based on node accessibility

作　　者：符光梅[1,2] 王红[1,2] 

机构地区：[1]山东师范大学信息科学与工程学院,济南250014 [2]山东省分布式计算机软件新技术重点实验室,济南250014

出　　处：《计算机应用研究》2012年第12期4492-4494,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(60970004);山东省研究生教育创新计划资助项目(SDYY10059)

摘　　要：针对公交网络路径搜索问题,以复杂网络的角度进行了相关研究。根据出行者实际需求,提出一种基于节点可达度的公交多路径搜索算法。采用复杂二分网络模型来描述公交网络,将公交线路和公交站点分别看做一类节点,每条公交线路与它所经过的公交站点之间存在连边;在分析网络社团结构的基础上定义了节点可达度,算法根据节点可达度逐步搜索直至目的节点,搜索过程保留可能存在的多条最佳路径。实验结果表明,该方法能够得到最小换乘的多条有效路径。This paper studied path search problem in public transport network from the perspective of complex network, and proposed a multi-path search algorithm in public transportation based on node accessibility from the actual needs of travelers. This algorithm represented public transport network with complex bipartite network, which regarded bus lines and bus stations as different kinds of nodes respectively and there was an edge between each line and every station it passed. Based on the anal- ysis of network community, it defined a concept of node accessibility. The algorithm searched paths from source node to destination node according to node accessibility and it reserved multiple possible optimal paths. Experiment result shows that this algorithm can find several effective paths which have the minimum transfer times.

关 键 词：二分网络 节点可达度 公交网络 多路径搜索 

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