RECIFE-SAT: A MILP-based algorithm for the railway saturation problem

Measuring capacity of railway infrastructures is a 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 of saturating an infrastructure by adding as many trains as possible to an existing (possibly empty) timetable. Specifically, RECIFE-SAT considers a large set of potentially interesting saturation trains and integrates them in the timetable whenever possible. This integration is feasible only when it does not imply the emergence of any conflict with other trains. Thanks to a novel approach to microscopically represent the infrastructure, RECIFE-SAT guarantees the absence of conflicts based on the actual interlocking system deployed in reality. Hence, it can really quantify the actual capacity of the infrastructure considered. The presented version of RECIFE-SAT has two objective functions, namely it maximizes the number of saturation trains scheduled and the number of freight ones. 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.