Branching approaches for integrated vehicle and crew scheduling
Document Type
Journal Article
Publication Date
2009
Subject Area
operations - scheduling, infrastructure - vehicle
Abstract
The integrated multi-depot vehicle and crew scheduling problem simultaneously builds vehicle blocks and crew duties. We present an integer mathematical formulation that combines a multi-commodity flow model with a mixed set partitioning/covering model. We propose solution approaches that start by solving the linear programming relaxation of the model. Whenever the resulting linear programming solution is not integer, three branching alternative strategies can be applied: a branch-and-bound algorithm and two branch-and-price schemes. The branch-and-bound algorithm performs branching over the set of feasible crew duties generated while solving the linear relaxation. In the first branch-and-price scheme the linear programming relaxation is solved approximately, while in the second one it is solved exactly. Computational experience is reported over two different types of problems: randomly generated data publicly available for benchmarking in the Internet and data from a bus company operating in Lisbon.
Recommended Citation
Mesquita, M., Paias, A., & Respício, A. (2009). Branching approaches for integrated vehicle and crew scheduling Journal of Public Transport, Vol. 1, Issue, 1, Pp. 21-37.
