We present a fast heuristic for an important NP-hard problem, arising in the planning of a railway passenger system, that calls for the definition of the train units to be assigned to a given set of timetabled trips, each with a given number of passenger seats requested. The heuristic is based on the Lagrangian relaxation of a natural formulation of the problem, whose solution can be found by solving a sequence of assignment problems. With respect to an already existing method, the heuristic we propose turns out to be much faster in practice and still providing solutions of good quality. This makes it suitable for all cases in which the problem either must be solved many times, e.g., when it is integrated with other phases of railway planning, or when it must be solved within short computing time, e.g., within real-time operations.

A Lagrangian Heuristic for a Train-Unit Assignment Problem

CACCHIANI, VALENTINA;CAPRARA, ALBERTO;TOTH, PAOLO
2013

Abstract

We present a fast heuristic for an important NP-hard problem, arising in the planning of a railway passenger system, that calls for the definition of the train units to be assigned to a given set of timetabled trips, each with a given number of passenger seats requested. The heuristic is based on the Lagrangian relaxation of a natural formulation of the problem, whose solution can be found by solving a sequence of assignment problems. With respect to an already existing method, the heuristic we propose turns out to be much faster in practice and still providing solutions of good quality. This makes it suitable for all cases in which the problem either must be solved many times, e.g., when it is integrated with other phases of railway planning, or when it must be solved within short computing time, e.g., within real-time operations.
DISCRETE APPLIED MATHEMATICS
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/113183
 Attenzione

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

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