Exact methods for the time frame rostering problem in the context of tram driver rostering

Creating more robust rosters that offer medium-term planning security for employees is a desired goal in the public trans- portation sector. To tackle this problem, we introduce a new approach in the context of tram driver rostering 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 paper, we formally define the time frame rostering problem and provide a solver-independent model of the problem. Furthermore, we compare two state-of-the-art solvers on real-world instances and demonstrate that optimal or almost optimal solutions can be found in a reasonable amount of time. Additionally, we verify these solutions by simulating absences and subsequent shift assignment.