Constructive Heuristics for the Multicompartment Vehicle Routing Problem with Stochastic Demands

Jorge E. Mendoza (), Bruno Castanier (), Christelle Guéret (), Andrés L. Medaglia () and Nubia Velasco ()
Additional contact information
Jorge E. Mendoza: Équipe Optimisation des Systèmes de Production et Logistiques, LISA (EA CNRS 4094), Université Catholique de l'Ouest, 49008 Angers, France
Bruno Castanier: Équipe Systèmes Logistiques et de Production, IRCCyN (UMR CNRS 6597), École des Mines de Nantes, 44307 Nantes Cedex 3, France
Christelle Guéret: Équipe Systèmes Logistiques et de Production, IRCCyN (UMR CNRS 6597), École des Mines de Nantes, 44307 Nantes Cedex 3, France
Andrés L. Medaglia: Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, AA 4976 Bogotá, Colombia
Nubia Velasco: Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, AA 4976 Bogotá, Colombia

Transportation Science, 2011, vol. 45, issue 3, 346-363

Abstract: The vehicle routing problem with stochastic demands (VRPSD) consists of designing transportation routes of minimal expected cost to satisfy a set of customers with random demands of known probability distribution. This paper tackles a generalization of the VRPSD known as the multicompartment VRPSD (MC-VRPSD), a problem in which each customer demands several products that, because of incompatibility constraints, must be loaded in independent vehicle compartments. To solve the problem, we propose three simple and effective constructive heuristics based on a stochastic programming with recourse formulation. One of the heuristics is an extension to the multicompartment scenario of a savings-based algorithm for the VRPSD; the other two are different versions of a novel look-ahead heuristic that follows a route-first, cluster-second approach. In addition, to enhance the performance of the heuristics these are coupled with a post-optimization procedure based on the classical 2-Opt heuristic. The three algorithms were tested on instances of up to 200 customers from the MC-VRPSD and VRPSD literature. The proposed heuristics unveiled 26 and 12 new best known solutions for a set of 180 MC-VRPSD problems and a 40-instance testbed for the VRPSD, respectively.

Keywords: vehicle routing; stochastic demands; stochastic programming; look-ahead heuristics; multicompartment vehicle routing (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1100.0353 (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:45:y:2011:i:3:p:346-363

Access Statistics for this article

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