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

Walter Rei (), Michel Gendreau () and Patrick Soriano ()
Additional contact information
Walter Rei: Département de Management et Technologie, École des Sciences de la Gestion, Université du Québec à Montréal, C.P. 8888, succ. Centre-ville, Montréal, Québec H3C 3P8, Canada, and Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport (CIRRELT), C.P. 6128, succ. Centre-ville, Montréal, Québec H3C 3J7, Canada
Michel Gendreau: Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal, C.P. 6079, succ. Centre-ville, Montréal, Québec H3C 3J7, Canada, and Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport (CIRRELT), C.P. 6128, succ. Centre-ville, Montréal, Québec H3C 3J7, Canada
Patrick Soriano: Service des Méthodes Quantitatives de Gestion, HEC Montréal, 3000 Chemin de la Côte Sainte-Catherine, Montréal, Québec H3T 2A7, Canada, and Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport (CIRRELT), C.P. 6128, succ. Centre-ville, Montréal, Québec H3C 3J7, Canada

Transportation Science, 2010, vol. 44, issue 1, 136-146

Abstract: We present a new algorithm that uses both local branching and Monte Carlo sampling in a multidescent search strategy for solving 0-1 integer stochastic programming problems. This procedure is applied to the single-vehicle routing problem with stochastic demands. Computational results show the effectiveness of this new approach to solving hard instances of the problem. This paper was accepted by former Editor-in-Chief Hani Mahmassani.

Keywords: local branching; Monte Carlo sampling; stochastic vehicle routing problems (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1090.0295 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:44:y:2010:i:1:p:136-146

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().