Search: onr:"swepub:oai:DiVA.org:vti-320" >
Railway Timetabling...
Railway Timetabling Using Lagrangian Relaxation
-
- Brännlund, Ulf (author)
- KTH
-
- Lindberg, Per Olov (author)
- Linköping University
-
- Nou, Andreas (author)
- KTH
-
show more...
-
- Nilsson, Jan-Eric, 1952- (author)
- Banverket
-
show less...
-
(creator_code:org_t)
- Institute for Operations Research and the Management Sciences (INFORMS), 1998
- 1998
- English.
-
In: Transportation Science. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0041-1655 .- 1526-5447. ; 32:4, s. 358-369
- Related links:
-
https://urn.kb.se/re...
-
show more...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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 if 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, wh ich 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.
Subject headings
- NATURVETENSKAP -- Matematik -- Matematisk analys (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Mathematical Analysis (hsv//eng)
Keyword
- Optimization
- Mathematical model
- Timetable
- Rail bound transport
- Railway: Passenger transport
- Railway: Passenger transport
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database