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

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.

This is a joint work with Remy Spliet.

Participation

If you would like to participate in the seminar, please send an email to the secretariat of Econometrics, eb-secr@ese.eur.nl.