Benders-branch-and-cut for the vehicle routing problem with multiple deliverymen and stochastic demand

Abstract

In this research project, we intend to improve the benders-branch-and-cut algorithm developed in BEPE project of process 2017/06434-3 to effectively solve instances of reasonable size of the vehicle routing problem with time windows, multiple deliverymen and stochastic demand. The problem was formulated as a two-stage stochastic program with recourse. In the first stage, a set of routes is defined. In the second stage, recourse decisions or contingency actions are taken in order to mitigate the impact of demand uncertainties in the routes defined a priori. An exact solution method based on the benders-branch-and-cut algorithm was proposed to solve the problem. Computational experiments were done using the well known instances of Solomon in order to evaluate the computational performance of the proposed algorithm. Computational results revealed the difficulty of the benders-branch-and-cut algorithm to solve instances of reasonable size of the problem. Indeed, the algorithm could not prove optimality within a running time of 3600 seconds for instances with more than 25 customers and 20 scenarios. For this reason, the present research project aims to improve the performance of the benders-branch-and-cut algorithm developed in BEPE project of process 2017/06434-3 to effectively solve instances of reasonable size.