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

G-84-04

An Exact Algorithm for the Asymetrical Capacitated Vehicle Routing Problem

, et

The aim of this paper is to develop an exact algorithm for the asymmetrical capacitated vehicle routing problem, i.e. the multiple travelling salesman problem subject to capacity restrictions. The problem is solved by means of a branch and bound tree in which subproblems are modified assignment problems subject to some restrictions. Two branching rules and three partitioning rules are examined. Computational results for problems involving up to 260 nodes (cities) are reported.

, 23 pages

Ce cahier a été révisé en mai 1985