
Open access
Date
2004Type
- Report
ETH Bibliography
yes
Altmetrics
Abstract
Delay management for public transport consists of deciding whether vehicles should wait for delayed transferring passengers, with the objective of minimizing the overall passenger discomfort. We model the underlying transportation network as a directed acyclic graph, where edges represent trains, and weighted paths represent passenger flows. Given initial delays of some of the passenger paths, our goal is to decide which edges wait for delayed passenger paths, such that the sum of all passenger delays is minimized. This paper classifies the computational complexity of delay management problems with respect to various structural parameters, such as the maximum number of passenger transfers, the graph topology, and the capability of edges to reduce delays. Our focus is to distinguish between polynomially solvable and NP-complete problem variants. To that end, we show that even fairly restricted versions of the delay management problem are hard to solve. Show more
Permanent link
https://doi.org/10.3929/ethz-a-006759907Publication status
publishedJournal / series
Technical reportVolume
Publisher
ETH, Department of Computer ScienceSubject
COMPLEXITY CLASSES (THEORETICAL COMPUTER SCIENCE); COMPUTER APPLICATIONS IN TRAFFIC AND TRANSPORTATION; COMPUTERANWENDUNGEN IN VERKEHR UND TRANSPORT; KOMPLEXITÄTSKLASSEN (THEORETISCHE INFORMATIK)Organisational unit
02150 - Dep. Informatik / Dep. of Computer Science
More
Show all metadata
ETH Bibliography
yes
Altmetrics