Technical Note—The Complexity of the Pricing Problem of the Set Partitioning Formulation of Vehicle Routing Problems

State-of-the-art exact algorithms for vehicle routing problems are branch-price-and-cut algorithms that make use of a set partitioning formulation. Only exponential time algorithms are known for the corresponding pricing problem. In this technical note, it is proven that the pricing problem is strongly NP-hard for various vehicle routing problems. This justifies the common use of route relaxations that modify the set partitioning formulation with the aim to allow pseudopolynomial pricing algorithms at the expense of a weaker LP bound.