The Road-Based Vehicle Rescheduling Problem: Methods and Extensions

In contrast to the well-researched aircraft and railway recovery problems, the road- based vehicle rescheduling problem (VRSP) is a relatively unexplored problem. This thesis builds further on Li, Mirchandani, and Borenstein (2009), who proposed solving the VRSP using a Lagrangian heuristic. This results in fewer cancelled trips than an ad hoc rescheduling procedure, emphasizing the benefits of optimized rescheduling. Besides replicating the results of Li et al. (2009), we compare their Lagrangian heuristic with a column generation based heuristic. This heuristic leads to better, very often optimal solutions, but computation times are longer. The last contribution of this thesis is the introduction of the vehicle rescheduling problem with retiming (VRSPRT), where trips can not only be cancelled, but also delayed. This increases scheduling flexibility such that less disruptive solutions can be obtained. To incorporate the delays in the problem formulation, we propose a new method that expands the underlying network to include all relevant delay possibilities. An advantage of this method is that both heuristics for the VRSP can directly be applied. For large instances, we propose a dynamic neighborhood exploration heuristic that allows retiming for a subset of all trips. The results indicate that retiming reduces the number of cancellations with 40% compared to the original VRSP.