Single-line rail rapid transit timetabling under dynamic passenger demand

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

Research output: Contribution to journalArticlepeer-review

93 Citations (Scopus)

Abstract

Railway planning is a complex activity which is usually decomposed into several stages, traditionally network design, line design, timetabling, rolling stock, and staffing. In this paper, we study the design and optimization of train timetables for a rail rapid transit (RRT) line adapted to a dynamic demand environment, which focuses on creating convenient timetables for passengers. The objective is to minimize the average passenger waiting time at the stations, thus focusing on passenger welfare. We first propose two mathematical programming formulations which generalize the non-periodic train timetabling problem on a single line under a dynamic demand pattern. We then analyze the properties of the problem before introducing a fast adaptive large neighborhood search (ALNS) metaheuristic in order to solve large instances of the problem within short computation times. The algorithm yields timetables that may not be regular or periodic, but are adjusted to a dynamic demand behavior. Through extensive computational experiments on artificial and real-world based instances, we demonstrate the computational superiority of our ALNS compared with a truncated branch-and-cut algorithm. The average reduction in passenger waiting times is 26%, while the computational time of our metaheuristic is less than 1% of that required by the alternative CPLEX-based algorithm. Out of 120 open instances, we obtain 84 new best known solutions and we reach the optimum on 10 out of 14 instances with known optimal solutions.

Original languageEnglish
Pages (from-to)134-150
Number of pages17
JournalTransportation Research Part B: Methodological
Volume70
DOIs
Publication statusPublished - 1 Dec 2014

Keywords

  • Adaptive large neighborhood search metaheuristic
  • Demand-based timetable
  • Passenger welfare
  • Rail rapid transit

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Fingerprint Dive into the research topics of 'Single-line rail rapid transit timetabling under dynamic passenger demand'. Together they form a unique fingerprint.

Cite this