2008/04/24 by Arnaud Liefooghe, Liefooghe, Arnaud, Laëtitia Jourdan +5 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Multi-Objective Optimization Algorithms #Combinatorics (math.CO) #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #Vehicle Routing Optimization Methods #math.CO
paper · pdf · doi:10.48550/arxiv.0804.3965
openalex publication_date 2008/04/24 · arxiv created 2008/04/28 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.