Solving periodic timetabling problems with SAT and machine learning
Document Type
Journal Article
Publication Date
2021
Subject Area
operations - scheduling
Keywords
Periodic timetabling, Optimisation, Periodic event scheduling problem, SAT, Reinforcement learning
Abstract
In this research work we address periodic timetabling, namely the optimisation of public transport timetables with respect to travel times using Boolean satisfiability problem (SAT) and reinforcement learning approaches. While in previous work this optimisation problem has been addressed with mixed integer linear programming, genetic algorithms, SAT, the modulo network simplex, among other techniques, in this work we use an approximation method based on SAT, reinforcement learning and multiagents, a combination of techniques which (to our knowledge) has never been applied in this field. Finally, we present promising results which show that our approach applied to real-world data performs better than existing SAT approaches and even outperforms the current state-of-the-art algorithms (based on the modulo network simplex, mixed integer programming and heuristics) on some problems.
Rights
Permission to publish the abstract has been given by SpringerLink, copyright remains with them.
Recommended Citation
Matos, G.P., Albino, L.M., Saldanha, R.L., & Morgado, E.M. (2021). Solving periodic timetabling problems with SAT and machine learning. Public Transport, Vol. 13, pp. 625–648.
