Solving the Train Dispatching Problem Using Graph Neural Networks

Abstract

Train Dispatching Problemet er arbeidet rundt å innhente togforsinkelser når uforutsette hendelser oppstår. Per dags dato, bruker en kontrollør gjerne intuisjon og erfaring i kombinasjon med hjelpeverktøy for å minke forsinkelser. Disse hjelpevektøyene er blant annet heuristikker eller eksakte algoritmer som finner en ny tidsplan for togene. Ulempen ved disse metodene er at de enten finner suboptimale løsninger eller skalerer eksponentsielt i kjøretid med størrelsen på jernbanenetverket. Dermed vil en skalerbar metode med bedre løsninger enn heuristikker kunne skape verdi for både jernbaneaktører og passasjerer. I lang tid har problemet blitt forsøkt løst ved bruk av MILP Formulering og Branch-and- Bound som metode. I senere tid har Reinforcement Learning blitt aktivt testet ut. Vår metode tar utgangspunktet i en Graph Neural Network-arkitektur og Markov Decision Process, med problemet på en Alternativ Graf Formulering. Ved å teste på data fra Jærbanen og Dovrebanen i Norge, viser vår metode forbedrede løsninger i forhold til to klassisk heuristikker. Av de 6 unike vektene som ble trent, ga selv den dårligeste agenten en reduksjon på 59, 6% og 43, 6% i forsinkelser mot heuristikene på problemer med kjent optimal løsning. Videre reduserte agentene den gjennomsnitlige forsinkelsetiden med mer enn 9 minutter mot en grådig heuristikk og mer en 18 minutter mot en First- Come, First-Served heuristikk på problemer med ukjent optimal løsning. Samtidig skalerer methoden betydelig bedre enn eksakte løsere, som ofte kan være uanvennlige på vanskelige problemer.

The Train Dispatching Problem is the effort of rectifying train traffic when disturbances and disruptions have happened, with the least possible delay. In everyday life, the problem is solved by dispatchers using intuition and experience on specific lines sometimes with the assistance of tools such as heuristics and exact solvers. However, these methods are often limited by either suboptimal solutions or exponential scalability. Finding efficient and performant solution methods could provide significant value to society. The problem has classically been studied with formulations such as Mixed-Interger Linear Program- ming (MILP) and methods such as Branch-and-Bound. More recently Reinforcement Learning and Graph Neural Network (GNN) methods have been tested. We propose a new GNN-based method that uses the Alternative Graph Formulation with a Markov Decision Process to solve the problem. This method shows significant improvement over two classic heuristics in our evaluations with data from Jærbanen and Dovrebanen in Norway. Out of 6 differently trained GNN agents, even the worst one reduces the MIP gap by 59.6% and 43.6% versus the best heuristic in two evaluation sets with known op- timal solutions. Furthermore, the trained GNN agents achieve, on average, more than 9 minutes improvement over the greedy heuristic, and more than 18 minutes improvement over the First-Come, First-Served heuristic in instances without known optimal solutions. It also scales considerably better than exact solvers, which can be inapplicable to use in difficult instances.