Title

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.

Share

COinS