Non-cyclic train timetabling and comparability graphs

被引：43

作者：

Cacchiani, Valentina ^{[1
]}

Caprara, Alberto ^{[1
]}

Toth, Paolo ^{[1
]}

机构：

[1] Univ Bologna, DEIS, I-40136 Bologna, Italy

来源：

OPERATIONS RESEARCH LETTERS | 2010年 / 38卷 / 03期

关键词：

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

D O I：

10.1016/j.orl.2010.01.007

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：179 / 184

页数：6

共 9 条

[1] Railway timetabling using Lagrangian relaxation [J].