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

Arnaud Liefooghe 1, 2 Laetitia Jourdan 1, 2 El-Ghazali Talbi 1, 2
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : 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.
Type de document :
[Research Report] RR-6515, INRIA. 2008
Liste complète des métadonnées

Littérature citée [59 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 28 avril 2008 - 10:13:22
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mardi 21 septembre 2010 - 16:27:41


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00275659, version 2
  • ARXIV : 0804.3965


Arnaud Liefooghe, Laetitia Jourdan, El-Ghazali Talbi. Metaheuristics and Their Hybridization to Solve the Bi-objective Ring Star Problem: a Comparative Study. [Research Report] RR-6515, INRIA. 2008. 〈inria-00275659v2〉



Consultations de la notice


Téléchargements de fichiers