A new scatter search design for multiobjective combinatorial optimization with an application to facility location

Abstract

Scatter search (SS) is a well-established metaheuristic solution methodology that has seen most of its success in single-objective optimization. The literature includes a few examples of the SS methodology adapted to multiobjective optimization, almost all dealing with continuous, nonlinear problems. We describe an SS design that we believe has general applicability in the area of multiobjective combinatorial optimization and show its effectiveness by applying it to a facility location problem. Facility location consists of identifying the best locations for a set of facilities. The set of best locations may vary substantially according to the objective function employed to solve the optimization problem.We employ a facility location problem with multiple objectives (mo-FLP) to test our design ideas for a multiobjective optimization scatter search. We focus on the objective functions associated with threewell-known location problems in the literature: the p-Median Problem (pMP), the Maximal Coverage Location Problem (MCLP), and the p-Center Problem (pCP). Our computational experiments are configured to show that the proposed SS design is capable of producing high-quality Pareto-front approximations.