Memory Efficient Index for Route Planning in Public Transportation Networks

MA Hui; TANG Yong; HE Huai-wen

doi:10.12263/DZXB.20200436

您当前的位置：

首页 >

文章列表页 >

Memory Efficient Index for Route Planning in Public Transportation Networks

CORRESPONDENCE | 更新时间：2025-12-08

- Memory Efficient Index for Route Planning in Public Transportation Networks
- ACTA ELECTRONICA SINICA Vol. 49, Issue 11, Pages: 2273-2278(2021)
- 作者机构：
  
  1.电子科技大学中山学院计算机学院,广东中山528402
  2.华南师范大学计算机学院,广东广州 510631
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20200436
  CLC： TP392
- Received：07 May 2020，
  
  Revised：2021-05-19，
  
  Published：25 November 2021
- 稿件说明：
移动端阅览
马慧,汤庸,何怀文.主存高效的公交网络路径规划索引[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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Hybrid Index Structure Based on Multi-Core Cluster

Containment Based XML Indexing

Related Author

LONG Bai

SUN Guang-zhong

XIONG Yan

CHEN Guo-liang

XU Hai-yuan

WU Quan-yuan

WANG Huai-min

JIA Yan

Related Institution

School of Computer Science and Technology, University of Science and Technology of China

Key Laboratory on High Performance Computing of Anhui Province,, Auhui

School of Computer Science and Technology University of Science and Technology of China Hefei Anhui China

Key Laboratory on High Performance Computing of Anhui Province Hefei Auhui China

School of Computer Science,National University of Defence Technology

⁰