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

马慧; 汤庸; 何怀文

doi:10.12263/DZXB.20200436

您当前的位置：

首页 >

文章列表页 >

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

科研通信 | 更新时间：2025-12-08

- 主存高效的公交网络路径规划索引
- Memory Efficient Index for Route Planning in Public Transportation Networks
- 电子学报 2021年49卷第11期页码：2273-2278
- 作者机构：
  
  1.电子科技大学中山学院计算机学院,广东中山528402
  2.华南师范大学计算机学院,广东广州 510631
- 作者简介：
  
  [ "马　慧　女,1981年生,博士,副教授.研究方向为大规模图数据处理." ]
  [ "汤　庸（通信作者）　男,1964年生,博士,教授,学者网创始人（个人主页Scholat.com/ytang）.主要研究领域为学术社交网络、教育大数据服务.E-mail:ytang@scnu.edu.cn" ]
- 基金信息：
  
  国家自然科学基金(U1811263;61772211);中山市社会公益科技研究(2019B2006);中山市重大科技专项(2019A40027)
- DOI：10.12263/DZXB.20200436
  中图分类号： TP392
- 收稿：2020-05-07，
  
  修回：2021-05-19，
  
  纸质出版：2021-11-25
- 稿件说明：
移动端阅览
马慧,汤庸,何怀文.主存高效的公交网络路径规划索引[J].电子学报,2021,49(11):2273-2278.

MA Hui,TANG Yong,HE Huai-wen.Memory Efficient Index for Route Planning in Public Transportation Networks[J].ACTA ELECTRONICA SINICA,2021,49(11):2273-2278.
马慧,汤庸,何怀文.主存高效的公交网络路径规划索引[J].电子学报,2021,49(11):2273-2278. DOI： 10.12263/DZXB.20200436.

MA Hui,TANG Yong,HE Huai-wen.Memory Efficient Index for Route Planning in Public Transportation Networks[J].ACTA ELECTRONICA SINICA,2021,49(11):2273-2278. DOI： 10.12263/DZXB.20200436.

摘要

在公交时间表下给定起始和目标站点

路径规划查询返回一组到达时间早和换乘次数少的帕雷托最优路径.现有的索引方法需要大量运行时内存.本文提出主存空间高效的索引方法(a-)PAINT. (a-)PAINT对每个站点

预计算一组标签

使得对于从站点

到站点

的查询可以通过匹配

和

相关的标签高效地生成查询结果的一条路径. 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

a set of labels

such that

for any query from stop

to stop

we can efficiently retrieve a path of the query result from the label sets of

and

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

关键词

Keywords

references

Delling D , Pajor T , Werneck R F . Round-based public transit routing [J]. Transportation Science , 2015 , 49 ( 3 ): 591 - 604 .

Sun X , Wandelt S , Hansen M , et al . Multiple airport regions based on inter-airport temporal distances [J]. Transportation Research Part E: Logistics and Transportation Review , 2017 , 101 : 84 - 98 .

Wang S , Lin W , Yang Y , et al . Efficient route planning on public transportation networks: A labelling approach [A]. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data [C]. ACM , 2015 . 967 - 982 .

Pyrga E , Schulz F , Wagner D , et al . Efficient models for timetable information in public transportation systems [J]. Journal of Experimental Algorithmics (JEA) , 2008 , 12 : 1 - 39 .

Delling D , Dibbelt J , Pajor T , et al . Public transit labeling [A]. International Symposium on Experimental Algorithms [C]. Springer , Cham , 2015 . 273 - 285 .

Bast H , Hertel M , Storandt S . Scalable transfer patterns [A]. Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX) [C]. USA : SIAM , 2016 . 15 - 29 .

Witt S . Trip-based public transit routing . Algorithms-ESA 2015 [M]. Berlin, Heidelberg : Springer , 2015 . 1025 - 1036 .

Witt S . Trip-based public transit routing using condensed search trees [J]. arXiv preprint arXiv: 1607.01299 , 2016 .

Phan D M , Viennot L . Fast public transit routing with unrestricted walking through hub labeling [A]. International Symposium on Experimental Algorithms [C]. Springer , Cham , 2019 . 237 - 247 .

Delling D , Dibbelt J , Pajor T , et al . Faster transit routing by hyper partitioning [A].17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017) [C]. Vienna , 2017 . 8 .

Weng D , Chen R , Zhang J , et al . Pareto-optimal transit route planning with multi-objective Monte-Carlo tree search [J]. IEEE Transactions on Intelligent Transportation Systems , 2020 . 1185 - 1195 .

沈国江 , 杜建波 . 基于非等间隔的两线路公交换乘模型研究 [J]. 浙江工业大学学报 , 2017 , ( 5 ): 587 - 590 .

Bast H , Delling D , Goldberg A , et al . Route planning in transportation networks . Algorithm Engineering [M]. Berlin : Springer , 2016 . 19 - 80 .

Abraham I , Delling D , Goldberg A V , et al . Hierarchical hub labelings for shortest paths [A]. European Symposium on Algorithms [C]. Berlin, Heidelberg : Springer , 2012 . 24 - 35 .

Delling D , Goldberg A V , Pajor T , et al . Robust distance queries on massive networks [A]. European Symposium on Algorithms [C]. Berlin, Heidelberg : Springer , 2014 . 321 - 333 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

一种基于多核机群架构的混合索引结构

基于相容关系的XML索引机制