We consider the customary formulation of non-cyclic train timetabling, calling for a maximum-profit collection of compatible paths in a suitable graph. 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, propose some new stronger ones, all having the essential property that both separation and column generation can be carried out efficiently, and report computational results on highly-congested instances.
Non-cyclic Train Timetabling and Comparability Graphs / V. Cacchiani; A. Caprara; P. Toth. - In: OPERATIONS RESEARCH LETTERS. - ISSN 0167-6377. - STAMPA. - 38:(2010), pp. 179-184. [10.1016/j.orl.2010.01.007]
Non-cyclic Train Timetabling and Comparability Graphs
CACCHIANI, VALENTINA;CAPRARA, ALBERTO;TOTH, PAOLO
2010
Abstract
We consider the customary formulation of non-cyclic train timetabling, calling for a maximum-profit collection of compatible paths in a suitable graph. 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, propose some new stronger ones, all having the essential property that both separation and column generation can be carried out efficiently, and report computational results on highly-congested instances.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
