Creating Robust and Cost-Efficient Line Plans for the Oslo Metro Using Combinatorial Benders' Decomposition

Abstract

I 2019 transporterte T-banen mer enn 119 millioner passasjerer i Oslo og Bærum kommune, og antall reisende er forventet å øke i årene som kommer. Mulighetene for kostnadsreduksjon og reduksjon i klimaavtrykk gjør det ønskelig å drifte T-banen mer effektivt. Driften av T-banen kan effektiviseres ved minimering av kostnader knyttet til antall tog. Dagens drift av T-banen utføres manuelt ved bruk av Excel, basert på erfaring og skjønn. Dette gjør det utfordrende å vekte alle krav og preferanser knyttet til strukturen og driften av T-banen, noe som kan medføre suboptimale løsninger.

Denne masteroppgaven er skrevet i samarbeid med Sporveien AS, som eier og administrerer T-banen. Formålet er å lage et beslutningsverktøy for å generere et linjekart og tilhørende tidstabell som minimerer kostnader. Linjeplanleggingsproblemet og tidstabellproblemet er matematisk formulert, og de resulterende modellene er integrert og løst ved bruk av Kombinatorisk Benders' Dekomponering. Etter omfattende litteratursøk konkluderer forfatterene av denne oppgaven med at problemstillingen som oppgaven tar for seg ikke er drøftet i litteraturen tidligere.

Modellen benytter de operasjonelle og strukturelle parameterene som Sporveien bruker i driften av T-banen i dag. I tillegg benyttes parametere som er estimert, basert på historisk data på kjøretidsavvik. Modellen genererer en løsning som er mer optimal enn T-banens nåværende linjekart og tidstabell. Det viser seg at signifikante kostnadsreduksjoner er mulig å oppnå ved bruk av beslutningverktøyet som er beskrevet i denne masteroppgaven. Denne reduksjonen skyldes primært en reduksjon på maksimalt tre tog relativt til dagens drift. Videre indikerer resultatene at verktøyet genererer løsninger som finner en god balanse i avveiningen mellom robusthet og kostnadseffektivitet. Ved å inkludere myke restriksjoner i modellen, oppnår man videre innsikt i avveiningen mellom robusthet og kostnadseffektivitet.

Problemet som studeres i masteroppgaven tar for seg planlagte prosjekter angående endringer i driften og strukturen av T-banen. En planlagt operasjonell endring vil resultere i ytterligere avganger, noe som forbedrer kollektivtilbudet i Oslo og Bærum. Videre er tilskuddet av en ny T-banestrekning, som knytter Fornebu til sentrum, en strukturell endring som Sporveien planlegger å gjennomføre. Resultater viser at beslutningsverktøyet presentert i denne masteroppgaven kan inkorpore ny infrastruktur til det eksisterende T-banenettet på en effektiv måte.

The Oslo Metro transported more than 119 million people in 2019, and the passenger demand is expected to increase in the years to come. The opportunities of reducing costs and the carbon footprint provide incentives to operate the Oslo Metro efficiently. A means to achieve operational efficiency is to minimize the costs related to the number of trains needed in operation. The current planning of the Oslo Metro is done manually based on experience and discretion using Excel. This makes it challenging to weigh all requirements and preferences concerning the structure and operations of the metro system, and might result in suboptimal operations.

This thesis is written in collaboration with Sporveien AS, which is the owner and administrator of the Oslo Metro. The common goal is to create a decision support tool to generate a line plan and a corresponding timetable that minimize costs. The problems of line planning and timetabling are mathematically formulated, and the resulting models are integrated and solved using Combinatorial Benders' Decomposition. Studying relevant literature, a similar problem with all the considered aspects has to the best of our knowledge not previously been investigated.

The input of the model is the structural and operational parameters that Sporveien AS currently operates with. Further, an analysis of historical data on travel times has been conducted, and the results are used as input to the model. The optimal solution of the model differs from the current line plan and timetable. It proves that significant cost reductions are enabled by utilizing the decision support tool created. The cost reduction is primarily due to a reduction of maximally three trains needed in operation. The results further indicate that the decision support tool generates solutions that balance the trade-off between cost-efficiency and robustness. An extended version of the model including soft constraints provides further analysis of this trade-off.

Future projects regarding changes to the operations and structure of the Oslo Metro are studied in this thesis. A planned operational change is the introduction of additional arrivals, which enhances the public transport service in the Oslo Metro. Furthermore, a planned structural change is the addition of a new stretch of railway tracks connecting Fornebu and the city center. The decision support tool created in this thesis proves to efficiently incorporate the addition of new infrastructure to the existing network of the Oslo Metro.