Title:
|
Combining constraint programming, lagrangean relaxation and probabilistic algorithms to solve the vehicle routing problem
|
Author:
|
Guimarans, D; Herrero, R; Riera, D; Juan Pérez, Angel Alejandro; Ramos, J
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada I |
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:
|
Peer Reviewed |
Subject(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa -Operations research -Programming (Mathematics) -Investigació operativa -Programació (Matemàtica) -Classificació AMS::90 Operations research, mathematical programming |
Rights:
|
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
Document type:
|
Article - Published version Article |
Share:
|
|