An Improved Integer L-Shaped Method for the Vehicle Routing Problem with Stochastic Demands
提出一种改进的整数L形方法，相比现有最优方法提速高达325倍，解决了153个此前未解的基准实例，通过修正技术问题、改进部分路径不等式并引入三类新有效不等式实现。
We present an improved integer L-shaped method for the vehicle routing problem with stochastic demands. It exhibits speedups up to a factor of 325 compared with the current state-of-the-art, which allows us to solve 153 previously unsolved benchmark instances to optimality. The algorithm builds on the state-of-the-art in a few ways. First, we rectify a few technical issues found in the current literature. Second, we improve valid inequalities known as partial route inequalities. Finally, we introduce three new types of valid inequalities. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online appendices are available at https://doi.org/10.1287/ijoc.2023.1271 .