A Hybrid Monte Carlo Local Branching Algorithm for the Single Vehicle Routing Problem 
with Stochastic Demands

Michel Gendreau(1, 2), Walter Rei(1, 3), and Patrick Soriano(1, 4)

1.	Centre interuniversitaire de recherche sur les réseaux d'entreprise, la logistique et le transport (CIRRELT)
	Université de Montréal 
	C.P. 6128, succursale Centre-ville, Montreal, Canada, H3C 3J7

2.	Département d'informatique et de recherche opérationnelle 
	Université de Montréal 
	C.P. 6128, succursale Centre-ville, Montreal, Canada, H3C 3J7

3.	Département de management et technologie, Université du Québec à Montréal
C.P. 8888, succursale Centre-ville, Montreal, Canada, H3P 3P8

4.	Service de l'enseignement des méthodes quantitatives de gestion
	HEC Montréal
	3000, chemin de la Côte Sainte-Catherine, Montreal, Canada, H3T 2A7


Abstract

We present a new algorithm that uses both local branching and Monte Carlo sampling in a multi-descent search strategy for solving approximately 0-1 integer stochastic programming problems. This procedure is applied to the single vehicle routing problem with stochastic demands. An interesting feature of the method in this case is that each descent is initiated from the solution of a traveling salesman problem with additional constraints. Computational results show the effectiveness of this new approach for solving hard instances of the problem.

Keywords: local branching, Monte Carlo sampling, stochastic vehicle routing problems.