Combining Constraint Programming, Lagrangian Relaxation and probabilistic algorithms to solve the Vehicle Routing Problem

Daniel Guimarans, Rosa Herrero, Daniel Riera, Angel A. Juan, Juan José Ramos

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

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 multistart 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.

Original languageEnglish
Title of host publication17th RCRA 2010 Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion
PublisherRheinisch-Westfaelische Technische Hochschule Aachen
Number of pages18
Volume616
Publication statusPublished - 2010
Externally publishedYes
Event17th RCRA 2010 Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion - Bologna, Italy
Duration: 10 Jun 201011 Jun 2010

Publication series

NameCEUR Workshop Proceedings
PublisherRheinisch-Westfaelische Technische Hochschule Aachen * Lehrstuhl Informatik V
ISSN (Print)1613-0073

Conference

Conference17th RCRA 2010 Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion
CountryItaly
CityBologna
Period10/06/1011/06/10

Cite this