The Vehicle Rescheduling Problem with Retiming

Abstract

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

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 8 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.