Metaheuristics for the bi-objective ring star problem

Citation

Liefooghe A, Jourdan L, Basseur M, Talbi E & Burke E (2008) Metaheuristics for the bi-objective ring star problem. In: van Hemert J & Cotta C (eds.) Evolutionary Computation in Combinatorial Optimization: 8th European Conference, EvoCOP 2008, Naples, Italy, March 26-28, 2008. Proceedings. Lecture Notes in Computer Science, 4972. 8th European Conference, EvoCOP 2008: » Evolutionary Computation in Combinatorial Optimization, Naples, Italy, 26.03.2008-28.03.2008. Berlin Heidelberg: Springer, pp. 206-217. http://link.springer.com/chapter/10.1007%2F978-3-540-78604-7_18; https://doi.org/10.1007/978-3-540-78604-7_18

Abstract
The bi-objective ring star problem aims to locate a cycle through a subset of nodes of a graph while optimizing two types of cost. The first criterion is to minimize a ring cost, related to the length of the cycle, whereas the second one is to minimize an assignment cost, from non-visited nodes to visited ones. In spite of its natural multi-objective formulation, this problem has never been investigated in such a way. In this paper, three metaheuristics are designed to approximate the whole set of efficient solutions for the problem under consideration. Computational experiments are performed on well-known benchmark test instances, and the proposed methods are rigorously compared to each other using different performance metrics.