A dynamic approach to vehicle scheduling

This paper presents a dynamic approach to the vehicle scheduling problem. We discuss the potential benefit of our approach compared to the traditional one, where the vehicle scheduling problem is solved only once for a whole period and the travel times are assumed to be fixed. In our dynamic approach, we solve a sequence of optimization problems, where we take into account different scenarios for future travel times. Because in the multiple-depot case we cannot solve the problem exactly within reasonable computation time, we use a "cluster-reschedule" heuristic where we first assign trips to depots by solving the static problem and then solve dynamic single-depot problems. We use new mathematical formulations of these problems that allow a fast solution by standard optimization software. We report on the results of a computational study with real life data, in which we compare different variants of our approach and perform a sensitivity analysis with respect to deviations of the actual travel times from the estimated ones.