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

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...).
Type de document :
Communication dans un congrès
5th International Seminar on Railway Operations Modelling and Analysis - RailCopenhagen, May 2013, Copenhagen, Denmark. 13p., 2013
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00823169
Contributeur : Olivier Guyon <>
Soumis le : jeudi 16 mai 2013 - 18:07:23
Dernière modification le : mercredi 29 novembre 2017 - 10:06:23
Document(s) archivé(s) le : samedi 17 août 2013 - 04:14:50

Identifiants

  • HAL Id : emse-00823169, version 1

Collections

Citation

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., 2013. 〈emse-00823169〉

Partager

Métriques

Consultations de la notice

332

Téléchargements de fichiers

409