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é
|
Other authors:
|
Universitat Autònoma de Barcelona; Universitat Oberta de Catalunya (UOC) |
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. |
Subject(s):
|
-hybrid algorithms -variable neighborhood search -vehicle routing problem -probabilistic algorithms -algoritmos híbridos -problema de rutas de vehículos -algoritmos probabilísticos -búsqueda de vecindad variable -algorismes híbrids -problema de rutes de vehicles -algorismes probabilístics -cerca de veïnatge variable -Algorithms -Algorismes -Algoritmos |
Rights:
|
(c) Author/s & (c) Journal
|
Document type:
|
Article Article - Submitted version |
Published by:
|
Annals of Mathematics and Artificial Intelligence
|
Share:
|
|