ACO and CP working together to build a flexible tool for the VRP

Negar ZakeriNejad, Daniel Riera, Daniel Guimarans

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

Abstract

In this paper a flexible hybrid methodology, combining Ant Colony Optimisation (ACO) and Constraint Programming (CP), is presented for solving Vehicle Routing Problems (VRP). The stress of this methodology is on the word 'flexible': It gives reasonably good results to changing problems without high solution redesign efforts. Thus a different problem with a new set of constraints and objectives requires no changes to the search algorithm. The search part (driven by ACO) and the model of the problem (included in the CP part) are separated to take advantage of their best attributes. This separation makes the application of the framework to different problems much simpler. To assess the feasibility of our approach, we have used it to solve different instances of the VRP family. These instances are built by combining different sets of constraints. The results obtained are promising but show that the methodology needs deeper communication between ACO and CP to improve its performance.

Original languageEnglish
Title of host publicationProceedings of 5th the International Conference on Operations Research and Enterprise Systems
EditorsBegona Vitoriano, Greg H. Parlier
Place of PublicationPortugal
PublisherScitepress
Pages122-129
Number of pages8
ISBN (Electronic)9789897581717
DOIs
Publication statusPublished - 2016
Externally publishedYes
EventInternational Conference on Operations Research and Enterprise Systems 2016 - Rome, Italy
Duration: 23 Feb 201625 Feb 2016
Conference number: 5th
http://www.icores.org/?y=2016

Conference

ConferenceInternational Conference on Operations Research and Enterprise Systems 2016
Abbreviated titleICORES 2016
CountryItaly
CityRome
Period23/02/1625/02/16
Internet address

Keywords

  • Ant colony optimisation
  • Constraint programming
  • Optimisation
  • Vehicle routing problem

Cite this