The train frequency compatibility problem

Jorge Orestes Cerdeira, Carlos Iglésias, Pedro C. Silva

Research output: Contribution to journalArticle

Abstract

How should trains that arrive at a railway station in constant intervals be scheduled so that the safety interval between two trains is maximum? This is a timetabling problem which we call the train frequency compatibility (TFC) problem that can be mathematically stated as follows. Given a collection A of N (possible repeated) positive integers ai (the train frequencies), find δi≥0 (the starting time of the periodic trip i), for i=1,…,N, such that z=min|najj−(maii)|, with i,j=1,…,N,i≠j and m,n∈N0, is maximum. We present Mixed Integer Linear Programming (MILP) formulations for the problem, describe a procedure to obtain bounds on maximum z, and report computational results. We also consider a restricted version of the TFC which yields more realistic solutions regarding the train scheduling applications. For the restricted version we give a formulation based on matchings in bipartite graphs, compare the computational performance of this formulation with the MILP model, and prove that the problem is NP-hard.

Original languageEnglish
Pages (from-to)18-26
Number of pages9
JournalDiscrete Applied Mathematics
Volume269
Issue numberSI
DOIs
Publication statusPublished - 30 Sep 2019

Keywords

  • Computational complexity
  • Mixed integer linear programming
  • Optimization

Fingerprint Dive into the research topics of 'The train frequency compatibility problem'. Together they form a unique fingerprint.

Cite this