VI ALIO/EURO Workshop on Applied Combinatorial Optimization

December 15 - 17, 2008, Buenos Aires, Argentina

Local Branching-Based Solution Methods for the Vehicle Routing Problem with Stochastic Demands

Michel Gendreau

Département d’informatique et de recherche opérationnelle and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT)

Université de Montréal

C.P. 6128, Succursale Centre-ville, Montreal, H3C 3J7, Canada

The Vehicle Routing Problem with Stochastic Demands (VRPSD) consists in finding tours for a fleet of capacitated vehicles delivering goods to a set of customers with stochastic demands. A key feature of the problem is that the cumulative demand of the customers assigned to a vehicle may turn out to exceed its capacity, a situation defined as a route failure. The traditional approach to deal with failures is reactive in nature and involves sending the involved vehicle back to the depot to replenish its stock whenever a failure is detected. More proactive approaches consider having vehicles perform preventive replenishment trips when the on-board stock becomes too low. In either case, the trips back to the depot increase the length of the routes effectively performed by the vehicles. The objective in the VRPSD is to find the set of routes that yields the lowest expected total cost when these trips to the depot are considered.

In this talk, we will present both an exact and a heuristic solution methods for the VRPSD. The exact method is only applicable, in its current form, to the reactive variant of the problem, while the heuristic approach is much more flexible and can also be adapted to proactive variants. Both methods rely heavily on concepts of the local branching approach proposed by Fischetti and Lodi to tackle mixed integer programs effectively. Computational results on a set of small to fairly large benchmark instances will be reported and discussed.

(Joint work with Walter Rei and Patrick Soriano)