An improved integer L-shaped method for the vehicle routing problem with stochastic demands

We present an improved integer L-shaped method for the vehicle routing problem, which allows us to solve 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. Secondly, we improve valid inequalities known as partial route inequalities. Finally, we introduce three new types of valid inequalities. Additionally, we analyze two curious modeling choices which are common in the literature. First, we prove that imposing the use of a fixed number of routes can result in an arbitrarily large increase in the optimal objective value, and we prove the same result for additionally imposing that the expected demand on a route may not exceed the capacity. Secondly, our algorithm enables us to perform numerical experiments  to illustrate the decrease in computation time, and increase of the optimal solution value which result from imposing these constraints for benchmark instances.

Zoom link: https://eur-nl.zoom.us/j/95156986071?pwd=NmhWa2pYbWRoL3F1SWtxcElGZUhOQT09

Meeting ID: 951 5698 6071