摘要
大规模多换乘网络中最短时间路径精确查询的算法是公交网络寻径问题的研究难点之一,近似搜索算法的求解满意度不高,而精确搜索算法的效率较低。提出了基于路径集合运算的公交网络寻径算法,按换乘次数从低到高依次求取路径集合,通过删除大量冗余路径来优化路径集合并减少计算量,最后生成最短时间路径汇总集合用于快速精确寻径。实验结果表明了算法的可行性和有效性。
Path searching problem of public transit network is NP-hard, one of whose nodus is the algorithm of accurately searching shortest-time-path in large multi-transfer network. A searching algorithm of public traffic network, based on path set calculation,was proposed to solve the nodus. Path sets are generated from low to high in accordance with the number of transfer,optimized by deleting redundant paths to reduce storage space and computation, and summarized to generate summary shortest-time-path set, which is used to search optimal path rapidly and accurately. Experimental results of Beijing public transit network show the algorithm is feasible and effective.
出处
《计算机科学》
CSCD
北大核心
2009年第6期239-240,272,共3页
Computer Science
基金
湖南省教育厅科研项目(08C790)
湖南省科技厅科技计划项目(2008FJ3089)资助
关键词
公交网络
寻径算法
多换乘
路径集合运算
最短时间路径
Public transit network, Searching algorithm, Multi-transfer, Path set calculation, Shortest-time-path
