RECIFE-SAT: a MILP-based algorithm for saturating railway timetables

Measuring capacity of railway infrastructures is an open problem even in its definition. In this paper, we propose RECIFE-SAT, a MILP-based algorithm to quantify capacity by solving the saturation problem. This problem consists in saturating an infrastructure by adding as many trains as possible to an existing (possibly empty) timetable. In an experimental analysis performed in collaboration with the French infrastructure manager, we show the promising performance of RECIFE-SAT. To the best of our knowledge, RECIFE-SAT is the first algorithm which is shown to be capable of saturating rather large railway networks considering a microscopic infrastructure representation. This representation allows RECIFE-SAT to really quantify the actual capacity of the infrastructure considered.