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

针对公交网络路径搜索问题,以复杂网络的角度进行了相关研究。根据出行者实际需求,提出一种基于节点可达度的公交多路径搜索算法。采用复杂二分网络模型来描述公交网络,将公交线路和公交站点分别看做一类节点,每条公交线路与它所经过的公交站点之间存在连边;在分析网络社团结构的基础上定义了节点可达度,算法根据节点可达度逐步搜索直至目的节点,搜索过程保留可能存在的多条最佳路径。实验结果表明,该方法能够得到最小换乘的多条有效路径。

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

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 analysis 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.