Non-cyclic train timetabling and comparability graphs

作者：Cacchiani Valentina; Caprara Alberto^*; Toth Paolo

来源：Operations Research Letters, 2010, 38(3): 179-184.

DOI：10.1016/j.orl.2010.01.007

• Train timetabling
• Comparability graph
• Stable set
• ILP formulations
• Clique inequalities
• Computational results

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 I LP models, propose some new stronger ones, all having the essential property that both the separation and the column generation can be carried out efficiently, and report the computational results on highly-congested instances.

• 出版日期2010-5