04. Solution of the Train Platforming Problem

Caprara, Alberto; Galli, Laura; Toth, Paolo

doi:10.4230/OASIcs.ATMOS.2007.1174

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.1174
URN: urn:nbn:de:0030-drops-11741
URL: https://drops.dagstuhl.de/opus/volltexte/2007/1174/

Caprara, Alberto ; Galli, Laura ; Toth, Paolo

04. Solution of the Train Platforming Problem

pdf-format:

07001.CapraraAlberto.Paper.1174.pdf (0.2 MB)

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 =		{10.4230/OASIcs.ATMOS.2007.1174},
  annote =	{Keywords: Train Platforming, Train Routing, Branch-and-Cut-and-Price,  Quadratic Objective Function, Linearization}
}

06.11.2007

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

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