Back to Search
Start Over
Combining probabilistic algorithms, Constraint Programming and Lagrangian Relaxation to solve the Vehicle Routing Problem.
- Source :
-
Annals of Mathematics & Artificial Intelligence . Dec2011, Vol. 62 Issue 3/4, p299-315. 17p. - Publication Year :
- 2011
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10122443
- Volume :
- 62
- Issue :
- 3/4
- Database :
- Academic Search Index
- Journal :
- Annals of Mathematics & Artificial Intelligence
- Publication Type :
- Academic Journal
- Accession number :
- 71112460
- Full Text :
- https://doi.org/10.1007/s10472-011-9261-y