Railway timetables are constructed yearly and contain the plan for the complete subsequent year. However, over the course of that year, they have to be modified frequently. A common cause is the closure of a line due to maintenance works, but also disruptions can cause railway lines to be closed for multiple days. In these scenarios, regional trains are often partially cancelled and replaced by buses, while it is preferable to keep long-distance trains running by rerouting them.

In order to reroute a train, planners must change its schedule—also known as a train path. At the moment, train paths are altered manually. We propose algorithms that help to automate these procedures. These algorithms also have other use cases for an infrastructure manager or a railway undertaking: they can add or request an ad-hoc train path, or verify when capacity is still available.

We present the building block for our later train rerouting procedure in Paper I: a fast and scalable algorithm for determining possible train paths for a single train. This algorithm is based on dynamic programming and obtains multiple pareto-optimal solutions within a given time window. By cleverly ordering the segments in the railway network, we only need to iterate over these segments once in order to obtain all useful schedules for that train. We also explore several settings for simplifying the network to further speed up the computations.

We use our procedure from the previous paper in Paper II to tackle larger rerouting settings when several trains must obtain a new path. We generate multiple options for each train and subsequently select one option for every train. This selection problem can be seen as an independent set problem: each possible path would be represented by a vertex, and a pair of vertices would be adjacent when adding both schedules creates a conflict. We explore a case study where the Southern Main Line is closed during a weekend, leading to 50 rerouted trains.

We can summarize our work on train rerouting by these two contributions: we explored the problem of inserting a single train to a timetable, and used these results for rerouting multiple trains. In addition to inserting/rerouting train paths close to operation, we also studied other aspects of handling train paths—in Paper III, in the context of timetabling early in advance. In Sweden, the operators must indicate in April which trains they want to run next year, while it can be hard to predict freight volumes so long in advance. Furthermore, the publication date in September is quite late for operators of passenger trains, who would prefer to start selling tickets earlier. Besides, this timetable cannot give any guarantee about the ability to also run the same train in later years, while it is also difficult to align large construction works between countries.

To resolve these limitations, a new, European timetabling process will be introduced. However,in order to shorten the time period between the requests of operators and the timetable publication,significant parts of the timetable must be pre-planned before operators submit their requests in April. Compared to other countries, Sweden has rather diverse freight trains, which are given a relatively high prioritization. This complicates the pre-planning of a timetable when the exact requests are unknown, thereby raising several interesting questions.

In Paper III, we shift our horizon to the new timetabling process. As timetabling will start before the precise requests are known, it now involves an additional layer of uncertainty—in particular,when it comes to freight trains. We get a grasp on this uncertainty by analyzing the last four yearly timetables. We compare which types of freight trains have which kinds of deviations,including changes in routing, timing, origin, destination, or intermediate commercial stops. This results in an overview of which later deviations should be anticipated when pre-planning a timetable, which also includes how much these fluctuate between different timetable changes.

To conclude, we consider two different contexts of handling train paths. In Paper I, we consider adding a single train to an existing timetable, like in ad-hoc settings. The scope is extended for rerouting multiple trains in Paper II. We subsequently switch to the setting of the yearly timetabling process, where the new rules will require pre-planning before the requests are submitted. As a first step, we analyze in Paper III how these requests change between different years.

Tågtidtabeller konstrueras årligen och utgör en plan for hela följande året. Dock måste de ofta uppdateras under årets lopp. En vanlig orsak ar att en linje är stängd för underhållsarbeten,men även störningar kan orsaka avstängningar under flera dagar. I dessa fall ställs regional trafik ofta in delvis för att ersättas med bussar, medan det typiskt är fördelaktigt att leda om fjärrtågen.

För att leda om tåg måste planerare ändra på tågets schema, hädanefter kallat tågläge. I dagsläget sker denna uppdatering av tåglägen manuellt. I det har arbetet föreslås algoritmer som kan användas for att automatisera detta. Sådana algoritmer har också andra användningsområden hos en infrastrukturhållare eller tågoperator som kan lagga till eller ansöka om tåglägen ad hoc,eller undersöka var det ännu finns ledig kapacitet.

