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

181 Citations (SciVal)


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
Publication statusPublished - 1 Jan 2014


  • 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


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