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


5-6
Dec

Vision Zero for Sustainable Road Safety in the Baltic Sea Region

The conference Vision Zero for Sustainable Road Safety in the Baltic Sea Region is held i Vilnius, Lithuania. VTI is part of the organisation committé and also one of the speakers.

LATEST NEWS


2018-10-18

ADAS&ME is tackling the interaction between people and technology

ADAS&ME is a major EU project focused on automation, the human condition and the human environment. The budget is EUR 9.6 million and VTI is the coordinator.


2018-10-05

Users contribute to the development of train simulators

Apart from advanced driving simulators, VTI has developed several variations of train simulators which are used for training, education and research. In recent years, interest has increased drastically among major actors in the railway sector, and VTI has...


2018-10-03

VR study to contribute to a better working environment for bus drivers

A study where bus drivers test autonomous driving in a VR environment may contribute to a better working environment with reduced stress on the driver and safer driving.


2018-10-02

Non-native plant species spread via transport systems

Researchers at VTI have compiled a report on non-native invasive plant species in Sweden and how they spread via transport systems.


2018-09-20

EU-project VIRTUAL: improving road safety with virtual crash tests

Crash tests are used to improve safety on roads. Therefore the EU now funds a research project to develop virtual methods of crash testing. VTI coordinates the project, called VIRTUAL. The project now invites experts interested in Human Body Modeling to join...


2018-08-28

EU project protects cyclists and pedestrians

According to the World Health Organisation, more than one quarter of road traffic fatalities in 2010 were pedestrians and cyclists. Every year, about 335,000 unprotected road users die because of traffic accidents, which shows the scale of the problem. The EU...