A branch and bound algorithm for the multiple depot vehicle scheduling problem

TLDR

The Vehicle Scheduling Problem assigns time‑tabled trips to vehicles to minimize cost, and the NP‑hard Multiple Depot variant adds vehicle‑to‑depot assignment. The study proposes a branch‑and‑bound algorithm for the Multiple Depot Vehicle Scheduling Problem. The algorithm employs assignment‑relaxation and connectivity‑based lower bounds, a strong dominance procedure derived from new criteria, and a branch‑and‑bound framework. Computational results are presented.

Abstract

Abstract The Vehicle Scheduling Problem concerns the assigning of a set of time‐tabled trips to vehicles so as to minimize a given cost function. We consider the NP‐hard Multiple Depot case in which, in addition, one has to assign vehicles to depots. Different lower bounds based on assigment relaxation and on connectivity constraints are presented and combined in an effective bounding procedure. A strong dominance procedure derived from new dominance criteria also described. A branch and bound algorithm is finally proposed. Computational results are given.