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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1174/
Caprara, Alberto ;
Galli, Laura ;
Toth, Paolo
04. Solution of the Train Platforming Problem
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}
}
Keywords: |
|
Train Platforming, Train Routing, Branch-and-Cut-and-Price, Quadratic Objective Function, Linearization |
Collection: |
|
7th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'07) |
Issue Date: |
|
2007 |
Date of publication: |
|
06.11.2007 |