A Lagrangian heuristic for a real-life integrated planning problem of railway transportation resources - Mines Saint-Étienne Access content directly
Conference Papers Year : 2013

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


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...).
Fichier principal
Vignette du fichier
IAROR_-_RailCopenhagen2013_-_article.pdf (226.99 Ko) Télécharger le fichier
IAROR_-_RailCopenhagen2013_-_slides.pdf (257.88 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Other

Dates and versions

emse-00823169 , version 1 (16-05-2013)


  • HAL Id : emse-00823169 , version 1


Faten Benhizia, Stéphane Dauzère-Pérès, David de Almeida, Olivier Guyon. A Lagrangian heuristic for a real-life integrated planning problem of railway transportation resources. 5th International Seminar on Railway Operations Modelling and Analysis - RailCopenhagen, May 2013, Copenhagen, Denmark. 13p. ⟨emse-00823169⟩
262 View
421 Download


Gmail Facebook X LinkedIn More