Groupe d’études et de recherche en analyse des décisions


A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems

, , , , et

The need for an integrating framework for vehicle routing and crew scheduling problems has been apparent for some time. While several attempts have been made in this direction, they have stopped short of formally modeling several important practical complexities. This paper presents a more general model than previously considered which integrates all the different time constrained vehicle routing and crew scheduling problem types examined so far in the literature. This enables the reader to understand the common structure of these problems. It also allows to perceive the relations between the various problems, the different forms of the model used previously in the literature, and assorted applications across a unified formulation. To solve the multi-commodity problems in this class, the paper presents a branch-and-bound framework where the lower bounds are derived by using a decomposition approach. We focus on an extension of the Dantzig-Wolfe decomposition principle and establish that this is valid even for nonlinear objective functions and constraints. We also illustrate that it embeds the column generation-based methods previously suggested in the literature as special cases. The branching module used to obtain integer solutions compatible with column generation is more general, but yet simpler than other prior strategies. Finally, we examine the constrained Shortest Path Problems that appear at the subproblem level of the decomposition. The paper permits to see the variety of specialized dynamic programming algorithms that have been developed to solve these and more general single commodity problems and the aspects which have not yet received attention.

, 42 pages

Ce cahier a été révisé en novembre 1997