| Article ID: | iaor19982732 |
| Country: | United States |
| Volume: | 7 |
| Issue: | 1 |
| Start Page Number: | 1 |
| End Page Number: | 9 |
| Publication Date: | Dec 1995 |
| Journal: | INFORMS Journal On Computing |
| Authors: | Miller Donald L. |
| Keywords: | programming: branch and bound |
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.