Railway Timetabling Using Lagrangian Relaxation
- 1 November 1998
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 32 (4), 358-369
- https://doi.org/10.1287/trsc.32.4.358
Abstract
We present a novel optimization approach for the timetabling problem of a railway company, i.e., scheduling of a set of trains to obtain a profit maximizing timetable, while not violating track capacity constraints. The scheduling decisions are based on estimates of the value of running different types of service at specified times. We model the problem as a very large integer programming problem. The model is flexible in that it allows for general cost functions. We have used a Lagrangian relaxation solution approach, in which the track capacity constraints are relaxed and assigned prices, so that the problem separates into one dynamic program for each physical train. The number of dual variables is very large. However, it turns out that only a small fraction of these are nonzero, which one may take advantage of in the dual updating schemes. The approach has been tested on a realistic example suggested by the Swedish National Railway Administration. This example contains 18 passenger trains and 8 freight trains to be scheduled during a day on a stretch of single track, consisting of 17 stations. The computation times are rather modest and the obtained timetables are within a few percent of optimality.Keywords
This publication has 6 references indexed in Scilit:
- Routing Trains Through Railway Stations: Model Formulation and AlgorithmsTransportation Science, 1996
- A descent proximal level bundle method for convex nondifferentiable optimizationOperations Research Letters, 1995
- Tactical Scheduling of Rail Operations: The SCAN I SystemTransportation Science, 1991
- Integer and Combinatorial OptimizationPublished by Wiley ,1988
- Computer Aided Train Dispatching: Decision Support Through OptimizationInforms Journal on Applied Analytics, 1983
- The Lagrangian Relaxation Method for Solving Integer Programming ProblemsManagement Science, 1981