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

Remy Spliet ()
Additional contact information
Remy Spliet: Econometric Institute, Erasmus University Rotterdam, 3000 DR Rotterdam, Netherlands

Operations Research, 2023, vol. 71, issue 5, 1454-1457

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 (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.2481 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:5:p:1454-1457

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().