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

Publication date2003
Place of PublicationLancaster University
PublisherThe Department of Management Science
Number of pages0
<mark>Original language</mark>English

Publication series

NameManagement Science Working Paper Series


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.