Hardness of Pricing Routes for Two-Stage Stochastic Vehicle Routing Problems with Scenarios

Matheus J. Ota () and Ricardo Fukasawa ()
Additional contact information
Matheus J. Ota: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Ricardo Fukasawa: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada

Operations Research, 2025, vol. 73, issue 4, 2177-2187

Abstract: The vehicle routing problem with stochastic demands (VRPSD) generalizes the classic vehicle routing problem by considering customer demands as random variables. Similar to other vehicle routing variants, state-of-the-art algorithms for the VRPSD are often based on set-partitioning formulations, which require efficient routines for the associated pricing problems. However, all of these set partitioning–based approaches have strong assumptions on the correlation between the demands of random variables (e.g., no correlation), a simplification that diverges from real-world settings where correlations frequently exist. In contrast, there is a significant effort in the stochastic programming community to solve problems where the uncertainty is modeled with a finite set of scenarios. This approach can approximate more diverse distributions via sampling and is particularly appealing in data-driven contexts where historical data are readily available. To fill this gap, we focus on the VRPSD with demands given by scenarios. We show that for any route relaxation (where repeated visits are allowed in a route) and any approximation of the recourse cost that satisfies some mild assumptions, the VRPSD pricing problem is still strongly N P -hard. This provides a very strong argument for the difficulty of developing efficient column generation–based algorithms for the VRPSD with demands following an empirical probability distribution of scenarios.

Keywords: Optimization; vehicle routing; column generation; computational complexity; stochastic programming (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.0569 (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:73:y:2025:i:4:p:2177-2187

Access Statistics for this article

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