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.2016.6
URN: urn:nbn:de:0030-drops-65302
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6530/
Go to the corresponding OASIcs Volume Portal

Jaumard, Brigitte ; Tian, Huaining

Multi-Column Generation Model for the Locomotive Assignment Problem

pdf-format:
OASIcs-ATMOS-2016-6.pdf (0.9 MB)

Abstract

We propose a new decomposition model and a multi-column generation algorithm for solving the Locomotive Assignment Problem (LAP). The decomposition scheme relies on consist configurations, where each configuration is made of a set of trains pulled by the same set of locomotives. We use the concept of conflict graphs in order to reduce the number of trains to be considered in each consist configuration generator problem: this contributes to significantly reduce the fraction of the computational times spent in generating new potential consists. In addition, we define a column generation problem for each set of variables, leading to a multi-column generation process, with different types of columns.

Numerical results, with different numbers of locomotives, are presented on adapted data sets coming from Canada Pacific Railway (CPR). They show that the newly proposed algorithm is able to solve exactly realistic data instances for a timeline spanning up to 6 weeks, in very reasonable computational times.

BibTeX - Entry

@InProceedings{jaumard_et_al:OASIcs:2016:6530,
  author =	{Brigitte Jaumard and Huaining Tian},
  title =	{{Multi-Column Generation Model for the Locomotive Assignment Problem}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{6:1--6:13},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Marc Goerigk and Renato Werneck},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6530},
  URN =		{urn:nbn:de:0030-drops-65302},
  doi =		{10.4230/OASIcs.ATMOS.2016.6},
  annote =	{Keywords: Railway optimization, Locomotive assignment, Column Generation}
}

Keywords: Railway optimization, Locomotive assignment, Column Generation
Collection: 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)
Issue Date: 2016
Date of publication: 24.08.2016

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