Solving a Freight Railcar Flow Problem Arising in Russia

Ruslan Sadykov 1 Alexander Lazarev 2 Vitaliy Shiryaev 3 Alexey Stratonnikov 3
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : We consider a variant of the freight railcar flow problem. In this problem, we need 1) to chose a set of transportation demands between stations in a railroad network, and 2) to fulfill these demands by appropriately routing the set of available railcars, while maximizing the total profit. We formulate this problem as a multi-commodity flow problem in a large space-time graph. Three approaches are proposed to solve the Linear Programming relaxation of this formulation: direct solution by an LP solver, a column generation approach based on the path reformulation, and a "column generation for extended formulations" approach. In the latter, the multi-commodity flow formulation is solved iteratively by dynamic generation of arc flow variables. Three approaches have been tested on a set of real-life instances provided by one of the largest freight rail transportation companies in Russia. Instances with up to 10 millions of arc flow variables were solved within minutes of computational time.
Type de document :
Communication dans un congrès
ATMOS - 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - 2013, Sep 2013, Sophia Antipolis, France. Dagstuhl Open Access Series in Informatics, 2013, to appear. 〈http://drops.dagstuhl.de/opus/volltexte/2013/4244〉. 〈10.4230/OASIcs.ATMOS.2013.55〉
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00857914
Contributeur : Ruslan Sadykov <>
Soumis le : jeudi 10 octobre 2013 - 15:31:55
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : jeudi 6 avril 2017 - 15:17:18

Fichier

Solving_a_freight.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Ruslan Sadykov, Alexander Lazarev, Vitaliy Shiryaev, Alexey Stratonnikov. Solving a Freight Railcar Flow Problem Arising in Russia. ATMOS - 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - 2013, Sep 2013, Sophia Antipolis, France. Dagstuhl Open Access Series in Informatics, 2013, to appear. 〈http://drops.dagstuhl.de/opus/volltexte/2013/4244〉. 〈10.4230/OASIcs.ATMOS.2013.55〉. 〈hal-00857914〉

Partager

Métriques

Consultations de la notice

518

Téléchargements de fichiers

171