A Variable Neighbourhood Search combining Constraint Programming and Lagrangean Relaxation for solving routing problems

Rosa Herrero, Daniel Guimarans, Juan José Ramos, Silvia Padrón

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

1 Citation (Scopus)

Abstract

This paper presents a methodology based on the Variable Neighbourhood Search metaheuristic, applied to the Capacitated Vehicle Routing Problem. The presented approach uses Constraint Programming and Lagrangean Relaxation methods in order to improve algorithm"s efficiency. The complete problem is decomposed into two separated submodels, to which the mentioned techniques are applied to obtain a complete solution. With this decomposition, the methodology provides a quick initial solution which is rapidly improved by means of metaheuristics" iterative process. Constraint Programming and Lagrangean Relaxation are also embedded within this structure, in order to ensure constraints satisfaction and to reduce the calculation burden. Remarkable results have been obtained using this methodology, including a new best-known solution for a rarely solved 200-customers test instance and a better alternative solution for another benchmark problem.

Original languageEnglish
Title of host publicationSummer Computer Simulation Conference, SCSC 2010 - Proceedings of the 2010 Summer Simulation Multiconference, SummerSim 2010
PublisherSociety for Computer Simulation International
Pages379-386
Number of pages8
ISBN (Print)9781617387029
Publication statusPublished - 2010
Externally publishedYes
EventSummer Computer Simulation Conference, SCSC 2010, Part of the 2010 Summer Simulation Multiconference, SummerSim 2010 - Ottawa, Canada
Duration: 12 Jul 201014 Jul 2010

Conference

ConferenceSummer Computer Simulation Conference, SCSC 2010, Part of the 2010 Summer Simulation Multiconference, SummerSim 2010
CountryCanada
CityOttawa
Period12/07/1014/07/10

Keywords

  • Constraint Programming
  • Hybrid Algorithms
  • Lagrangean Relaxation
  • Variable Neighbourhood Search
  • Vehicle Routing

Cite this