Group for Research in Decision Analysis

G-2018-41

Exact branch-price-and-cut algorithms for vehicle routing

, , and

Vehicle routing problems (VRPs) are among the most studied problems in operations research. Nowadays, the leading exact algorithms for solving many classes of VRPs are branch-price-and-cut algorithms. In this survey paper, we highlight the main methodological and modeling contributions made over the years on branch-and-price(-and-cut) algorithms for VRPs, whether they are generic or specific to a VRP variant. We focus on problems related to the classical VRP, i.e., problems in which customers must be served by several capacitated trucks, and which are not combinations of a VRP and another optimization problem.

, 52 pages