The efficiency of indicator‐based local search for multi‐objective combinatorial optimisation problems

In the last few years, a significant number of multi‐objective metaheuristics have been proposed in the literature in order to address real‐world problems. Local search methods play a major role in many of these metaheuristic procedures. In this paper, we adapt a recent and popular indicator‐based selection method proposed by Zitzler and Künzli in 2004, in order to define a population‐based multi‐objective local search. The proposed algorithm is designed in order to be easily adaptable, parameter independent and to have a high convergence rate. In order to evaluate the capacity of our algorithm to reach these goals, a large part of the paper is dedicated to experiments. Three combinatorial optimisation problems are tested: a flow shop problem, a ring star problem and a nurse scheduling problem. The experiments show that our algorithm can be applied with success to different types of multi‐objective optimisation problems and that it outperforms some classical metaheuristics. Furthermore, the parameter sensitivity analysis enables us to provide some useful guidelines about how to set the parameters.