The Train-Unit Assignment Problem calls for an optimal assignment of train units (which are self-contained trains with an engine and passenger seats) to a given set of timetabled trips. The goal is to minimize the number of train units globally used, while satisfying the seat requests, the sequencing constraints and the maintenance constraints. We propose an Integer Linear Programming model and a heuristic alcorithm, based on the Lagrangian Relaxation of the model. Computational results on real-world instances show the effectiveness of the proposed algorithm.
A Heuristic Algorithm for the Train-Unit Assignment Problem / V. Cacchiani; A. Caprara; P. Toth. - STAMPA. - (2010), pp. 33-36. (Intervento presentato al convegno 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010) tenutosi a Cologne, Germany nel May 25-27, 2010).
A Heuristic Algorithm for the Train-Unit Assignment Problem
CACCHIANI, VALENTINA;CAPRARA, ALBERTO;TOTH, PAOLO
2010
Abstract
The Train-Unit Assignment Problem calls for an optimal assignment of train units (which are self-contained trains with an engine and passenger seats) to a given set of timetabled trips. The goal is to minimize the number of train units globally used, while satisfying the seat requests, the sequencing constraints and the maintenance constraints. We propose an Integer Linear Programming model and a heuristic alcorithm, based on the Lagrangian Relaxation of the model. Computational results on real-world instances show the effectiveness of the proposed algorithm.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
