Multi-Depot Periodic Vehicle Routing Problem under Cleaning Constraints at the Oslo Metro

Abstract

Kollektivtransportsystemer som T-banen i Oslo dekker en essensiell del av storbyers behov for persontransport. Verden opplever en økende urbanisering og etterspørsel etter klimavennlige transportløsninger. Større og mer komplekse transportsystemer gir samtidig en mulighet for å for å redusere kostnader gjennom operasjonsanalyse. En betydelig kostnadsbesparing er å redusere tomkjøring av tog mellom depot og første og siste stasjon på en T-banerute. På grunn av det integrerte designet er dette problemet spesielt presserende for T-banenettverket i Oslo.

En allokeringsplan av tog til depot og ruter må også tilfredstille togenes vaskekrav innen visse tidsintervall, og bare noen depot er utstyrt med vaskeutstyr. En slik plan må også overholde depotenes makskapasitet. Denne oppgaven forsøker å finne allokeringsplaner som minimerer tomkjøring i realistiske scenarier ved T-banen i Oslo over lange planleggingshorisonter mens vaskekrav er tilfredstilt. Oppgavens hovedbidrag er å definere problemet, formulere en tilhørende matematisk modell, utvikle en eksakt og en heuristisk løsningsmetode og teste den heuristiske løsningsmetoden for realistiske instanser over lange planleggingshorisonter. Det er ikke identifisert tidligere forskningslitteratur på T-banesystemer som dekker dette

problemet, men relatert forskning på metrobussystemer finnes og er diskutert i oppgaven. En halvårlig allokeringsplan for T-banen i Oslo er funnet i oppgaven ved bruk av den foreslåtte heuristiske løsningsmetoden. Denne løsningen er estimert til å utgjøre en 18,6 prosent forbedring, tilsvarende en kostnadsbesparelse på 3,4 millioner kroner, sammenlignet med dagens løsning fra Sporveien AS, operatøren av T-banen i Oslo. Løsningen er funnet ved bruk av kommersiell programvare på en vanlig stasjonær datamaskin innen en løsningstid på 24 timer.

Mass rapid transit systems like the Oslo Metro are an important part of a city’s transport service in a world of increased urbanization and demand for environmentally friendly transport solutions. Increasing size and complexity of transport systems also provides an opportunity for optimizing scheduling and planning to reduce costs. A significant cost saving measure is to reduce the distance empty trains drive between depots and terminal stations. Driving empty trains between depots and the first and last station of a day is called deadheading. Because of the integrated network design the problem of reducing deadheading is particularly relevant at the Oslo Metro.

A plan that allocate trains to depots and passenger routes must also satisfy cleaning constraints as all trains must be cleaned within certain time intervals, and only some depots have cleaning equipment. Such a plan must also adhere to the maximum storing capacity of all depots.

This thesis aims to find allocation plans that minimize deadheading in a realistic situation at the Oslo metro over a long planning horizon while satisfying all practical side constraints. The main contributions of this thesis is defining the Multi-Depot Periodic Vehicle Routing Problem, formulating a mathematical model for the problem, developing an exact and heuristic solution method and testing the heuristic solution method for realistic instances with long planning horizons. No previous research literature on metro systems are found that study this problem, however, related research on the similar bus rapid transit systems exists and are discussed in the thesis. A half-year allocation plan for the Oslo Metro is found using the proposed heuristic solution method. This solution is estimated to pose an 18.6 percent improvement, equivalent to a cost saving of about NOK 3.4 million, over the current plan used by Sporveien AS, the operator of Oslo Metro. The solution is found using a commercial solver on a standard desktop computer within 24 hours of computing time.