Railway Timetabling Using Lagrangian Relaxation

Publisher's full text
Ulf Brännlund
Per Olov Lindberg
Andreas Nou

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.

MEET US


6
Oct

Open seminar with Mistra SAMS international scientific advisory...

Mistra SAMS international scientific advisory panel (ISAP) is visiting Stockholm, and the program will host an open seminar where the panel members will give talks in their area of expertise.
19-20
Oct

ERPUG 2017

The five year anniversary of  European Road Profile Users' Group (ERPUG) Forum will take place at Ramboll head quarter, Copenhagen, Denmark October 19-20, 2017. 

LATEST NEWS


2017-07-05

Vehicle Driver Monitoring: sleepiness and cognitive load

To prevent road crashes it is important to understand driver related contributing factors, which have been suggested to be the critical reason in 94 per cent of crashes. The overall aim of the project Vehicle Driver Monitoring has been to advance the...


2017-06-29

Tomas Svensson new director-general

Tomas Svensson was today appointed Director-General of VTI. Tomas has been acting Director-General since January 2017. 


2017-05-30

Crash testing bicycles at VTI

For the first time single bicycle crashes have been simulated at the VTI crash safety laboratory.


2017-05-15

A case study exploring firefighters’ and municipal officials’ preparedness for electrical vehicles

A VTI-study presents a social perspective on new vehicle technology. It explores the self-reported preparedness of the fire departments (i.e., rescue services) in Sweden’s three largest cities regarding rescue operations involving electrical vehicles (EVs).


2017-05-02

Pioneering research on and about bicycles at VTI

Under what circumstances might cyclists lose tyre grip? What actions could then be taken to prevent a crash? VTI is currently developing a theoretical model of the behaviour of bicycle tyres during braking and steering in different situations and on different...


2017-05-02

Virtual pedestrians create efficient stations

If more people are to choose sustainable travel, then the public transport stations of the future must be designed so that pedestrians can get where they are going quickly, without congestion or queues. The Swedish Road and Transport Research Institute (VTI)...