Combining constraint programming, lagrangian relaxation and probabilistic algorithms to solve the vehicle routing problem
| Autor: | Daniel Guimarans, Herrero, R., Riera, D., Juan, A. A., Ramos, J. J. |
|---|---|
| Přispěvatelé: | Universitat Oberta de Catalunya (UOC), Universitat Autònoma de Barcelona |
| Předmět: |
lagrangian relaxation
constraint programming relaxació lagrangiana Algoritmos capacitated vehicle routing problem programación con restricciones Algorismes probabilistic algorithms problema d'enrutament de vehicles capacitats algoritmos probabilísticos problema de enrutamiento de vehículos capacitados programació amb restriccions algorismes probabilístics Algorithms relajación lagrangiana |
| Zdroj: | Scopus-Elsevier O2, repositorio institucional de la UOC Universitat Oberta de Catalunya (UOC) |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|