《计算机应用研究》|Application Research of Computers

公交网络路径规划问题中的一种高效索引方法

Efficient index for route planning in public transportation network

免费全文下载 (已被下载 次)  
获取PDF全文
作者 马慧,汤庸,梁瑞仕
机构 1.电子科技大学中山学院 计算机学院,广东 中山 528400;2.华南师范大学 计算机学院,广州 510631
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2019)08-021-2342-07
DOI 10.19734/j.issn.1001-3695.2018.02.0088
摘要 TTL是在公交网络中求解最早到达路径、最晚出发路径和最短耗时路径的一种高效索引。TTL采用Time-dependent为核心算法构建索引,存在两个不足:a)大量的昂贵的出堆操作拖慢了建立索引的效率;b)所求得的路径具有较多的换乘次数。针对这两个不足,提出了一种基于旅程的索引TAIL。TAIL预先生成部分路径,在查询阶段通过匹配部分路径得到最优解,避免在原图上进行查询,提高效率。TAIL并不是基于图结构,而是以旅程为单位存储公交数据。在生成路径时,首先扫描路过起点的旅程,找到从起点直达的站点;然后扫描从直达站点出发的旅程,找到一次换乘可达的站点;如是这般,从可达站点出发扫描旅程,发现更多的可达站点。为了在早期找到最早到达路径,从而减少旅程的扫描量,TAIL并没有严格按照换乘次数的顺序扩展站点。这种方法避免了昂贵的堆操作,也保留了旅程的完整性。在真实数据集上测试表明,与TTL相比,TAIL有较短的建立索引的时间,生成的路径的换乘次数也较少。
关键词 最短路径; 公交网络; 路径规划; 索引; 时间表; 换乘次数
基金项目 国家自然科学基金资助项目(61772211)
广东省高等学校优秀青年教师项目(YQ2015241,YQ2015242)
广东省青年创新人才类项目(2015KQNCX206)
中山市科技计划项目(2015B2307,2016B2158)
本文URL http://www.arocmag.com/article/01-2019-08-021.html
英文标题 Efficient index for route planning in public transportation network
作者英文名 Ma Hui, Tang Yong, Liang Ruishi
机构英文名 1.School of Computer,Zhongshan Institute,University of Electronic Science & Technology of China,Zhongshan Guangdong 528400,China;2.School of Computer,South Normal University,Guangzhou 510631,China
英文摘要 TTL is a highly efficient indexing structure for finding an earliest arrival path, or a latest departure path, or a shortest duration path in public transportation networks. TTL uses Time-dependent algorithm as its core algorithm to build index, and is therefore, results in two deficiencies. Firstly, it needed relatively expensive priority queue operations. Secondly, it would generate paths with more transfers. This paper proposed a new indexing structure, TAIL, which used a trip-based method to build index. TTL pre-computed some canonical paths. A query could be answered by matching up the canonical paths, which avoided traversing the entire network. Instead of the graph structure, TAIL used trip array as its input, and generated paths by scanning trips. Initially, TAIL scanned trips starting from the source stop, from which TAIL obtained direct reachable stops. After that, TAIL scanned trips starting from the direct reachable stops, from which TAIL obtained reachable stops within one transfer. Generally, TAIL discovered new reachable stops from scanning the trips starting at the already discovered reachable stops. In order to obtain the earliest arrival paths in the early stage, so as to reduce the number of trip scanning, TAIL did not scan the stops strictly in increasing order of their transfer times. In this way, TAIL avoids valuable priority queue operations, while preserves the entity of a trip. Experiments on real datasets shows that, compared to TTL, TAIL has lower index construction time and its generated path has fewer transfer times.
英文关键词 shortest path; public transportation network; route planning; index; time table; transfer times
参考文献 查看稿件参考文献
 
收稿日期 2018/2/23
修回日期 2018/3/29
页码 2342-2348
中图分类号 TPT311.13
文献标志码 A