License
when quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2007.1174
URN: urn:nbn:de:0030-drops-11741
URL: http://drops.dagstuhl.de/opus/volltexte/2007/1174/
Caprara, Alberto ; Galli, Laura ; Toth, Paolo

04. Solution of the Train Platforming Problem

pdf-format:
Dokument 1.pdf (195 KB)

Abstract

In this paper we study a general formulation of the train platforming problem, which contains as special cases all the versions previously considered in the literature as well as a case study from the Italian Infrastructure manager that we addressed. In particular, motivated by our case study, we consider a general quadratic objective function, and propose a new way to linearize it by using a small number of new variables along with a set of constraints that can be separated efficiently by solving an appropriate linear program. The resulting integer linear programming formulation has a continuous relaxation that leads to strong bounds on the optimal value. For the instances in our case study, we show that a simple diving heuristic based on this relaxation produces solutions that are much better than those produced by a simple heuristic currently in use, and that often turn out to be (nearly-) optimal.

BibTeX - Entry

@InProceedings{caprara_et_al:DSP:2007:1174,
  author =	{Alberto Caprara and Laura Galli and Paolo Toth},
  title =	{04. Solution of the Train Platforming Problem},
  booktitle =	{ATMOS 2007 - 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems},
  year =	{2007},
  editor =	{Christian Liebchen and Ravindra K. Ahuja and Juan A. Mesa},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2007/1174},
  annote =	{Keywords: Train Platforming, Train Routing, Branch-and-Cut-and-Price,  Quadratic Objective Function, Linearization},
  ISBN =	{978-3-939897-04-0}
}

Keywords: Train Platforming, Train Routing, Branch-and-Cut-and-Price, Quadratic Objective Function, Linearization
Seminar: 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 Published by LZI