Advanced Greedy Randomized Adaptive Search Procedure for the Obnoxious p-Median Problem

TitleAdvanced Greedy Randomized Adaptive Search Procedure for the Obnoxious p-Median Problem
Publication TypeJournal Article
Year of Publication2016
AuthorsColmenar, J M., P. Greistorfer, R. Martí, and A. Duarte
JournalEuropean Journal of Operational Research
Volume252
Issue2
Start Page432
Pagination432-442
ISSN0377-2217
KeywordsDiversity problem, Filter solutions, GRASP, Metaheuristics, Obnoxious location
Abstract

The Obnoxious p-Median problem consists in selecting a subset of p facilities from a given set of possible locations, in such a way that the sum of the distances between each customer and its nearest facility is maximized. The problem is NP-hard and can be formulated as an integer linear program. It was introduced in the 1990s, and a branch and cut method coupled with a tabu search has been recently proposed. In this paper, we propose a heuristic method – based on the Greedy Randomized Adaptive Search Procedure, GRASP, methodology – for finding approximate solutions to this optimization problem. In particular, we consider an advanced GRASP design in which a filtering mechanism avoids applying the local search method to low quality constructed solutions. Empirical results indicate that the proposed implementation compares favorably to previous methods. This fact is confirmed with non-parametric statistical tests.

URLhttp://www.sciencedirect.com/science/article/pii/S0377221716000928
DOI10.1016/j.ejor.2016.01.047
Full text: