Technical Note—The Complexity of the Pricing Problem of the Set Partitioning Formulation of Vehicle Routing Problems
证明了车辆路径问题集划分形式中的定价问题是强NP难的，除非P=NP，否则不存在伪多项式或多项式时间算法，这为常见的松弛做法提供了理论依据。
The pricing problem of vehicle routing problems is strongly NP hard. Many algorithms for finding optimal solutions to various vehicle routing problems rely on a subroutine to solve a so-called pricing problem of a set partitioning formulation. Only exponential time algorithms are known for these pricing problems. Therefore, the set partitioning formulation is oftentimes relaxed at the expense of weaker LP bounds, so that the resulting pricing problem can now be solved using a pseudopolynomial or polynomial time algorithm. In “The Complexity of the Pricing Problem of the Set Partitioning Formulation of Vehicle Routing Problems,” it is proven by Remy Spliet that the pricing problem is strongly NP hard for many different vehicle routing problems. This means that, unless P = NP, no pseudopolynomial or polynomial time algorithm exists for the pricing problem, justifying the common use of relaxations.