A branch-and-cut approach for solving railway line-planning problems

被引:93
作者
Goossens, JW
van Hoesel, S
Kroon, L
机构
[1] Univ Maastricht, Dept Quantitat Econ, NL-6200 MD Maastricht, Netherlands
[2] Erasmus Univ, Sch Management, NL-3000 DR Rotterdam, Netherlands
关键词
rail transportation; integer programming; branch and cut; combinatorial optimization;
D O I
10.1287/trsc.1030.0051
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
An important strategic phase in the planning process of a railway operator is the development of a line plan, i.e., a set of routes (paths) in a network of tracks, operated at a given hourly frequency. We consider a model formulation of the line-planning problem where total operating costs are to be minimized. This model is solved with a branch-and-cut approach, for which we develop a variety of valid inequalities and reduction methods. A computational study of five real-life instances based on examples from Netherlands Railways (NS) is included.
引用
收藏
页码:379 / 393
页数:15
相关论文
共 20 条
[1]  
*ABACUS, 1998, ABACUS BRANCH AND CU
[2]  
[Anonymous], THESIS TU BRAUNSCHWE
[3]  
Bussieck M, 1998, THESIS U BRAUNSCHWEI
[4]   Optimal lines for railway systems [J].
Bussieck, MR ;
Kreuzer, P ;
Zimmermann, UT .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1997, 96 (01) :54-63
[5]  
BUSSIECK MR, 2002, COST OPTIMAL LINE PL
[6]   Algorithms for railway crew management [J].
Caprara, A ;
Fischetti, M ;
Toth, P ;
Vigo, D ;
Guida, PL .
MATHEMATICAL PROGRAMMING, 1997, 79 (1-3) :125-141
[7]   Cost optimal allocation of rail passenger lines [J].
Claessens, MT ;
van Dijk, NM ;
Zwaneveld, PJ .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 110 (03) :474-489
[8]   OBTAINING CLIQUE, COVER AND COEFFICIENT REDUCTION INEQUALITIES AS CHVATAL-GOMORY INEQUALITIES AND GOMORY FRACTIONAL CUTS [J].
DIETRICH, BL ;
ESCUDERO, LF .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 73 (03) :539-546
[9]   Dispatching buses in parking depots [J].
Gallo, G ;
Di Miele, F .
TRANSPORTATION SCIENCE, 2001, 35 (03) :322-330
[10]  
GOOSSENS JH, 2002, RM02009 METEOR U MAA