Please use this identifier to cite or link to this item:

http://hdl.handle.net/10609/124086
Title: Combining constraint programming, lagrangian relaxation and probabilistic algorithms to solve the vehicle routing problem
Author: Guimarans Serrano, Daniel
Herrero, Rosa
Riera Terrén, Daniel  
Juan Pérez, Ángel Alejandro
Ramos González, Juan José
Others: Universitat Oberta de Catalunya (UOC)
Universitat Autònoma de Barcelona
Keywords: capacitated vehicle routing problem
constraint programming
lagrangian relaxation
probabilistic algorithms
Issue Date: 22-Jul-2010
Publisher: CEUR Workshop Proceedings
Citation: Guimarans, D., Herrero, R., Riera, D., Juan, A.A. & Ramos, J.J. (2010). Combining constraint programming, lagrangian relaxation and probabilistic algorithms to solve the vehicle routing problem. CEUR Workshop Proceedings, 616(), 1-18.
Published in: RCRA workshop, Bolonya, Itàlia, 10-11, juny de 2010
Project identifier: info:eu-repo/grantAgreement/HAROSA09
Also see: http://ceur-ws.org/Vol-616/
Abstract: This paper presents a hybrid approach that aims at solving the Capacitated Vehicle Routing Problem (CVRP) by means of combining Constraint Programming (CP) with Lagrangian Relaxation (LR) and Probabilistic Algorithms. After introducing the CVRP and reviewing the main literature in this area, the paper proposes the use of a multi-start hybrid Variable Neighbourhood Search (VNS) algorithm. This algorithm uses a randomised version of the classical Clarke and Wright savings heuristic to generate a starting solution to a given CVRP. 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. Some results on well-known CVRP benchmarks are analysed and discussed.
Language: English
URI: http://hdl.handle.net/10609/124086
ISSN: 1613-0073MIAR
Appears in Collections:Conference lectures

Share:
Export:
Files in This Item:
File SizeFormat 
Riera_Juan_CEUR_Combining.pdf175.71 kBAdobe PDFView/Open

Items in repository are protected by copyright, with all rights reserved, unless otherwise indicated.