A disaggregated integer L-shaped method for stochastic vehicle routing problems with monotonic recourse

Lucas Parada, Robin Legault, Jean-François Côté and Michel Gendreau

European Journal of Operational Research, 2024, vol. 318, issue 2, 520-533

Abstract: This paper proposes a new integer L-shaped method for solving two-stage stochastic integer programs whose first-stage solutions can decompose into disjoint components, each one having a monotonic recourse function. In a minimization problem, the monotonicity property stipulates that the recourse cost of a component must always be higher or equal to that of any of its subcomponents. The method exploits new types of optimality cuts and lower bounding functionals that are valid under this property. The stochastic vehicle routing problem is particularly well suited to be solved by this approach, as its solutions can be decomposed into a set of routes. We consider the variant with stochastic demands in which the recourse policy consists of performing a return trip to the depot whenever a vehicle does not have sufficient capacity to accommodate a newly realized customer demand. This work shows that this policy can lead to a non-monotonic recourse function, but that the monotonicity holds when the customer demands are modeled by several commonly used families of probability distributions. We also present new problem-specific lower bounds on the recourse that strengthen the lower bounding functionals and significantly speed up the solving process. Computational experiments on instances from the literature show that the new approach achieves state-of-the-art results.

Keywords: Stochastic programming; Integer L-shaped method; Monotonic recourse; Vehicle routing problem (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724003497
Full text for ScienceDirect subscribers only

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:eee:ejores:v:318:y:2024:i:2:p:520-533

DOI: 10.1016/j.ejor.2024.05.012

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().