We consider the customary formulation of non-cyclic train timetabling, calling for a maximum-profit collection of compatible paths in a suitable acyclic network. The associated ILP models look for a maximum-weight clique in a(n exponentially-large) compatibility graph. By taking a close look at the structure of this graph, we analyze the existing ILP models and propose some new stronger ones, all having the essential property that both separation and column generation can be carried out efficiently. Computational results show that the LP relaxations of the new formulations can lead to much stronger upper bounds on highly-congested instances.

V. Cacchiani, A. Caprara, P. Toth (2009). Non-cyclic Train Timetabling and Comparability Graphs. PISA : s.n.

Non-cyclic Train Timetabling and Comparability Graphs

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

Abstract

We consider the customary formulation of non-cyclic train timetabling, calling for a maximum-profit collection of compatible paths in a suitable acyclic network. The associated ILP models look for a maximum-weight clique in a(n exponentially-large) compatibility graph. By taking a close look at the structure of this graph, we analyze the existing ILP models and propose some new stronger ones, all having the essential property that both separation and column generation can be carried out efficiently. Computational results show that the LP relaxations of the new formulations can lead to much stronger upper bounds on highly-congested instances.
2009
Proceedings of the International Network Optimization Conference 2009 (INOC 2009)
1
7
V. Cacchiani, A. Caprara, P. Toth (2009). Non-cyclic Train Timetabling and Comparability Graphs. PISA : s.n.
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: https://hdl.handle.net/11585/73029
 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