License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-11741
URL:

; ;

04. Solution of the Train Platforming Problem

pdf-format:


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:OASIcs:2007:1174,
  author =	{Alberto Caprara and Laura Galli and Paolo Toth},
  title =	{{04. Solution of the Train Platforming 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/1174},
  URN =		{urn:nbn:de:0030-drops-11741},
  doi =		{http://dx.doi.org/10.4230/OASIcs.ATMOS.2007.1174},
  annote =	{Keywords: Train Platforming, Train Routing, Branch-and-Cut-and-Price,  Quadratic Objective Function, Linearization}
}

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: 2007


DROPS-Home | Fulltext Search | Imprint Published by LZI