2026-08-17T05:10:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1174 2024-03-06T10:28:28Z ddc:004 open_access

04. Solution of the Train Platforming Problem Caprara, Alberto Galli, Laura Toth, Paolo Train Platforming Train Routing Branch-and-Cut-and-Price Quadratic Objective Function Linearization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alberto Caprara and Laura Galli and Paolo Toth 2007 Is Part Of OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2007.1174 urn:nbn:de:0030-drops-11741 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1174 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode