To access the full text documents, please follow this link: http://hdl.handle.net/2117/17339

Combining constraint programming, lagrangean relaxation and probabilistic algorithms to solve the vehicle routing problem
Guimarans, D; Herrero, R; Riera, D; Juan Pérez, Angel Alejandro; Ramos, J
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada I
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.
Peer Reviewed
À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
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/publishedVersion
Article
         

Show full item record

Related documents

Other documents of the same author

Juan Pérez, Angel Alejandro; Faulín, Javier; Jorba, Josep; Riera, D; Masip Rodó, David; Barrios, Barry
Ionescu, Dragos; Juan Pérez, Angel Alejandro; Faulín, Javier; Ferrer Biosca, Alberto
Mas, Sílvia; Juan Pérez, Angel Alejandro; Arias, Pol; Fonseca Casas, Pau
 

Coordination

 

Supporters