Railway Crew Rescheduling with Retiming

Railway operators have to deal with several disruptions during the day. These disruptions can make the timetable, rolling stock schedule and crew schedule infeasible. In this thesis, we present a column generation approach to reschedule the crew if a disruption made the crew schedule infeasible. This crew rescheduling approach uses retiming. With retiming it is allowed to slightly adapt the timetable if that would result in a better crew schedule. We use the retiming especially to come up with crew schedules with less canceled trains. First, we solve the crew rescheduling problem without using retiming. We do this by using an existing approach of \cite{Potthoff2008}. This approach selects only a subset of the duties and tasks to solve the problem. If the crew schedule generated by this existing approach has still some uncovered tasks, we use retiming and a neighborhood selection of duties to improve the schedule. Experiments on data instances of train drivers of Netherlands Railways (NS) have shown that our retiming approach results in better crew schedules than an approach without retiming. Especially, the approach with retiming comes up with crew schedules with less canceled trains. For the used instances of NS, the approach with retiming was able to generate a totally new crew schedule within three minutes. In the worst case it required only one minute computation time more than the approach without retiming. Both approaches (with and without retiming) have even some potential to become faster since some parts can be computed parallel on different cores or computers.