A Matching Based Exact Algorithm for Capacitated Vehicle Routing Problems

A branch and bound algorithm for capacitated vehicle routing is described. Lower bounds are derived by relaxing the subtour elimination and vehicle capacity constraints to yield a perfect b-matching problem. Bounds are strengthened by using Lagrange multipliers to enforce subtour elimination and capacity constraints. Computational results are reported for problems taken from the literature for sizes up to 61 vertices. With the exception of the 48 vertex instance (att48.vrp), the algorithm solves all problems in TSPLIB having 51 or fewer vertices.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.