Abstract
At toga er punktlege er ein av dei viktigaste indikatorane
på at togtrafikken fungerer, og høg andel punktlege tog er naudsynt om jernbana skal vera ein attraktiv transportform. I alle jernbanenett vil det skje at tog vert forseinka, og for å halde toga så punktlege som mogleg, må ein handtere desse forseinkingane slik at dei vert minst mogleg, og får minimalt utslag på resten av trafikken i nettet. Dette er ein kompleks oppgåve, sidan togrutene er tett kopla saman og kapasiteten i nettet er avgrensa. I dag er det menneskelege trafikkleiarar som gjer denne jobben, med noko hjelp frå ulike støttesystem.
Eg har formulert ein matematisk modell for tog som køyrer i eit nett av stasjonar og linjer, og legg fram ein algoritme for å løyse problemet med optimal trafikkstyring av tog i sann tid. Algoritmen kan nytta to ulike metodar for å forhindre konfliktar med kapasiteten på stasjonane. Den eine er å leggje til overdekningssidekrav dynamisk, og den andre er ein kompakt flytformulering.
Testar med dei to metodane på tre testtilfelle med aukande tal på stasjonar og tog, syner at metoden med overdekningssidekrav gjev meir fleksibilitet, betre skalering og er eit betre val for bruk i den verkelege verda.
Denne oppgåva legg fram ein modell og ein algoritme som finn ei optimal løysing i sann tid på problemet med trafikkstyring av tog på enkeltspor.
Punctuality is a key performance indicator for railway traffic, and high punctuality is vital if the railways are to be an attractive means of transport. In any railway network, delays will occur, and in order to maintain high punctuality, these delays must be dealt with in such a way that they are minimized and have a minimal impact on the rest of the traffic in the network. This is a complex task, as the train schedules are strongly intertwined, and capacity in the network is limited. Today, this task is done by human dispatchers, with some help from varying decision support systems.
I have formulated a mathematical model for trains running on a network of stations and tracks, and present an algorithm for solving to optimality the Railway Traffic Control Problem of re-scheduling trains in real-time. The algorithm can be implemented using either dynamically added cover cuts, or a compact flow formulation for station capacity conflicts.
Testing the two approaches on three test cases with an increasing number of trains and stations, we see that the cover cuts implementation has more flexibility, better scaling properties, and is the best choice for real world implementations.
This thesis describes a model and an algorithm that can solve the Single-Track Railway Traffic Control problem to optimality in real-time.