Program > By author > Rei Walter

A Local Branching Matheuristic for the Multi-Vehicle Routing Problem with Stochastic Demands
Ola Jabali  1, 2, *@  , Florent Hernandez  1, 3, *@  , Michel Gendreau  1, 3, *@  , Walter Rei  1, 4, *@  
1 : Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport  (CIRRELT)  -  Website
Pavillon André-Aisenstadt, bureau 3520 2920, Chemin de la Tour Montréal (Québec) H3T 1J4 CANADA -  Canada
2 : HEC Montréal
3 : Ecole Polytechnique de Montreal  (EPM)  -  Website
Campus de l'Université de Montréal 2500, chemin de Polytechnique Montréal (Québec) H3T 1J4 -  Canada
4 : Université du Québec à Montréal - UQAM (CANADA)
* : Corresponding author

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.


Online user: 1