×

Flexible train rostering. (English) Zbl 1205.90120

Ibaraki, Toshihide (ed.) et al., Algorithms and computation. 14th international symposium, ISAAC 2003, Kyoto, Japan, December 15–17, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20695-7/pbk). Lect. Notes Comput. Sci. 2906, 615-624 (2003).
Summary: Determining cost-effective vehicle scheduling is an important optimization issue in mass transportation networks. An interesting question in this context is whether allowing certain flexibility in the departure times of scheduled routes may reduce the number of vehicles needed. We formulate this question as the Flexible Train Rostering problem. (Our motivation comes from railway optimization problems. However, our results apply to other mass transportation media as well.) We consider two cases that are of practical interest:
– Unlimited flexibility: only the durations of routes are given and we are free to determine the most appropriate departure time for each route.
– Limited flexibility: initial departure times are given, together with a delay threshold \(\varepsilon \); we are asked to determine the most appropriate delay \(\leq \varepsilon \) for each route.
We also consider variants where we are allowed to use empty rides, (i.e., routes without passengers). We present a variety of results for these problems: polynomial-time algorithms that optimally solve some of them, NP- and APX-hardness proofs for others, as well as approximation algorithms for most of the hard problems.
For the entire collection see [Zbl 1029.00053].

MSC:

90B35 Deterministic scheduling theory in operations research
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI