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

89 Citations (Scopus)

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

Keywords

  • Branch-and-cut
  • Dynamic demand
  • Exact algorithm
  • Regular timetable
  • Train timetabling

ASJC Scopus subject areas

  • Computer Science(all)
  • 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