Den centrala byggstenen for att for att automatisera omledningsförfarandet presenteras i Paper I: en snabb och skalbar algoritm för att hitta möjliga tåglägen for ett tag i taget. Algoritmen bygger på dynamisk programmering och hittar många pareto optimala lösningar inom ett givet tidsfönster. Genom att sortera segment i järnvägsnätet på ett smart satt behovs bara en iteration over dessa for att generera alla användbara tåglägen for det aktuella taget. Ytterligare inställningar för att förenkla nätverket och därigenom snabba upp beräkningarna undersöks också.

Den föreslagna metoden används sedan i Paper II for att hantera större omledningar när flera tåg måste få nya tåglägen. For varje tag tas flera alternativ fram och ett av dessa selekteras ut. Detta selektionsproblem kan ses som problemet att avgöra om en given graf har en oberoende mängd,det som på engelska kallas ’the independet set problem’: varje möjligt tågläge representeras dåav en nod, och ett par av noder är intilliggande när de båda tåglägena orsakar en konflikt. Metoden demonstreras på ett fiktivt fall, där Södra stambanan är stängd over ett veckoslut,vilket leder till 50 omledda tåg.

Arbetet kring omledning av tåg kan sammanfattas i följande två bidrag: problemet att skapa ett tågläge for ett enskilt tillkommande tåg i en given tidtabell har studerats, och resultaten har använts för att skapa tåglägen då multipla tåg leds om. Utöver hur man skapar/lägger om tåglägen sent i planeringsprocessen har även andra aspekter kring tåglägen studerats i Paper III, i samband med tidig förplanering. I Sverige måste operatorerna ansöka om tåglägen for nästa år redan i april, trots att det är mycket svårt att förutsäga godsvolymer sa långt i förväg.

Dessutom är datumet för fastställd tågplan i september mycket sent för de operatorer som kör resandetåg och skulle önska att biljettförsäljningen kunde komma igång tidigare. Därutöver finns idag inga garantier för att ett givet tåg ska kunna köras aven nästkommande år. Det är också svårt att samplanera stora banarbeten mellan länder.

For att komma till rätta med dessa begränsningar kommer en ny, europeisk tidtabelläggningsprocess att introduceras. For att korta tiden mellan operatörernas tåglägesansökningar och fastställd tågplan kommer dock viktiga delar av tidtabellen att behöva förplaneras redan innan operatörerna skickar in sina ansökningar i april. I jämförelse med andra länder har Sverige en relativt stor blandning av godståg, vilka ges en ganska hög prioritering. Detta komplicerar förplaneringen av tidtabellen där de exakta ansökningarna är okända, och ger upphov till flera intressanta frågor.

I Paper III flyttas fokus till den nya tidtabellsprocessen. Eftersom tidtabelläggningen kommer att påbörjas redan innan de exakta tåglägesansökningarna ar kända, tillkommer nu en nivå av osäkerhet, särskilt nar det kommer till godståg. Den har osäkerheten fångas upp genom att analysera de fyra senaste årens fastställda tågplaner. En jämförelse görs av vilka typer av godståg som har vilka sorters avvikelser, inklusive ändringar i rutt, tidläge, utgångsstation, destination eller mellanliggande, kommersiella stopp. Resultatet är en översikt av vilka förändringar man bör rakna med när tidtabellen förplaneras, vilket också innefattar hur mycket dessa fluktuerar mellan olika tidtabellsskiften.

For att sammanfatta studeras hanteringen av tåglägen i två olika sammanhang. Paper I handlar om hur ett enskilt tågläge kan laggas till i en given tidtabell, vilket inträffar i ad hoc-processen. Denna frågeställning utökas sedan till att lagga om multipla tåglägen i Paper II. Därefter flyttas perspektivet till den årliga tidtabellsprocessen dar de nya reglerna kommer att kräva förplanering innan tåglägesansökningarna är kända. Som ett första steg analyseras i Paper III hur dessa ansökningar förändras över åren.