A parallel variable neighborhood search approach for the obnoxious p‐median problem

• DOI: http://doi.org/10.1111/itor.12510
• Author: Abraham Duarte,José M. Colmenar,Alberto Herrán,Rafael Martí
• Date: 01 January 2020
• Published date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 336–360

DOI: 10.1111/itor.12510

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A parallel variable neighborhood search approach

for the obnoxious p-median problem

Alberto Herr´

ana,Jos

´

e M. Colmenara, Rafael Mart´

ıband Abraham Duartea

aDepartment of Computer Sciences, Universidad ReyJuan Carlos, Madrid, Spain

bDepartamento de Estad´

ıstica e Investigaci´

on Operativa, Universidad de Valencia, Valencia, Spain

E-mail: alberto.herran@urjc.es [Herr´

an]; josemanuel.colmenar@urjc.es [Colmenar]; rafael.marti@uv.es [Mart´

ı];

abraham.duarte@urjc.es [Duarte]

Received 26 February2017; received in revised form 19 September 2017; accepted 23 December 2017

Abstract

The obnoxious p-median problem consists of selecting plocations, considered facilities, in a way that the

sum of the distances from each nonfacility location, called customers, to its nearest facility is maximized.

This is an NP-hard problem that can be formulated as an integer linear program. In this paper, we propose

the application of a variable neighborhood search (VNS) method to effectively tackle this problem. First,

we develop new and fast local search procedures to be integrated into the basic VNS methodology. Then,

some parameters of the algorithm are tuned in order to improve its performance. The best VNS variant

is parallelized and compared with the best previous methods, namely branch and cut, tabu search, and

GRASP over a wide set of instances. Experimental results show that the proposed VNS outperforms pre-

vious methods in the state of the art. This fact is finally confirmed by conducting nonparametric statistical

tests.

Keywords:obnoxious location; metaheuristics; VNS; parallel algorithms

1. Introduction

The obnoxious p-median problem, OpM (Church and Garfinkel, 1978; Erkut and Neuman, 1989),

belongs to the category of facility location problems(Francis and White, 1974). More precisely, it is

derived from the p-median problems (Hakimi, 1964) that, for fixed values of p, they can be solved

in polynomial time. On the other hand, they become strongly NP-hard for variable value s of p

(Current et al., 2004).

In OpM,pidentifies facilities that are actually opened, whereas the rest ones are consid-

ered as unopened facilities. In addition, it considers the open facilities to be obnoxious. That

is, they correspond to real-world facilities that are usually noisy, dangerous, or disgusting

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

A. Herr´

an et al. / Intl. Trans. in Op. Res. 27 (2020) 336–360 337

for humans, such as waste disposal facilities or airports. Therefore, instead of trying to re-

duce the distance between open facilities and customers, as it happens in classical location

problems, the objective is to maximize the distance between the facilities and their closer

customer.

More formally, we can define the problem as follows. Let Ibe a set of clients, Ja set of facilities,

and dij the distance between the client i∈Iand the facility j∈J.TheOpM problem consists in

finding a subset Sof the set of facilities with |S|=p,S⊆Jand p<|J|, such that the sum of the

minimum distance between each client and the set of facilities is maximized. In mathematical terms,

if we call fto the objective function, the problem is defined as

max f(S)=

i∈I

min{dij :j∈S}

subject to

S⊆J/|S|=p.

The OpM problem was introduced in Belotti et al. (2007) as belonging to the same family

of the p-dispersion and the p-median optimization problems (Shier, 1977; Kuby, 1988). As stated

in Belotti et al. (2007), the OpM problem belongs to the class of maxi-sum (or p-antimedian)

problems. In Ting (1988) it is proven that this problem is polynomially solvable on networks

with a O(n)algorithm in the case of p=1 (1-maxian problem). However, in Tamir (1991) it is

proven that the general and discrete cases of both maxi-sum and maxi-min problems are NP-

hard. Besides, for the simplest cases where p=1andp=2, they present a polynomial-time

algorithm.

Note that the practical need to solve the OpM problem may involve medium and large size

instances, which motivates the use of heuristics. The exact method by Belotti et al. (2007) is able

to solve medium size instances (up to p=50). For larger instances, their method provides a gap

w.r.t. the best upper bound. Therefore, if we need to know a good solution for instances with p

larger than 100, it is useful to run a heuristic method to complement the information provided by

the exact method. For example, in the well-known example of nuclear plant allocation, we find

around p=150 plants in Europe, which would require the use of both methodologies, exact and

heuristic, to determine a high-quality solution for such an important problem. The elaboration

of rational policies in the European context motivates the need of efficient methods to this

problem

An extensive literature review is given in relation to those kind of problems. In addition, a

mathematical model, a linear programming formulation, and some valid inequalities are pro-

vided. These theoretical results are then used in Belotti et al. (2007) to implement a Branch

and Cut (BC) method. Besides, a tabu search heuristic (XTS) is also introduced. In order to

reduce the executing time, XTS is coupled with a BC implementation. As it is shown in the

associated computational experience, this hybrid algorithm obtains good results in terms of

quality. The study is performed over a set of instances derived from the p-median problem

literature.

A GRASP method has been recently presented in Colmenar et al. (2016). The authors

present two different constructive methods and two local search algorithms. Additionally, they

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies