DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2013.55

Solving a Freight Railcar Flow Problem Arising in Russia

Authors: Ruslan Sadykov, Alexander A. Lazarev, Vitaliy Shiryaev, and Alexey Stratonnikov

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

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.

Cite as

Ruslan Sadykov, Alexander A. Lazarev, Vitaliy Shiryaev, and Alexey Stratonnikov. Solving a Freight Railcar Flow Problem Arising in Russia. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 55-67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{sadykov_et_al:OASIcs.ATMOS.2013.55,
  author =	{Sadykov, Ruslan and Lazarev, Alexander A. and Shiryaev, Vitaliy and Stratonnikov, Alexey},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.55},
  URN =		{urn:nbn:de:0030-drops-42448},
  doi =		{10.4230/OASIcs.ATMOS.2013.55},
  annote =	{Keywords: Freight routing, multi-commodity flow, column generation}
}

Search Results

Documents authored by Shiryaev, Vitaliy

Solving a Freight Railcar Flow Problem Arising in Russia

Abstract

Cite as

Thanks for your feedback!

Could not send message