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


Advances in Constrained Routing and Scheduling Problems

, et

The majority of vehicle routing and crew scheduling problems studied up to date in the literature can be formulated by means of a unified model introduced by Desaulniers et al.(1994) and Desrosiers et al.(1995). The first part of this paper presents an initial formulation of this model that describes it as a nonlinear generalization of a multi-commodity flow problem. The second section presents an equivalent decomposed formulation. This formulation takes advantage of the model's special structure to streamline its solution. Finally, the third and fourth sections analyze the two formulations in order to extend the apparent boundaries stemming from the mathematical programming structure and the decomposition and linearization process.

, 14 pages