TY - JOUR

T1 - The train frequency compatibility problem

AU - Cerdeira, Jorge Orestes

AU - Iglésias, Carlos

AU - Silva, Pedro C.

N1 - info:eu-repo/grantAgreement/FCT/5876/147204/PT#
UID/AGR/002389/2013.
We are grateful to Ricardo Saldanha and Susana Branclao from SISCOG, for discussions and computational assistance.

PY - 2019/9/30

Y1 - 2019/9/30

N2 - 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|naj+δj−(mai+δi)|, 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.

AB - 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|naj+δj−(mai+δi)|, 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.

KW - Computational complexity

KW - Mixed integer linear programming

KW - Optimization

UR - http://www.scopus.com/inward/record.url?scp=85057073964&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2018.10.046

DO - 10.1016/j.dam.2018.10.046

M3 - Article

AN - SCOPUS:85057073964

SN - 0166-218X

VL - 269

SP - 18

EP - 26

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - SI

ER -