Railway Timetabling Using Lagrangian Relaxation

Förlagets fulltext
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.

TRÄFFA OSS


5-6
dec

Vision Zero for Sustainable Road Safety in the Baltic Sea Region

Konferensen Vision Zero for Sustainable Road Safety in the Baltic Sea Region arrangeras i Vilnius. VTI medverkar i organiserandet av konferensen och som talare.
9-10
jan

Transportforum 2019

Transportforum 2019 genomförs 9-10 januari i Konsert och kongress Linköping. 
25-27
aug

ICTTP 2020

ICTTP, International Conference on Traffic and Transport Psychology, arrangeras i Göteborg. 

SENASTE NYTT


2018-11-08

Ny teknik för att undersöka resvanor öppnar möjligheter

Alternativa resvaneundersökningar kan ibland ersätta traditionella, men då måste syftet vara tydligt. VTI har testat insamlingsmetoderna webbenkät och mobilapp under olika förutsättningar i en pilotundersökning tillsammans med Trafikanalys och Trivector.


2018-11-07

VTI kartlägger cykelträngsel

Cykelträngseln i storstäder som Stockholm och Göteborg – det är en fråga som engagerar. Forskare på VTI har undersökt cykelflöden för att ta reda på om är problemet så stort så att det får samhällsekonomiska konsekvenser.


2018-11-01

Regeringsuppdrag om trafikens samhällsekonomiska kostnader överlämnat

VTI har sedan 2013 haft flera uppdrag från regeringen att ta fram underlag om trafikens samhällsekonomiska kostnader. 1 november 2018 redovisades det senaste uppdraget, Samkost 3. Uppdraget har omfattat alla trafikslag, men fokus har legat på sjö- och luftfart.


2018-10-26

Pedagogikutveckling med tågsimulatorer

Det är hög koncentration och många aha-upplevelser när tågklarerare får prova på att sitta ”på andra sidan” mot var de vanligtvis befinner sig. De är de som styr vilka tåg som ska köra och när. I VTI:s tågsimulatorer får de i stället prova på miljön och...


2018-10-19

Dubbdäck till cykel testade

Halka är den dominerande orsaken bakom cyklisternas singelolyckor under tiden december-februari. Ett sätt att minska olycksrisken är att använda dubbdäck. VTI har, på uppdrag av Länsförsäkringars forskningsfond, testat ett antal däck.


2018-10-15

VTI utvecklar effektivare halkbekämpning

Genom rätt åtgärder på rätt plats och tid kan halkbekämpning rädda liv, säkra arbetsmiljön och minska samhällskostnaderna. Nu finns digital teknik som ska förbättra vinterväghållningen. VTI har tagit fram systemet tillsammans med Svevia och B&M systemutveckling.


2018-10-02

Mobilitetstjänster möjliga även i landsbygd

Tjänster som bilpooler och cykeluthyrning växer i städerna med syfte att öka mobiliteten och samtidigt minska behovet av egen bil. Men hur kan sådana tjänster införas även på landsbygd? Nu har en förstudie presenterats som visar på vägen framåt mot...


2018-10-01

Mer kunskap om ambulansvård under utryckning

Ambulanspersonal har tuffa utmaningar. Utryckningsfordonets framfart och arbetsmiljö påverkar de flesta vårdmomenten som utförs i ambulansen. Det visar en forskningsrapport från VTI, Katastrofmedicinskt centrum och Linköpings universitet.


2018-11-08

Ny teknik för att undersöka resvanor öppnar möjligheter

Alternativa resvaneundersökningar kan ibland ersätta traditionella, men då måste syftet vara tydligt. VTI har testat insamlingsmetoderna webbenkät och mobilapp under olika förutsättningar i en pilotundersökning tillsammans med Trafikanalys och Trivector.


2018-11-07

VTI kartlägger cykelträngsel

Cykelträngseln i storstäder som Stockholm och Göteborg – det är en fråga som engagerar. Forskare på VTI har undersökt cykelflöden för att ta reda på om är problemet så stort så att det får samhällsekonomiska konsekvenser.


2018-11-01

Regeringsuppdrag om trafikens samhällsekonomiska kostnader överlämnat

VTI har sedan 2013 haft flera uppdrag från regeringen att ta fram underlag om trafikens samhällsekonomiska kostnader. 1 november 2018 redovisades det senaste uppdraget, Samkost 3. Uppdraget har omfattat alla trafikslag, men fokus har legat på sjö- och luftfart.


2018-10-26

Pedagogikutveckling med tågsimulatorer

Det är hög koncentration och många aha-upplevelser när tågklarerare får prova på att sitta ”på andra sidan” mot var de vanligtvis befinner sig. De är de som styr vilka tåg som ska köra och när. I VTI:s tågsimulatorer får de i stället prova på miljön och...


2018-10-19

Dubbdäck till cykel testade

Halka är den dominerande orsaken bakom cyklisternas singelolyckor under tiden december-februari. Ett sätt att minska olycksrisken är att använda dubbdäck. VTI har, på uppdrag av Länsförsäkringars forskningsfond, testat ett antal däck.


2018-10-15

VTI utvecklar effektivare halkbekämpning

Genom rätt åtgärder på rätt plats och tid kan halkbekämpning rädda liv, säkra arbetsmiljön och minska samhällskostnaderna. Nu finns digital teknik som ska förbättra vinterväghållningen. VTI har tagit fram systemet tillsammans med Svevia och B&M systemutveckling.


2018-10-02

Mobilitetstjänster möjliga även i landsbygd

Tjänster som bilpooler och cykeluthyrning växer i städerna med syfte att öka mobiliteten och samtidigt minska behovet av egen bil. Men hur kan sådana tjänster införas även på landsbygd? Nu har en förstudie presenterats som visar på vägen framåt mot...


2018-10-01

Mer kunskap om ambulansvård under utryckning

Ambulanspersonal har tuffa utmaningar. Utryckningsfordonets framfart och arbetsmiljö påverkar de flesta vårdmomenten som utförs i ambulansen. Det visar en forskningsrapport från VTI, Katastrofmedicinskt centrum och Linköpings universitet.