Program > By author > Rei Walter

In this paper we propose a local branching matheuristic for the vehicle routing problem with stochastic demands (VRPSD). The actual demands are revealed upon arrival at customer locations. In this setting, a failure may occur if a vehicle does not have sufficient capacity to serve the observed demand of a customer. In the event of a failure, a recourse action is performed by having the vehicle return to the depot, replenish its capacity and resume its planned route at the point of failure. Thus, the objective of the VRPSD is to minimize the sum of the planned routes cost and of the expected recourse cost. Considering a local branching framework, we introduce an intensification procedure applied at each node of the local branching tree. We design a diversification strategy. Finally, we dynamically allocate the computation time within the branching tree. Extensive computational results demonstrate the effectiveness our matheuristic when compared to the optimal solutions.