Frequency-based search for public transit

Bast, Hannah; Storandt, Sabine

Frequency-based search for public transit

Files

There are no files associated with this item.

Date

2014

Authors

Bast, Hannah

Storandt, Sabine

DOI (citable link)

10.1145/2666310.2666405

Collections

Informatik und Informationswissenschaft

Publication type

Contribution to a conference collection

Publication status

Published

Published in

Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems / Huang, Yan (ed.). - New York, NY : ACM Press, 2014. - pp. 13-22. - ISBN 978-1-4503-3131-9

Abstract

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.

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.

Subject (DDC)

004 Computer Science

Conference

The 22nd ACM SIGSPATIAL International Conference (SIGSPATIAL '14), Nov 4, 2014 - Nov 7, 2014, Dallas, Texas

Cite This

ISO 690

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

BibTex

@inproceedings{Bast2014Frequ-45910,
  year={2014},
  doi={10.1145/2666310.2666405},
  title={Frequency-based search for public transit},
  isbn={978-1-4503-3131-9},
  publisher={ACM Press},
  address={New York, NY},
  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}
}

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/45910">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:language>eng</dc:language>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-05-24T09:45:31Z</dc:date>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dc:creator>Bast, Hannah</dc:creator>
    <dc:contributor>Bast, Hannah</dc:contributor>
    <dcterms:issued>2014</dcterms:issued>
    <dcterms:abstract xml:lang="eng">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.&lt;br /&gt;&lt;br /&gt;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.</dcterms:abstract>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dcterms:title>Frequency-based search for public transit</dcterms:title>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/45910"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-05-24T09:45:31Z</dcterms:available>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
  </rdf:Description>
</rdf:RDF>

Bibliography of Konstanz

No