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

Cacchiani, Valentina ; Caprara, Alberto ; Toth, Paolo

06. Solving a Real-World Train Unit Assignment Problem

pdf-format:
07001.CacchianiValentina.Paper.1172.pdf (0.2 MB)

Abstract

We face a real-world train unit assignment problem for an
operator running trains in a regional area. 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 an assignment of the train units to trips, possibly combining
more than one train unit for a given trip, that fulfills the seat requests.
With respect to analogous case studies previously faced in the literature,
ours is characterized by the fairly large number of distinct train unit
types available (in addition to the fairly large number of trips to be
covered). As a result, although there is a wide margin of improvement
over the solution used by the practitioners (as our results show), even
only finding a solution of the same value is challenging in practice. We
present a successful approach, based on an ILP formulation in which
the seat requirement constraints are stated in a “strong” form, derived
from the description of the convex hull of the variant of the knapsack
polytope arising when the sum of the variables is restricted not to exceed
two, illustrating computational results on our case study.

BibTeX - Entry

@InProceedings{cacchiani_et_al:OASIcs:2007:1172,
  author =	{Valentina Cacchiani and Alberto Caprara and Paolo Toth},
  title =	{{06. Solving a Real-World Train Unit Assignment Problem}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Christian Liebchen and Ravindra K. Ahuja and Juan A. Mesa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2007/1172},
  URN =		{urn:nbn:de:0030-drops-11726},
  doi =		{10.4230/OASIcs.ATMOS.2007.1172},
  annote =	{Keywords: }
}

Collection: 7th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'07)
Issue Date: 2007
Date of publication: 06.11.2007

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