Superadditivity properties and new valid inequalities for the vehicle routing problem with stochastic demands

Robin Legault, Panca Jodiawan, Jean-François Côté, Leandro C. Coelho · 2025

Read Superadditivity properties and new valid inequalities for the vehicle routing problem with stochastic demands by Robin Legault, Panca Jodiawan, Jean-François Côté, Leandro C. Coelho (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-05877.txt.

Introduction

Robin Legault and co-authors study in 2025 delivery routing when customer demand is random. A split method that prices recourse by customer recently beat older aggregate forms. Whether the split works under other fallback policies stayed open until now.

A property called superadditivity turns out to license the split. The property holds under optimal restocking, and a flawed proof for the depot-return policy gets repaired. New edge-set cuts generalize the split cuts with structural gains. Their solver beats rivals at high customer-to-vehicle ratios and closes fourteen open cases. Long-run bounds on best cost round out the theory side of the work.

Catalog record

CREATORRobin Legault, Panca Jodiawan, Jean-François Côté, Leandro C. Coelho
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-05877

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Superadditivity properties and new valid inequalities for the vehicle routing problem with stochastic demands Robin Legault, Panca Jodiawan, Jean-François Côté, Leandro C. Coelho Abstract Over the past thirty years, the vehicle routing problem with stochastic demands has emerged as a canonical application of the integer L-shaped method, leading to an extensive body of literature and several methodological refinements. Recently, the disaggregated integer L-shaped (DL-shaped) method, which decomposes the recourse function by customer rather than treating it as an aggregate cost, has been proposed and successfully applied under the detour-to-depot recourse policy. However, the validity of this new approach and its generalizability to other policies have not been thoroughly investigated. In this work, we provide a necessary and sufficient condition for the validity of the DL-shaped method, namely, the superadditivity of the recourse function under concatenation. We demonstrate that the optimal restocking policy satisfies this superadditivity property. Moreover, we rectify an incorrect argument from the original paper on the DL-shaped method to rigorously establish its validity under the detour-to-depot policy. We then develop a DL-shaped algorithm tailored to the optimal restocking policy. Our algorithm exploits new dynamic programming-based lower bounds on the optimal restocking recourse function. We also introduce new valid inequalities that generalize the original DL-shaped cuts and speed up computations by an order of magnitude. Computational experiments show that our DL-shaped algorithm significantly outperforms the state-of-the-art integer L-shaped algorithm from the literature. We solve several open instances to optimality, including 14 single-vehicle instances, which constitute the most challenging variant of the problem. Keywords: Vehicle routing problem, Stochastic demands, Optimal restocking, Integer L-shaped method, Superadditivity 1 Introduction Since the seminal work of Tillman 1969 , the vehicle routing problem with stochastic demands (VRPSD) has been extensively studied ( Oyola et al. 2017 , Oyola et al. 2018 ) . The VRPSD can be described as the problem of designing routes for vehicles of limited capacity to serve, at minimal expected cost, a set of random demands whose realization is only observed upon arrival at the customer location. The present work considers the standard VRPSD, which models a homogeneous fleet, a single depot, and no time windows. We study the problem under the a priori optimization framework ( Bertsimas et al. 1990 ) , i.e., the routes are designed before the observation of the demands, and each vehicle can perform restocking trips to the depot along its route. The actions that can be taken to anticipate or react to a stockout are defined by a recourse policy. In the classical , or detour-to-depot (DTD) policy ( Dror et al. 1989 ) , the only available action is to perform a round trip to the depot when a failure occurs, i.e., the demand of the current customer exceeds the vehicle’s residual capacity. Alternatively, in the optimal restocking (OR) policy ( Yee and Golden 1980 , Yang et al. 2000 ) , after serving each customer, vehicles also have the option of performing a preventive trip to the depot before traveling to the next customer. Exact algorithms for the VRPSD Over the last three decades, a rich body of exact algorithms has been developed to solve the VRPSD under the DTD and OR policies. These algorithms can be divided into integer L-shaped methods ( Gendreau et al. 1995 , Hjorring and Holt 1999 , Laporte et al. 2002 , Jabali et al. 2014 , Louveaux and Salazar-González 2018 , Salavati-Khoshghalb et al. 2019 , Hoogendoorn and Spliet 2023 , Parada et al. 2024 , Hoogendoorn and Spliet 2025 ) and branch-price-and cut (BP&C) methods ( Christiansen and Lysgaard 2007 , Gauvin et al. 2014 , Florio et al. 2020a , Florio et al. 2023 ) . Integer L-shaped approaches model the VRPSD as a two-stage stochastic program and rely on edge-flow or arc-flow formulations. Within a branch-and-cut (B&C) framework, they iteratively generate valid inequalities that tighten the approximation of the recourse function and characterize feasible routes. On the other hand, BP&C methods embed column generation inside a branch-and-bound (B&B) tree. The master problem is a set-partitioning model whose columns represent complete routes. At each iteration, a resource-constrained shortest-path problem ( Irnich and Desaulniers 2005 ) is solved to identify a new route with negative reduced costs. Although both integer L-shaped and BP&C algorithms operate within a B&B framework, their computational bottlenecks differ fundamentally, resulting in complementary performance profiles. In integer L-shaped algorithms, most of the effort is spent repeatedly solving the linear programming (LP) relaxation of the relaxed master problem, which becomes increasingly complex as more cuts are generated. Computational efficiency therefore relies on devising valid inequalities that rapidly tighten the master problem, thereby limiting the number of explored nodes. In comparison, the main computational burden in BP&C methods lies in solving an NP-hard pricing problem ( Ota and Fukasawa 2025 ) at each iteration. In state-of-the-art BP&C algorithms, this pricing subproblem is solved via backward labeling, where each label represents a partial path from a customer back to the depot. The worst-case number of labels generated grows exponentially with the maximum number of customers that can be visited on a route, and the computational cost of extending each label scales linearly with both the vehicle capacity and the cardinality of the random demand supports. Thus, recent developments in BP&C methods for the VRPSD largely focus on techniques designed to limit label proliferation, notably dominance rules and reduced-cost bounds. The BP&C methods of Florio et al. 2020a , Florio et al. 2023 , which leverage effective labeling strategies and benefit from the tight LP relaxation provided by the set-partitioning formulation of the VRPSD, achieve state-of-the-art results on instances characterized by many short routes and moderate vehicle capacities. However, when optimal solutions consist of only a few routes, the decomposition benefit of column generation weakens significantly, as each column encapsulates a substantial portion of the decisions that form a feasible solution. Notably, in the single-vehicle scenario, the set-partitioning formulation collapses to solving a single resource-constrained shortest-path problem. Reflecting a structural similarity with the traveling salesman problem, where the best-performing exact methods are based on edge-flow formulations strengthened by cutting planes ( Applegate 2006 ) , integer L-shaped algorithms remain the state of the art for instances involving a small number of long routes. Integer L-shaped algorithms Traditional integer L-shaped methods for the VRPSD model the expected recourse cost using a single auxiliary variable, which is progressively tightened using valid inequalities. In the VRPSD literature, these inequalities have typically been categorized as either optimality cuts or lower bounding functionals (LBFs), although both types can be described as optimality cuts from a broader Benders decomposition perspective ( Hooker 2023 ) . Optimality cuts denote valid inequalities that are tight at the current solution or explicitly exclude the current solution from the feasible domain, whereas LBFs are more general lower bounds that can be active 1. 1. endnote: 1. As customary in the VRPSD literature, we say that an optimality cut or a LBF is active at a first-stage solution if it imposes a strictly positive bound on its recourse cost. over a larger subset of the feasible domain. Optimality cuts alone are sufficient to ensure convergence of the algorithm. However, they are typically active for a

Read the complete text