Home > Research > Publications & Outputs > A new branch-and-cut algorithm for capacitated ...
View graph of relations

A new branch-and-cut algorithm for capacitated vehicle routing problems

Research output: Working paper



We present a new branch-and-cut algorithm for the well-known capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed capacity, strengthened comb, multistar, partial multistar, extended hypotour inequalities, and classical Gomory mixed-integer cuts. For each of these classes of inequalities we describe our separation algorithms in detail. Also we describe the other important ingredients of our branch-and-cut algorithm, such as the branching rules, the node selection strategy, and the cut pool management. Computational results, for a large number of instances, show that the new algorithm is competitive. In particular, we solve three instances of Augerat to optimality for the first time.

Bibliographic note

This was eventually published as: J. Lysgaard, A.N. Letchford & R.W. Eglese (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program., 100(2), 423-445.