Please use this identifier to cite or link to this item:
Title: Combining probabilistic algorithms, Constraint Programming and Lagrangian Relaxation to solve the vehicle routing problem
Author: Guimarans, Daniel
Riera Terrén, Daniel  
Juan Pérez, Ángel Alejandro
Ramos González, Juan José
Others: Universitat Autònoma de Barcelona
Universitat Oberta de Catalunya (UOC)
Keywords: hybrid algorithms
variable neighborhood search
vehicle routing problem
probabilistic algorithms
Issue Date: Jun-2011
Publisher: Annals of Mathematics and Artificial Intelligence
Citation: Guimarans, 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
Project identifier: info:eu-repo/grantAgreement/HAROSA09
Also see:
Abstract: This 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.
Language: English
ISSN: 1012-2443MIAR
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