This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Goossens, J.-W. Articles by Kroon, L. Search for Related Content

A Branch-and-Cut Approach for Solving Railway Line-Planning Problems

Department of Quantitative Economics, University of Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands
Department of Quantitative Economics, University of Maastricht, P.O. Box 616, 6200 MD Maastricht, The Netherlands
Rotterdam School of Management, Erasmus University Rotterdam, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands
j.goossens{at}ke.unimaas.nl
s.vanhoesel{at}ke.unimaas.nl
l.kroon{at}fbk.eur.nl

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.

Key Words: rail transportation; integer programming; branch and cut; combinatorial optimization
History: Received: September 2001; revised: September 2002; accepted: September 2002.

This article has been cited by other articles:

				R. Borndorfer, M. Grotschel, and M. E. Pfetsch A Column-Generation Approach to Line Planning in Public Transport Transportation Science, February 1, 2007; 41(1): 123 - 132. [Abstract] [PDF]