A hybrid scatter search algorithm to solve the capacitated arc routing problem with refill points

Eduyn Ramiro López-Santana, Germán Andrés Méndez-Giraldo, Carlos Alberto Franco-Franco

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

This paper presents a hybrid scatter search algorithm to solve the capacitated arc routing problem with refill points (CARP-RP). The vehicle servicing arcs must be refilled on the spot by using a second vehicle. This problem is addressed in real-world applications in many services systems. The problem consists on simultaneously determining the vehicles routes that minimize the total cost. In the literature is proposed an integer linear programming model to solve the problem. We propose a hybrid algorithm based on Scatter Search, Simulated Annealing and Iterated Local Search. Our method is tested with instances from the literature. We found best results in the objective function for the majority instances.

Original languageEnglish (US)
Title of host publicationIntelligent Computing Theories and Application - 12th International Conference, ICIC 2016, Proceedings
EditorsDe-Shuang Huang, Kang-Hyun Jo
PublisherSpringer
Pages3-15
Number of pages13
ISBN (Print)9783319422930
DOIs
StatePublished - 2016
Externally publishedYes
Event12th International Conference on Intelligent Computing Theories and Application, ICIC 2016 - Lanzhou, China
Duration: Aug 2 2016Aug 5 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9772
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Conference on Intelligent Computing Theories and Application, ICIC 2016
CountryChina
CityLanzhou
Period8/2/168/5/16

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A hybrid scatter search algorithm to solve the capacitated arc routing problem with refill points'. Together they form a unique fingerprint.

Cite this