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


7
Dec

Shipping and the environment – research meets reality

Centre for Transport Studies (CTS) in co-operation with Ports of Stockholm invite you to the seminar Shipping and the environment – research meets reality.

LATEST NEWS


2017-10-26

Simulation of cut-in by manually driven vehicles in platooning scenarios

A study in a VTI-driving simulator has showed that a platoon will be able to handle a cut in from a manually driven car. The results of this study have recently been presented at two conferences in Japan.


2017-10-16

ERPUG Forum

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.


2017-09-29

Self-driving buses in Sweden next year?

A self-driving, fossil-free bus. This idea might become reality through a forthcoming collaborative project involving the Swedish National Road and Transport Research Institute (VTI), Linköping University and several other participants. The project group aim...


2017-09-29

New climate-proof solutions for hard surfaces in cities

High-density road infrastructure that emphasise maximum durability and minimum maintenance create inflexible systems, which put increased stress on urban trees and lead to increased risk for flooding. Over the past five years, the ‘Climate-proof solutions for...


2017-09-29

VTI is preparing for automated vehicles

Automation of traffic systems will lead to major changes. The European Union’s (EU) CoEXist research project began in June 2017 with the aim of preparing cities and road operators for the introduction of self-driving vehicles. The Swedish National Road and...


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...