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

A new branch-and-cut algorithm for the capacitated vehicle routing problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published
<mark>Journal publication date</mark>2004
<mark>Journal</mark>Mathematical Programming
Issue number2
Volume100
Number of pages23
Pages (from-to)423-445
Publication StatusPublished
<mark>Original language</mark>English

Abstract

We present a new branch-and-cut algorithm for the capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed capacity, generalized 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 (B-n50-k8, B-n66-k9 and B-n78-k10) of Augerat to optimality for the first time.