Séminaire conjoint CIRRELT-Chaire de recherche industrielle du CRSNG/Hydro-Québec en optimisation stochastique de la production d’électricité-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport

TITRE : Improvements to the Integer L-shaped Algorithm for the Multi-Vehicle Routing Problem with Stochastic Demands

CONFÉRENCIER : Ola Jabali, École Polytechnique de Montréal, Canada

DATE et ENDROIT : 10 novembre 2011, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal

RESPONSABLE : Gilbert Laporte

RÉSUMÉ : We consider a variant of the VRP where customer demand is uncertain. This implies that the level of demand at each customer is revealed upon arrival to the customer. Given this characteristic, a vehicle may reach a client and then face the situation where the residual capacity is insufficient to serve the observed demand. Such a situation is referred to as a failure. The capacitated vehicle routing problem with stochastic demands (VRPSD) then consists of minimizing the total cost of the planned routes and the expected failures costs. We study the situation where a failure entails a return trip to the depot to reload the vehicle. The VRPSD is formulated as a two-stage stochastic programming model. We implement the integer L-shaped method for obtaining optimal solutions to the problem. We propose a generalized definition of partial routes to produce a series of lower bounding functional (LBF) cuts. An exact separation procedure is proposed to both identify general partial routes and produce a series of violated LBF cuts. As a consequence of the proposed strategies we are able to tackle larger instances of the problem.