Frequency-based search for public transit

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BAST, Hannah, Sabine STORANDT, 2014. Frequency-based search for public transit. The 22nd ACM SIGSPATIAL International Conference (SIGSPATIAL '14). Dallas, Texas, Nov 4, 2014 - Nov 7, 2014. In: HUANG, Yan, ed.. Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, NY:ACM Press, pp. 13-22. ISBN 978-1-4503-3131-9. Available under: doi: 10.1145/2666310.2666405

@inproceedings{Bast2014Frequ-45910, title={Frequency-based search for public transit}, year={2014}, doi={10.1145/2666310.2666405}, isbn={978-1-4503-3131-9}, address={New York, NY}, publisher={ACM Press}, booktitle={Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems}, pages={13--22}, editor={Huang, Yan}, author={Bast, Hannah and Storandt, Sabine} }

We consider the application of route planning in large public-transportation networks (buses, trains, subways, etc). Many connections in such networks are operated at periodic time intervals. When a set of connections has sufficient periodicity, it becomes more efficient to store the time range and frequency (e.g., every 15 minutes from 8:00am-6:00pm) instead of storing each of the time events separately. Identifying an optimal frequency-compression is NP-hard, so we present a time- and space-efficient heuristic.<br /><br />We show how we can use this compression to not only save space but also query time. We particularly consider profile queries, which ask for all optimal routes with departure times in a given interval (e.g., a whole day). In particular, we design a new version of Dijkstra's algorithm that works with frequency-based labels and is suitable for profile queries. We evaluate the savings of our approach on two metropolitan and three country-wide public-transportation networks. On our largest network, we simultaneously achieve a better space consumption than all previous methods as well as profile query times that are about 5 times faster than the best previous method. We also improve Transfer Patterns, a state-of-the-art technique for fully realistic route planning in large public-transportation networks. In particular, we accelerate the expensive preprocessing by a factor of 60 compared to the original publication. Storandt, Sabine Bast, Hannah eng 2014 2019-05-24T09:45:31Z Frequency-based search for public transit 2019-05-24T09:45:31Z Bast, Hannah Storandt, Sabine

This item appears in the following Collection(s)

Search KOPS


Browse

My Account