Fast and Exact Public Transit Routing with Restricted Pareto Sets

Daniel Delling · Julian Dibbelt · Thomas Pajor

20 citations0/0 files storedSociety for Industrial and Applied Mathematics eBooks

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Transportation Planning and Optimization Complexity and Algorithms in Graphs Urban Transport and Accessibility

Abstract

We present a novel exact journey planning approach to computing a reasonable subset of multi-criteria Pareto sets in public transit networks. Our restriction is well defined and independent of the choice of algorithm. In order to compute the restricted Pareto set efficiently, we present Bounded McRAPTOR, a new set of algorithms that extend the well-known McRAPTOR algorithm. The fastest variant employs a novel pruning scheme based on carefully computed bounds. Experiments on large metropolitan networks show that a four-criteria restricted Pareto set can be computed faster by a factor of up to 65, while retaining the important journeys of the full Pareto set. This easily enables interactive applications in practice, making multi-criteria Pareto-optimal journey planning scalable without the need of a preprocessing-based speedup technique.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 20 citations exist upstream.

References

2016Route Planning in Transportation Networks 2007Efficient models for timetable information in public transportation systems 2014Round-Based Public Transit Routing 2010Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns 2013Computing Multimodal Journeys in Practice 2018Connection Scan Algorithm 2015Trip-Based Public Transit Routing 2015Public Transit Labeling

Cited by

2021A Joint Passenger Flow Inference and Path Recommender System for Deploying New Routes and Stations of Mass Transit Transportation 2020A Goal-Prioritized Algorithm for Additional Route Deployment on Existing Mass Transportation System 2022Multicriteria Route Planning for In-Operation Mass Transit under Urban Data

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.