Exact Methods for the Time Frame Rostering Problem : In the Context of Tram Driver Rostering

Abstract

In dieser Diplomarbeit wird eine formale Definition eines in der Praxis vorkommenden kombinatorischen Optimierungsproblems im Bereich der Personaleinsatzplanung, speziell im Bereich der Dienstplanung für Straßenbahnfahrer:innen, vorgestellt. Aktuelle Ansätze in der Straßenbahn Turnuserstellung bieten den Fahrer:innen oft nur unzureichende mittelfristige Planungssicherheit. Es ist daher ein Ziel im öffentlichen Verkehrswesen, robustere Dienstpläne zu erstellen, die den Mitarbeiter:innen eine solche mittelfristige Planungssicherheit bieten. Um dieses Problem anzugehen, führe ich das Konzept des Rahmenzeiten-Turnusses formal ein. Anstatt den Turnuspositionen direkt Schichten zuzuweisen, werden den Positionen zunächst Rahmenzeiten zugewiesen. Diese Rahmenzeiten sind Zeitintervalle weit genug, um mehrere Schichten abdecken zu können. Die Schichtzuweisung erfolgt erst wenige Tage vor dem eigentlichen Arbeitstag. Somit verbessern Rahmenzeiten-Turnusse die mittelfristige Planungssicherheit, da Straßenbahnfahrer:innen garantiert wird, nur Schichten innerhalb ihrer zugewiesenen Rahmenzeit zu erhalten. Das Ziel des Rahmenzeiten-Turnusproblems besteht darin, Rahmenzeiten optimal einem Turnus zuzuweisen, sodass verschiedene Bedingungen erfüllt werden. In dieser Arbeit gebe ich eine allgemeine Problembeschreibung sowie eine formale Definition des Rahmenzeiten-Turnusproblems. Basierend auf dieser Definition wird ein löser-unabhängiges Modell des Problems vorgestellt. Darüber hinaus vergleiche ich zwei Löser, Gurobi und OR-Tools CP-SAT, anhand realer Instanzen und zeige, dass optimale oder nahezu optimale Lösungen in angemessener Zeit gefunden werden können. Zusätzlich überprüfe ich diese Lösungen mittels Monte-Carlo-Simulationen. Dabei werden die Abwesenheiten der Straßenbahnfahrer:innen simuliert und es wird überprüft, ob die anschließende Schichtzuweisung weiterhin möglich ist. Die Ergebnisse dieser Simulationen zeigen, dass das Modell den Anforderungen der allgemeinen Problembeschreibung entspricht.

In this diploma thesis, I introduce a formal definition of a real-world combinatorial optimization problem in the field of workforce scheduling, specifically in the area of tram driver rostering. Current tram driver rostering methods struggle with providing the tram drivers with medium-term planning security. Thus, creating more robust rosters that offer such medium-term planning security for employees is a desired goal in the public transportation sector. To tackle this problem, I formally introduce a new approach called time frame rostering. In this approach, instead of directly assigning shifts to roster positions, time frames are first allocated to roster positions. These time frames are intervals wide enough to accommodate a variety of shifts. The shift assignment takes place only a few days before the actual workday. Thus, time frame rosters provide medium-term planning security, as tram drivers are only assigned shifts within their designated time frames. The goal of the time frame rostering problem is then to optimally assign time frames to a roster such that several constraints are met. In this thesis, I provide a high-level problem description as well as a formal definition of the time frame rostering problem. Based on this definition, a solver-agnostic model of the problem is presented. Furthermore, I compare two state-of-the-art solvers, Gurobi and OR-Tools CP-SAT, on real-world instances and demonstrate that optimal or almost optimal solutions can be found in a reasonable amount of time. Additionally, these solutions are verified by Monte Carlo simulations. In this approach, I simulate the tram drivers’ absences and check whether subsequent shift assignment is still possible. The results of these simulations show that the model works as intended and corresponds to the high-level problem description.