A three-step Benders decomposition for the real-time Railway Traffic Management Problem

In railway systems, during congested traffic situations, the infrastructure capacity is completely exploited for trains circulation. When traffic is perturbed, some trains must be stopped or slowed down for ensuring safety, and delays occur. The real-time Railway Traffic Management Problem (rtRTMP) is the problem of modifying trains route and schedule to limit delay propagation. In this paper, we propose an approach based on Benders decomposition of a MILP-based algorithm for this problem, named RECIFE-MILP. Specifically, we split the solution process in three steps rather than two as in the standard decomposition. As we show in a thorough experimental analysis, this decomposition of the solution process into three steps can outperform the original RECIFE-MILP algorithm when tackling large instances with some specific features.