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

J. Manuel Colmenar, Peter Greistorfer, Rafael Martí and Abraham Duarte

European Journal of Operational Research, 2016, vol. 252, issue 2, 432-442

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.

Keywords: Obnoxious location; Diversity problem; Metaheuristics; GRASP; Filter solutions (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716000928
Full text for ScienceDirect subscribers only

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:eee:ejores:v:252:y:2016:i:2:p:432-442

DOI: 10.1016/j.ejor.2016.01.047

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().