电子学报 ›› 2021, Vol. 49 ›› Issue (11): 2273-2278.DOI: 10.12263/DZXB.20200436

• 科研通信 • 上一篇    下一篇

主存高效的公交网络路径规划索引

马慧1, 汤庸2, 何怀文1   

  1. 1.电子科技大学中山学院计算机学院, 广东 中山 528402
    2.华南师范大学计算机学院, 广东 广州 510631
  • 收稿日期:2020-05-07 修回日期:2021-05-19 出版日期:2021-11-25 发布日期:2021-11-25
  • 作者简介:马 慧 女,1981年生,博士,副教授.研究方向为大规模图数据处理.
    汤 庸(通信作者) 男,1964年生,博士,教授,学者网创始人(个人主页Scholat.com/ytang).主要研究领域为学术社交网络、教育大数据服务.E-mail:ytang@scnu.edu.cn
  • 基金资助:
    国家自然科学基金(U1811263);中山市社会公益科技研究(2019B2006);中山市重大科技专项(2019A40027)

Memory Efficient Index for Route Planning in Public Transportation Networks

Hui MA1, Yong TANG2, Huai-wen HE1   

  1. 1.School of Computer Science,University of Electronic Science and Technology of China,Zhongshan Institute,Zhongshan,Guangdong 528402,China
    2.School of Computer Science,South China Normal University,Guangzhou,Guangdong 510631,China
  • Received:2020-05-07 Revised:2021-05-19 Online:2021-11-25 Published:2021-11-25

摘要:

在公交时间表下给定起始和目标站点, 路径规划查询返回一组到达时间早和换乘次数少的帕雷托最优路径.现有的索引方法需要大量运行时内存.本文提出主存空间高效的索引方法(a-)PAINT. (a-)PAINT对每个站点v预计算一组标签,使得对于从站点s到站点d的查询可以通过匹配sd相关的标签高效地生成查询结果的一条路径. PAINT对任意查询返回最优路径. a-PAINT只需要很小的预处理开销,但可能返回多一趟换乘的次优路径.用真实的公交时间表与模拟查询测试,PAINT具有合理的预处理开销. a-PAINT需要更少量的预处理开销,在大规模公交网络下准确率达90%.

关键词: 路径规划, 索引, 公交网络, 时间表, 换乘次数

Abstract:

Given a source stop and a destination stop in a transportation timetable, the route planning query returns a Pareto set of paths that optimized in both earlier arrival time and less transfer times. Current indexing methods require large runtime memory. This paper proposes a memory space efficient index method (a-)PAINT. (a-)PAINT pre-computes, for each stop v, a set of labels, such that, for any query from stop s to stop d, we can efficiently retrieve a path of the query result from the label sets of s and d. PAINT could return optimal paths for every query. a-PAINT incurs far less preprocessing overheads, but might return sub-optimal path that takes one more transfer. We experimentally conducted simulated queries on real timetables. PAINT incurs reasonable preprocessing overheads. a-PAINT requires far less preprocessing overheads, and it has accurate rate up to 90% in large timetables.

Key words: route planning, index, public transportation network, timetable, transfer times

中图分类号: