Titre :

Metaheuristics and Their Hybridization to Solve the Bi-objective Ring Star Problem: a Comparative Study

Auteur(s) :

Liefooghe, Arnaud [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Jourdan, Laetitia [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Talbi, El-Ghazali [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]

Institution :

INRIA

Date de publication :

2008

Mot(s)-clé(s) en anglais :

Multi-objective combinatorial optimization
evolutionary algorithms
local exploration
hybrid approaches
routing

Discipline(s) HAL :

Mathématiques [math]/Combinatoire [math.CO]

Résumé en anglais : [en]

This paper presents and experiments approaches to solve a new bi-objective routing problem called the ring star problem. It consists of locating a simple cycle through a subset of nodes of a graph while optimizing two kinds ...
Lire la suite >This paper presents and experiments approaches to solve a new bi-objective routing problem called the ring star problem. It consists of locating a simple cycle through a subset of nodes of a graph while optimizing two kinds of cost. The first objective is the minimization of a ring cost that is related to the length of the cycle. The second one is the minimization of an assignment cost from non-visited nodes to visited ones. In spite of its obvious bi-objective formulation, this problem has always been investigated in a single-objective way. To tackle the bi-objective ring star problem, we first investigate different stand-alone search methods. Then, we propose two cooperative strategies that combines two multiple objective metaheuristics: an elitist evolutionary algorithm and a population-based local search. We apply this new hybrid approaches to well-known benchmark test instances and demonstrate their effectiveness in comparison to non-hybrid algorithms and to state-of-the-art methods.Lire moins >

Langue :

Anglais

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL