Exact formulations and algorithm for the train timetabling problem with dynamic demand

Eva Barrena, David Canca, Leandro C. Coelho, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

194 Citations (SciVal)

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 languageEnglish
Pages (from-to)66-74
Number of pages9
JournalComputers and Operations Research
Volume44
DOIs
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'Exact formulations and algorithm for the train timetabling problem with dynamic demand'. Together they form a unique fingerprint.

Cite this