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

G-86-10

Cutting Planes Based on Bin Packing Solutions for the Capacitate Vehicle Routing Problem

, et

This paper presents an integer linear programming formulation for the symmetrical capacitated vehicle routing problem (CVRP). This formulation includes degree constraints, integrality constraints and subtour elimination constraints based on bin packing solutions. The bin packing solutions are also used to derive comb inequalities for the CVRP. Computational results are reported.

, 18 pages