# A Lagrangian heuristic for a real-life integrated planning problem of railway transportation resources

1 SFL-ENSMSE - Département Sciences de la Fabrication et Logistique 2 SNCF - DIR - Direction Innovation & Recherche

Abstract : Railway planning requires three scarce and heterogeneous resources: train paths infrastructure, rolling stock and train drivers. In the current industrial approach at SNCF French National Railway Company, these resources are essentially planned through a sequential approach which typically starts from 1 train paths and goes further on to 2 rolling stock and finally 3 train drivers. SNCF has already developed optimization tools for Steps 2 and 3. In this paper, we built upon the work previously presented at IAROR-RAILROME 2011. We presented a mixed integer linear programming model with coupling constraints for a simplified integrated problem of railway production resources. We also proposed a Lagrangian relaxation heuristic. In this approach, sub-problems were solved thanks to a standard mathematical programming solver. First numerical experiments were conducted on a reduced data set, extracted from an actual instance from a French region Bretagne. The results obtained were promising but showed that the resolution with a standard solver was too costly in terms of computational times for real-world instances and that the model had to be improved for implementation in a Lagrangian relaxation framework. Since 2011, the mathematical model has been improved and numerous operational constraints have been integrated in order to tackle real-life integrated planning problems at SNCF. The Lagrangian relaxation heuristic has been updated consequently. As already mentioned, SNCF has already developed two independent optimization tools for planning rolling stock and train drivers. The Lagrangian approach has also been adapted so that the resulting sub-problems of this mathematical decomposition method can now be solved with the two dedicated tools. We thus can now address real-life instances and solve each sub-problem of the specific Lagrangian heuristic with proprietary software. Preliminary computational results show the interest of our method. Compared to a sequential approach, the Lagrangian heuristic leads to substantial cost reductions and generates good solutions in a reasonable CPU time. This is thus an interesting tool for human planners who want to experiment and quantitatively evaluate different scenarios e.g. other train-path distribution, specific rolling stock, train drivers with other capabilities

Keywords : Railway transportation integrated planning mixed integer programming Lagrangian heuristic

Author: Faten Benhizia - Stéphane Dauzère-Pérès - David De Almeida - Olivier Guyon -

Source: https://hal.archives-ouvertes.fr/