A Hybrid Scatter Search Algorithm to Solve the Capacitated Arc Routing Problem with Refill Points

Carlos Alberto Franco Franco, Germán Andrés Mendez Giraldo, eduyn ramiro Lopéz-Santana

Resultado de la investigación: Contribución a Revista

1 Cita (Scopus)

Resumen

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.
Idioma originalEnglish (US)
Páginas (desde-hasta)3-15
Número de páginas13
PublicaciónLecture Notes in Computer Science
Volumen9772
EstadoPublished - jul 12 2016

Huella dactilar

Arc Routing
Scatter Search
Routing Problem
Search Algorithm
Iterated Local Search
Integer Linear Programming
Hybrid Algorithm
Real-world Applications
Simulated annealing
Simulated Annealing
Linear programming
Programming Model
Linear Model
Arc of a curve
Objective function
Minimise
Costs

Citar esto

@article{2766209f312a4a72b6de5bbcdbeacf28,
title = "A Hybrid Scatter Search Algorithm to Solve the Capacitated Arc Routing Problem with Refill Points",
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.",
author = "{Franco Franco}, {Carlos Alberto} and {Mendez Giraldo}, {Germ{\'a}n Andr{\'e}s} and Lop{\'e}z-Santana, {eduyn ramiro}",
year = "2016",
month = "7",
day = "12",
language = "English (US)",
volume = "9772",
pages = "3--15",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer",

}

A Hybrid Scatter Search Algorithm to Solve the Capacitated Arc Routing Problem with Refill Points. / Franco Franco, Carlos Alberto; Mendez Giraldo, Germán Andrés ; Lopéz-Santana, eduyn ramiro.

En: Lecture Notes in Computer Science, Vol. 9772, 12.07.2016, p. 3-15.

Resultado de la investigación: Contribución a Revista

TY - JOUR

T1 - A Hybrid Scatter Search Algorithm to Solve the Capacitated Arc Routing Problem with Refill Points

AU - Franco Franco, Carlos Alberto

AU - Mendez Giraldo, Germán Andrés

AU - Lopéz-Santana, eduyn ramiro

PY - 2016/7/12

Y1 - 2016/7/12

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

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

M3 - Conference article

VL - 9772

SP - 3

EP - 15

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -