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

G-83-18

Optimal Routing Under Capacity and Distance Restrictions

, et

This paper describes an integer linear programming algorithm for vehicle routing problems involving capacity and distance constraints. The method uses constraint relaxation and a new class of subtour elimination constraints. Two versions of the algorithm are presented, according to the nature of the distance matrix. Exact solutions are obtained for problems involving up to 60 cities.

, 27 pages

Ce cahier a été révisé en avril 1984