Abstract
In this paper we study the design and optimization of train timetabling adapted to a dynamic demand environment. This problem arises in rapid train services which are common in most important cities. We present three formulations for the problem, with the aim of minimizing passenger average waiting time. The most intuitive model would consider binary variables representing train departure times but it yields to non-linear objective function. Instead, we introduce flow variables, which allow a linear representation of the objective function. We provide incremental improvements on these formulations, which allows us to evaluate and compare the benefits and disadvantages of each modification. We present a branch-and-cut algorithm applicable to all formulations. Through extensive computational experiments on several instances derived from real data provided by the Madrid Metropolitan Railway, we show the advantages of designing a timetable adapted to the demand pattern, as opposed to a regular timetable. We also perform an extensive computational comparison of all linear formulations in terms of size, solution quality and running time.
Original language | English |
---|---|
Pages (from-to) | 66-74 |
Number of pages | 9 |
Journal | Computers and Operations Research |
Volume | 44 |
DOIs | |
Publication status | Published - 1 Jan 2014 |
Funding
We thank the Area Editor and the two anonymous referees for their valuable comments and suggestions. This work was partly supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) under grant 39682-10 , and by the Excellence program of the Andalusian Government, under grant P09-TEP-5022. This support is gratefully acknowledged. We also thank the Calcul Québec for providing parallel computing facilities.
Keywords
- Branch-and-cut
- Dynamic demand
- Exact algorithm
- Regular timetable
- Train timetabling
ASJC Scopus subject areas
- General Computer Science
- Modelling and Simulation
- Management Science and Operations Research