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

Cacchiani, Valentina ; Caprara, Alberto ; Toth, Paolo

A Fast Heuristic Algorithm for the Train Unit Assignment Problem

pdf-format:
3.pdf (0.3 MB)

Abstract

In this paper we study a railway optimization problem known as the Train Unit Assignment Problem. A train unit consists of a self-contained train with an engine and a set of wagons with passenger seats. Given a set of timetabled train trips, each with a required number of passenger seats, and a set of train units, each with a given number of available seats, the problem calls for the best assignment of the train units to the trips, possibly combining more than one train unit for a given trip, that fulfills the seat requests. We propose a heuristic algorithm based on the computation of a lower bound obtained by solving an Integer Linear Programming model that gives the optimal solution in a "peak period" of the day. The performance of the heuristic algorithm is computationally evaluated on real-world instances provided by a regional Italian Train Operator. The results are compared with those of existing methods from the literature, showing that the new method is able to obtain solutions of good quality in much shorter computing times.

BibTeX - Entry

@InProceedings{cacchiani_et_al:OASIcs:2012:3697,
  author =	{Valentina Cacchiani and Alberto Caprara and Paolo Toth},
  title =	{{A Fast Heuristic Algorithm for the Train Unit Assignment Problem}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{1--9},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Daniel Delling and Leo Liberti},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3697},
  URN =		{urn:nbn:de:0030-drops-36971},
  doi =		{10.4230/OASIcs.ATMOS.2012.1},
  annote =	{Keywords: Train Unit Assignment, Heuristic Algorithm, ILP model, Real-world instances}
}

Keywords: Train Unit Assignment, Heuristic Algorithm, ILP model, Real-world instances
Collection: 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue Date: 2012
Date of publication: 13.09.2012

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