A New Scatter Search Design for Multiobjective Combinatorial Optimization with an Application to Facility Location

A. D. López-Sánchez (), J. Sánchez-Oro () and M. Laguna ()
Additional contact information
A. D. López-Sánchez: Pablo de Olavide University, 41013 Sevilla, Spain
J. Sánchez-Oro: Rey Juan Carlos University, 28933 Madrid, Spain
M. Laguna: Leeds School of Business, University of Colorado, Boulder, Colorado 80309

INFORMS Journal on Computing, 2021, vol. 33, issue 2, 629-642

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 three well-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. Summary of Contribution: Metaheuristic optimization is at the heart of the intersection between computer science and operations research. The INFORMS Journal on Computing has been fundamental in advancing the ideas behind metaheuristic methodologies. Fred Glover's Tabu Search–Part I was published more than 30 years ago in the first volume of the then ORSA Journal on Computing . This article, one of the most cited in the area of heuristic optimization, paved the way for many contributions to the methodology and practice of operations research. As a continuation of this stream of research, we describe a new scatter search design for multiobjective optimization. The design includes a short-term memory tabu search and a path relinking combination method. We show how the strategies and mechanisms within scatter search and tabu search can be combined to produce a highly effective approach to multiobjective optimization.

Keywords: multiobjective optimization; p -median; p -center; maximal coverage location; scatter search; path relinking; tabu search (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.0966 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:2:p:629-642

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().