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


An Optimal Algorithm for a General Class of Asymmetrical Vehicle Routing Problems

, et

This paper describes an exact algorithm for a general class of asymmetrical vehicle routing problems. Vehicle routes start and end at a central depot. Visits must be made to nodes grouped into clusters: every cluster must receive a minimum number of visits. But no all nodes must be visited: there are specified nodes and non-specified nodes. Vehicle routes are also constrained by capacity and distance restrictions. The problem is formulated as an integer linear program. It is then solved by a branch and bound algorithm which exploits the unimodular structure of the subproblems. Computational results are reported.

, 36 pages