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

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.
Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010)
33
36
V. Cacchiani; A. Caprara; P. Toth
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/100050
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact