文章基本信息

标题：Faster Transit Routing by Hyper Partitioning
本地全文：下载
作者：Daniel Delling ; Julian Dibbelt ; Thomas Pajor 等
期刊名称：OASIcs : OpenAccess Series in Informatics
电子版ISSN：2190-6807
出版年度：2017
卷号：59
页码：1-14
DOI：10.4230/OASIcs.ATMOS.2017.8
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We present a preprocessing-based acceleration technique for computing bi-criteria Pareto-optimal journeys in public transit networks, based on the well-known RAPTOR algorithm [Delling et al 2015]. Our key idea is to first partition a hypergraph into cells, in which vertices correspond to routes (e.g., bus lines) and hyperedges to stops, and to then mark routes sufficient for optimal travel across cells. The query can then be restricted to marked routes and those in the source and target cells. This results in a practical approach, suitable for networks that are too large to be efficiently handled by the basic RAPTOR algorithm.
关键词：Routing; speed-up techniques; public transport; partitioning