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. We consider two cases thai 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 ε; we are asked to determine the most appropriate delay ≤ ε 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.
展开▼
