Graph Neural Network Heuristic for Timetable Planning in Public Transport
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2024-05-21
Department
Major/Subject
Systems and Operations Research
Mcode
SCI3055
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
41+1
Series
Abstract
In public transport planning, timetabling is the process of assigning times for vehicle departures and arrivals to stops. Timetable optimization is an important step of a typical public transport planning process. The timetable affects which routes the passengers choose to take. Yet, the choices of routes also affect which timetables are optimal. As such, the best solutions to this problem are obtained when both the timetable and the passenger routes are optimized simultaneously instead of sequentially. However, this quickly becomes computationally intractable. Instead of finding exact solutions, as a heuristic approach, we propose to predict the best passenger routes and then to optimize the timetable using established methods. We propose a graph neural network model for predicting the aggregated passenger counts on the edges of the event activity network. Our approach demonstrates occasional improvements against a shortest path routing baseline. The relationship between the weight prediction loss and the resulting optimality gap indicates, that training the network with a direct regression task may not directly result in improvements of the optimality gap, which is our ultimate objective. Further research in the topic of graph neural networks as a heuristic could explore other training tasks instead of the direct prediction approach. Generating high-quality training datasets is also an area that could be improved.Aikataulutus joukkoliikennesuunnittelussa on prosessi, jossa määritellään kulkuneuvojen lähtö- ja saapumisajat joukkoliikennepysäkeille. Aikataulun optimointi on tärkeä osa tyypillistä joukkoliikenteen suunnitteluprosessia. Valittu aikataulu vaikuttaa reitteihin, joita matkustajat valitsevat pysäkkien välillä, mutta toisaalta matkustajien suosimat reitit vaikuttavat aikataulun optimointiin. Parhaat ratkaisut aikataulutusongelmaan saadaankin optimoimalla aikataulu ja matkustajien reittivalinnat samanaikaisesti perättäisen optimoinnin sijasta. Tästä tulee kuitenkin nopeasti laskennallisesti haastavaa. Eksaktien ratkaisujen etsimisen sijaan työssä esitetään uusi heuristinen ratkaisumenetelmä, joka ennustaa matkustajien parhaat reititykset ja optimoi sitten pelkästään kulkuneuvojen aikataulut. Graafineuroverkkolla ennustamme kokonaismatkustajamääriä graafin kaarille tapahtuma-aktiviteettiverkossa. Verrattuna lyhyimmän reitityksen vertailukohtaan, menetelmämme tuottaa toisinaan parempia ratkaisuja. Opetustehtävähäviön ja optimaalisuuskuilun välinen riippuvuus ei indikoi, että regressiotehtävän ratkaisu graafineuroverkon opetuksessa kaventaisi suoraan optimaalisuuskuilua, mikä on varsinaisena tavoitteena. Jatkotutkimuksessa koskien graafineuroverkkojen käyttöä heuristiikkana voitaisiin perehtyä verkon muihin opetustehtäviin suoran ennustamisen sijasta. Korkealaatuisen koulutusdatan generointi on myös yksi parannettavista osa-alueista.Description
Supervisor
Schiewe, PhilineThesis advisor
Schiewe, PhilineKeywords
public transportation planning, graph neural networks, TimPass, heuristic