Models, relaxations and exact approaches for the capacitated vehicle routing problem (Q697581)

The authors review exact algorithms based on branch-and-bound for the solution of the vehicle routing problem, in which only the vehicle capacity constraints are considered. The contents of this paper (for the asymmetric and symmetric case, respectively) can be resumed by the following key-words: the assignment lower bound, bounds based on arborescences, the disjunctive lower bound, the lower bound based on min-cost flow, branch-and-bound algorithms; the lower bound based on trees, on matching, the Lagrangian lower bounds, bounds based on a set partitioning formulation, branching schemes and overall algorithms. The authors present computational results and conclude with future directions of research.