Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGuimarans, Daniel-
dc.contributor.authorRiera Terrén, Daniel-
dc.contributor.authorJuan Pérez, Ángel Alejandro-
dc.contributor.authorRamos González, Juan José-
dc.contributor.otherUniversitat Autònoma de Barcelona-
dc.contributor.otherUniversitat Oberta de Catalunya (UOC)-
dc.identifier.citationGuimarans, D., Herrero, R., Riera-Terrén, D., Juan, A.A. & Ramos, J. (2011). Combining probabilistic algorithms, Constraint Programming and Lagrangian Relaxation to solve the vehicle routing problem. Annals of Mathematics and Artificial Intelligence, 62(3), 299-315. doi: 10.1007/s10472-011-9261-y-
dc.description.abstractThis paper presents an original hybrid approach to solve the Capacitated Vehicle Routing Problem (CVRP). The approach combines a Probabilistic Algorithm with Constraint Programming (CP) and Lagrangian Relaxation (LR). After introducing the CVRP and reviewing the existing literature on the topic, the paper proposes an approach based on a probabilistic Variable Neighbourhood Search (VNS) algorithm. Given a CVRP instance, this algorithm uses a randomized version of the classical Clarke and Wright Savings constructive heuristic to generate a starting solution. This starting solution is then improved through a local search process which combines: (a) LR to optimise each individual route, and (b) CP to quickly verify the feasibility of new proposed solutions. The efficiency of our approach is analysed after testing some well-known CVRP benchmarks. Benefits of our hybrid approach over already existing approaches are also discussed. In particular, the potential flexibility of our methodology is highlighted.en
dc.publisherAnnals of Mathematics and Artificial Intelligence-
dc.relation.ispartofAnnals of Mathematics and Artificial Intelligence, 2011, 62(3)-
dc.rights(c) Author/s & (c) Journal-
dc.subjecthybrid algorithmsen
dc.subjectvariable neighborhood searchen
dc.subjectvehicle routing problemen
dc.subjectprobabilistic algorithmsen
dc.subjectalgoritmos híbridoses
dc.subjectproblema de rutas de vehículoses
dc.subjectalgoritmos probabilísticoses
dc.subjectalgorismes híbridsca
dc.subjectproblema de rutes de vehiclesca
dc.subjectalgorismes probabilísticsca
dc.subjectbúsqueda de vecindad variablees
dc.subjectcerca de veïnatge variableca
dc.titleCombining probabilistic algorithms, Constraint Programming and Lagrangian Relaxation to solve the vehicle routing problem-
Appears in Collections:Articles

Files in This Item:
File Description SizeFormat 
AMAI_D_10_00050R2_Guimarans_et_al.pdf278.61 kBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons