License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2013.55
URN: urn:nbn:de:0030-drops-42448
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4244/
Go to the corresponding OASIcs Volume Portal

Sadykov, Ruslan ; Lazarev, Alexander A. ; Shiryaev, Vitaliy ; Stratonnikov, Alexey

Solving a Freight Railcar Flow Problem Arising in Russia

pdf-format:
6.pdf (0.5 MB)

Abstract

We consider a variant of the freight railcar flow problem. In this
problem, we need 1) to choose 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.

BibTeX - Entry

@InProceedings{sadykov_et_al:OASIcs:2013:4244,
  author =	{Ruslan Sadykov and Alexander A. Lazarev and Vitaliy Shiryaev and Alexey Stratonnikov},
  title =	{{Solving a Freight Railcar Flow Problem Arising in Russia}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{55--67},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Daniele Frigioni and Sebastian Stiller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4244},
  URN =		{urn:nbn:de:0030-drops-42448},
  doi =		{10.4230/OASIcs.ATMOS.2013.55},
  annote =	{Keywords: Freight routing, multi-commodity flow, column generation}
}

Keywords: Freight routing, multi-commodity flow, column generation
Collection: 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue Date: 2013
Date of publication: 05.09.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI