The Vehicle Rescheduling Problem with Retiming

When a vehicle breaks down during operation in a public transportation system, the remaining vehicles can be rescheduled to minimize the impact of the breakdown. In this paper, we discuss the vehicle rescheduling problem with retiming (VRSPRT). The idea of retiming is that scheduling flexibility is increased, such that previously inevitable cancellations can be avoided. To incorporate delays, we expand the underlying recovery network with retiming possibilities. This leads to a problem formulation that can be solved using Lagrangian relaxation. As the network gets too large, we propose an iterative neighborhood exploration heuristic to solve the VRSPRT. This heuristic allows retiming for a subset of trips, and adds promising trips to this subset as the algorithm continues. Computational results indicate that the heuristic performs well. While requiring acceptable additional computation time, the iterative heuristic finds improvement over solutions that do not allow retiming in one third of the tested instances. By delaying only one or two trips with on average 4 minutes, the average number of cancelled trips is reduced with over 30 percent.