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

G-84-02

Optimal Solutions to Capacitated Multidepot Vehicle Routing Problems

, et

This paper provides an integer linear programming formulation and an exact algorithm for a class of multidepot vehicle routing problems. This formulation contains degree constraints, subtour elimination constraints, chain barring constraints and integrality constraints. Integrality is obtained by branch and bound; subtour elimination and chain barring constraints are first relaxed and only imposed when they are found to be violated. Computational results are reported.

, 10 pages