| Popis: |
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 to the current state-of-the-art, 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 demand of the customers on a route may not exceed the capacity in expectation. 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. |
