Undesirable facility location problems on multicriteria networks

https://doi.org/10.1016/j.cor.2005.06.010Get rights and content

Abstract

This paper is devoted to the location of undesirable facilities on multicriteria networks. Firstly, we analyze the undesirable center and median models establishing new properties to characterize the efficient solutions and rules to remove inefficient edges. Then, by means of a convex combination of these two latter functions, we address the λ-anti-cent-dian problem providing an effective rule to remove inefficient edges as well as a polynomial algorithm that solves the problem. Finally, we also comment on how this model can be slightly modified to generalize other models presented in the literature.

Introduction

Most of the significant literature on location analysis deals with the siting of facilities such as shopping stores, emergency services and educational centers. All of these facilities are desirable (attractive) to the nearby inhabitants which try to have them as close as possible.

However, there are some other facilities such as garbage dump sites, landfills, chemical plants, nuclear reactors, military installations and polluting (noise/gas) plants that turn out to be undesirable (repulsive) for the surrounding population, which avoids them and tries to stay away from them. In this sense, Erkut and Neuman [1] distinguish between noxious (hazardous) and obnoxious (nuisance) facilities, although both can be simply regarded as undesirable.

Despite these undesirable facilities being necessary, in general, to the community, for instance garbage dump sites, gas stations, electrical plants, etc., the location of such facilities might cause a certain disagreement in the population. Such disagreement has become a true opposition of people toward the installation of undesirable facilities close to them. Moreover, in the last decade, a new nomenclature has been developed to define this opposition: NIMBY (not in my back yard), NIMNBY (not in my neighbor's back yard), NIABY (not in anyones back yard), NIMTOO/NIMTOF (not in my term of office), NOPE (not on planet earth), LULU (locally unwanted land use), BANANA (build absolutely nothing anywhere near anyone).

The classical location criteria minimax (center) and minisum (median) are useless to locate this type of facility. Thus, the maximin/maxmax and the maxisum criteria arose to model, respectively, the undesirable center problem and the undesirable median problem. By placing the new facility away from existing facilities, the maximin criterion minimizes the effect on the worst impacted existing facility, whereas the maxisum criterion minimizes the collective effect (average) on the existing facilities.

Likewise, some facilities might be considered semi-desirable since they provide a main service to the community but they can also cause inconveniences to the neighboring areas, for instance, an airport, a train station, or any other noisy facility. These problems can be perfectly modeled combining the minimax/minisum criteria and the maximin/maxisum criteria.

In this sense, the undesirable facility location models on networks analyzed in the literature are basically single-criterion. Church and Garfinkel [2] defined and solved the one-facility maximum median (maxian) problem in O(mnlogn) time, being n the number of nodes and m the number of edges. This was improved by Tamir [3], who briefly suggested an O(mn) procedure. Minieka [4] addressed the anti-center (maxmax) and the anti-median (maxsum). Ting [5] devised a linear time algorithm for the 1-maxisum problem on tree networks. Recently, Colebrook et al. [6] have developed a new bound and a new O(mn) algorithm to solve the network maxian problem.

Regarding the maximin problem, Tamir [7] briefly proposed a method in O(mn) time. Lately, Melachrinoudis and Zhang [8] and Berman and Drezner [9] have also devised new O(mn) algorithms. The most recent approach is addressed by Colebrook et al. [10].

Nevertheless, Erkut and Neuman [1] emphasized the need for multiobjective approaches to the siting of undesirable facilities when they stated that (p. 289): “Current models can be used to generate a small number of candidate sites, but the final selection of a site is a complex problem and should be approached using multiobjective decision making tools”. Daskin [11] and Zhang [12] also pointed out not only the need to include multiple criteria in undesirable facility location problems, but also the fact that poor attention has been paid by researchers to these problems and hence, little research has been done in this promising field.

Thus, the literature on multicriteria/multiobjective undesirable facility location on networks starts in the late eighties and is rather scarce. Ratick and White [13] proposed a multiobjective model for the location of undesirable facilities considering three objectives. List and Mirchandani [14] presented a combined routing/siting model that can be used for siting decisions of waste treatment facilities. Rahman and Kuby [15] examine the tradeoffs between minimizing costs and public opposition in the location of a solid waste transfer station. Giannikos [16] presented a multiobjective model for locating disposal facilities and transporting hazardous waste along the links of a network considering four objectives. Zhang and Melachrinoudis [17] considered the problem of locating an obnoxious facility on a general network using two objectives, maximizing the minimum weighted distance from the point to the vertices and maximizing the sum of weighted distances between the point and the vertices. Skriver and Andersen [18] modeled a semi-obnoxious facility location problem as a bicriterion problem in both the plane and the network case. Finally, Hamacher et al. [19] presented a polynomial time algorithm for the location of a semi-obnoxious facility on networks.

Accordingly, in this paper we present a multicriteria undesirable facility location model on networks with several weights on the nodes and several lengths on the edges, combining the maximin and maxisum criteria by a parameter λ. Such a model can be considered as opposite to the multicriteria network λ-cent-dian problem and hence, it can be described as the multicriteria λ-anti-cent-dian problem on networks.

The remainder of the paper is structured as follows. In Section 2 we introduce some basic definitions and the notation. In Sections 3 and 4, we analyze both the uncenter and maxian problems considering first two criteria and then extending those results to the multicriteria case. Section 5 is devoted to the multicriteria λ-anti-cent-dian problem, whereas in Section 6 the algorithm proposed to solve this problem is devised and commented upon. To illustrate this algorithm, in Section 7 we develop a brief example. Finally, we present the computational experience in Section 8, and the paper ends with the conclusions and discussion.

Section snippets

Notation and basic definitions

Let N=(V,E) be an undirected, simple and connected network, with node set V={v1,v2,,vn}, and E={(vs,vt):vs,vtV} being the set of edges. Let p be the number of weights associated with each node, and q the number of lengths (measures, costs) attached to each edge. For each vertex in V, we define the following weight function: w:VR0+pviVw(vi)=wi=(wi1,,wip).Similarly, over each edge in E we define the next length function l:ER0+qe=(vs,vt)El(e)=le=(le1,,leq).

Given an edge e=(vs,vt)E, let x

The multicriteria uncenter problem

Given any point xN, any weight s (1sp) and any length r (1rq), let fminsr(x)=minviVwisdr(x,vi) be the minimum weighted distance from x to the set of nodes. Given an edge eE, a point yesrQesr is a local uncenter point on edge e iff fminsr(yesr)=maxxefminsr(x), for any values (s,r), with 1sp and 1rq. Likewise, a point yNsrQNsr is a network uncenter point iff fminsr(yNsr)=maxxNfminsr(x)=maxeEfminsr(yesr), for any value of indices s and r.

The uncenter function fminsr(x) is a

The multicriteria maxian problem

Given any point xN, we define the function fsumsr(x)=viVwisdr(x,vi) as the sum of weighted distances from point x to the set of nodes, with 1sp and 1rq. For the properties of fsumsr(x), the reader is referred to [6]. These functions are continuous, concave and piecewise linear over each edge e=(vs,vt)E, with at least one local maxian point zesrBer{vs,vt} such that fsumsr(zesr)=maxxefsumsr(x), with 1sp and 1rq. Besides, if fsumsr(x) reaches its maximum value at two consecutive

Multicriteria λ-anti-cent-dian problem (MACDP)

Given λ[0,1] and xN, the λ-anti-cent-dian function is defined as follows: fsumsr(λ,x)=λfminsr(x)+(1-λ)fsumsr(x)being fminsr(x)=minviVwisdr(x,vi) and fsumsr(x)=viVwisdr(x,vi), with s=1,,p and r=1,,q. Provided that both fminsr(x) and fsumsr(x) are continuous, concave and piecewise linear functions on x, the λ-anti-cent-dian function facdsr(λ,x), being a convex combination of the two latter functions, fulfills these characteristics as well. Thus, bringing together the properties of the

The algorithm to solve MACDP

We now introduce the method proposed to solve MACDP, which is outlined in Algorithm 1. It has five input data, namely, the network N(V,G), the distance matrix d, the number of weights per node p, the number of lengths per edge q, and the parameter λ. We first define the set of points P and the set of segments S.

Then, Theorem 2 is applied to remove edges containing no efficient points. This is done in O(k2mn) time, since the computation of UBei is done in O(kmn) time and facdi(λ,xLBj), 1i,jk,

An example

The aim of this section is twofold. On one hand, it develops a trace of Algorithm 1; on the other, it allows us to show a practical application of the model on a real problem. Thus, Fig. 4 depicts a random planar network representing a transportation network among several demanding sites (n=7 nodes), which are connected through communication links (m=15 edges).

Each node holds p=2 weights, whereas each edge has associated q=2 lengths. Thus, we have k=4 criteria. Beside each node viV we place

Computational results

We have programmed Algorithm 1 in C++ programming language (GNU g++ 2.95.2) using the class library LEDA 4.2.1, on a two 1.2 Ghz processor Pentium III with 1 Gb of RAM under Red Hat Linux 7.3 (Valhalla).

Two kinds of experiments were performed. In both of them, random planar networks were generated with m=3n-6 edges using the generators developed by LEDA. Likewise, parameter λ varies from λ=0 (maxian problem) to λ=1 (uncenter problem) with a step of 0.25. Both the number of weights per node p and

Conclusions and discussion

In the first part of this paper we have analyzed the uncenter and maxian problems on multicriteria networks, namely, networks holding several weights on the nodes and several lengths on the edges. New properties were established together with the rules to remove edges containing no efficient points.

Through a parameter λ, the convex combination of these two latter problems was addressed as the multicriteria λ-anti-cent-dian problem. We propose a rule to delete inefficient edges and a polynomial

Acknowledgements

The authors wish to thank the three anonymous reviewers for their valuable comments and suggestions. This paper has been supported by the Research Project MTM2004-07550 from the National Plan of Scientific Research, Technological Development and Innovation, Ministerio de Educación y Ciencia (Spain).

References (21)

There are more references available in the full text version of this article.

Cited by (26)

  • Integrating spatial information technologies and fuzzy analytic hierarchy process (F-AHP) approach for landfill siting

    2020, City and Environment Interactions
    Citation Excerpt :

    Nevertheless, the associated risk is that an unsuitable landfill can lead to water, soil, and air pollution, which, in turn, can lead to public health hazards. So, this process is complicated because it requires a thorough review and assessment process, taking environmental, ecological, economic and legislative aspects into consideration [13–17]. Consequently, the selection of these landfill sites is driven by many issues such as availability of land, geological state, available transportation lines, various regional and state regulations, increasing amounts of waste production. [5,18].

  • Improving the food waste composting facilities site selection for sustainable development using a hybrid modified MADM model

    2018, Waste Management
    Citation Excerpt :

    Because of this, compared with other public infrastructures, waste comport planet often face to face to accept more public action. In fact, according to Colebrook and Sicilia (2007), the social opposition is positioned as a key element of the municipal solid waste management facilities, which seeks to position public opinion against less successful site selection. The criteria for visibility are not based on selected laws and regulations.

  • The multicriteria p-facility median location problem on networks

    2014, European Journal of Operational Research
  • Fuzzy MCDM framework for locating a nuclear power plant in Turkey

    2014, Energy Policy
    Citation Excerpt :

    Bian and Yu (2006) use AHP in order to evaluate the alternative reverse logistics (RL) operation locations for an international electrical manufacturer. Colebrook and Sicilia (2007) analyze the undesirable center and median models to remove inefficient edges. Finally, they also comment on how this model can be slightly modified to generalize other models presented in the literature.

  • Efficient location and allocation strategies for undesirable facilities considering their fundamental properties

    2013, Computers and Industrial Engineering
    Citation Excerpt :

    They applied the lexicographic minimax approach to obtain a fair non-dominated solution. Various types of criteria have been considered in the undesirable facility location problem; see Banias, Achillas, Vlachokostas, Moussiopoulos, and Tarsenis (2010) and Colebrook and Sicilia (2007) for more. Based on the survey article of Owen and Daskin (1998), location problems can be classified into four categories: median problem, covering problem, center problem and fixed charge facility location problem.

View all citing articles on Scopus
View full text