A branch-and-cut algorithm for Vehicle Routing Problems

The authors present a branch-and-cut algorithm for the identical customer Vehicle Routing Problem. Transforming the problem into an equivalent Path-Partitioning Problem allows them to exploit its polyhedral structure and to generate strong cuts corresponding to facet-inducing inequalities. By using cuts defined by multistars, partial multistars and generalized subtour elimination constraints, the authors are able to consistently solve 60-city problems to proven optimality and are currently attempting to solve problems involving a hundred cities. They also present details of the computer implementation and the present computational results.