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

• 成果类型: Article
• 署名作者: Spliet, Remy
• 署名单位: Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.2481
• 发表日期: 2023
• 页码: 1454-1457
• 关键词: column generation; exact algorithm; cut; models

摘要

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 algo-rithms 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 justi-fies 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.