Technical Note—The Complexity of the Pricing Problem of the Set Partitioning Formulation of Vehicle Routing Problems
Operations Research · 2023 · Volume 71 · Issue 5
Abstract
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.
Keywords
Transportation, vehicle routing problem, column generation, complexity theory
Enable JavaScript for citation tools and additional paper interactions.