Improving attractiveness of working shifts for train dispatchers

We consider the problem of scheduling shifts for train dispatchers: given legal and operational constraints, the dispatching work in geographical areas should be assigned to dispatchers. In previous work, we presented an integer-programming framework for scheduling one-day shifts, aiming to minimize the number of dispatchers needed. Here, we present a stronger formulation for this problem. Moreover, we handle several quality aspects of the resulting shifts: we exclude undesirable start times and too short shifts; and we present four approaches to handle unnecessary changes in the dispatcher-area assignments. With an experimental performance-evaluation, we show that the stronger model significantly reduces the runtime in all but one instance, with an average decrease of 82.2 percent. We can solve all real-world-sized instances in less than 10 seconds. Moreover, we compare the four handover-approaches on instances with different temporal and geographical resolutions, and show that the two promising approaches allow us to solve a real-world-sized instance.