Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10609/90886
Título : | Combining probabilistic algorithms, Constraint Programming and Lagrangian Relaxation to solve the vehicle routing problem |
Autoría: | Guimarans, Daniel Riera Terrén, Daniel Juan, Angel A. Ramos González, Juan José |
Otros: | Universitat Autònoma de Barcelona (UAB) Universitat Oberta de Catalunya (UOC) |
Citación : | 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 |
Resumen : | 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. |
Palabras clave : | algoritmos híbridos problema de rutas de vehículos algoritmos probabilísticos búsqueda de vecindad variable |
DOI: | 10.1007/s10472-011-9261-y |
Tipo de documento: | info:eu-repo/semantics/article |
Versión del documento: | info:eu-repo/semantics/submittedVersion |
Fecha de publicación : | jun-2011 |
Licencia de publicación: | https://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
Aparece en las colecciones: | Articles cientÍfics Articles |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
AMAI_D_10_00050R2_Guimarans_et_al.pdf | 356,12 kB | Adobe PDF | Visualizar/Abrir |
Comparte:
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons