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.

LATEST NEWS


2018-06-13

International Conference on Electric Road Systems starts today

Electric Road Systems (ERS) is a relatively new concept with many initiatives on the way. To learn from each other and stimulate new collaborations the Swedish Research and Innovation Platform for Electric Roads arranged the first international conference...


2018-05-18

Same survey of road users’ attitudes in 50 countries

At the Road Safety on Five Continents Conference, RS5C, one entire session presented a large survey of road users' attitudes in 38 countries. Results show large differences between countries in many areas, both regarding behavior and attitudes. A new survey...


2018-05-17

Good results with alcohol interlock program according to Swedish study

An alcohol interlock program makes it possible for drink driving offenders to continue their everyday lives. In a Swedish study most of the participants were satisfied with the program and experienced improved health. They also reported drinking alcohol more...


2018-05-16

Traffic safety in the spotlight

Today the Conference Road Safety on Five Continents (RS5C) opened in Jeju Island, South Korea. More than 220 participators have come from all over the world to present findings and learn about traffic safety. Dr. Young Tae Kim, Secretary-General of the...


2018-04-17

VTI will develop simulators for ambulance staff

VTI has initiated a pilot study for paramedics with the Centre for Teaching & Research in Disaster Medicine and Traumatology and Linköping University. The aim is to give ambulance staff the opportunity to practice critical medical tasks in a moving vehicle in...


2018-04-12

Unique electrified road opens in Sweden

The world’s first electrified road recharging the batteries of cars and trucks while driving opened in Sweden. The Swedish Minister for Infrastructure, Tomas Eneroth, was at the formal inauguration of the electrified road on April 11, 2018. VTI is one of 22...