Computers & Operations Research 33 (2006) 3566 – 3582 www.elsevier.com/locate/cor
Euclidean push–pull partial covering problems Yoshiaki Ohsawaa,∗ , Frank Plastriab , Kazuki Tamurac a Institute of Policy and Planning Sciences, University of Tsukuba, Tsukuba 305-8573, Japan b MOSI - Vrije Universiteit Brussel, Brussel B-1050, Belgium c Railway Technical Research Institute, Kokubunji 185-8540, Japan
Available online 10 May 2005
Abstract This paper considers a bicriteria model to locate a semi-obnoxious facility within a convex polygon. Assuming that a given number of closest points and farthest points may be neglected in the analysis, it considers simultaneously the resulting push and pull partial covering criteria with Euclidean distances. Although both objectives are neither concave or convex, low complexity polynomial algorithms to find all the efficient solutions and the tradeoffs involved are developed by way of higher-order Voronoi diagrams. Comparison of the tradeoff for full covering and partial covering enables decision makers to understand to what extent the maximin and minimax criteria are improved at the expense of neglecting some points. The extensions to different sets of points pulling and pushing the facility and to weighted points are discussed. All methods are illustrated via small scale examples. 䉷 2005 Elsevier Ltd. All rights reserved. Keywords: Semi-obnoxious facility; Partial covering; Efficient location; Tradeoff curve; Higher-order Voronoi diagram
1. Introduction For the last decade, the need for the location of semi-obnoxious facilities such as sewage treatment plants, landfills, waste incineration plants, airports, cemeteries, . . ., i.e., incorporating both attractive and noxious aspects has been acknowledged in the literature. This need is particularly acute today now emphasis seems to shift from simply seeking social welfare to evaluating the individuals’ environment. Indeed, one of the most difficult tasks faced by governments today is to impose semi-obnoxious facilities ∗ Corresponding author. Tel.: +81 29 853 5224; fax: +81 29 855 3849.
E-mail addresses:
[email protected] (Y. Ohsawa),
[email protected] (F. Plastria),
[email protected] (K. Tamura). 0305-0548/$ - see front matter 䉷 2005 Elsevier Ltd. All rights reserved. doi:10.1016/j.cor.2005.03.034
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
3567
on unwilling inhabitants. On the one hand these facilities are by consensus necessary for development and growth of the community due to their positive external effects. But on the other hand they also burden the local communities with negative external effects in their immediate neighborhood, and are therefore also called NIMBY (not-in-my-backyard) facilities: see [1,2]. Such positive and negative external effects can be regarded as opposite forces acting on the facility’s location, respectively pulling it towards and pushing it away from population concentrations. These forces are evidently in conflict; no single location can be optimal for both types of forces. Accordingly, for the support of decisions in locating such facilities a bicriteria approach allowing trade-off evaluations is most appropriate, as advocated by Carrizosa and Plastria [17], Blanquero and Carrizosa [4]. For the formulation of such pushing and pulling forces, maximin and minimax criteria have often been used, leading to the bicriteria model fully solved by Ohsawa [5]. In such models, however, only the extreme distances to the individuals concerned determine the objective function values. This means that a small minority may have the same effect on these objectives as a large majority, which is not a desirable property. As a result of this difficulty in providing the same service and level of well-being to all inhabitants equally, the siting of semi-obnoxious facilities usually gives rise to many types of negotiation, during which compensation from the host population is sought for an encumbered minority through transfer of benefits in monetary or non-monetary form. For example, governments have often resettled some inhabitants, bought off intense opposition, improved or set up more public facilities such as roads, schools, parks, swimming pools, landscaping and clinics in the neighborhood of the semi-obnoxious facilities, or protected their property values for the neighbors. On the other hand, in view of the severe financial problems many governments today face, such compensations should remain restricted within given budgetary bounds. Thus, real-world location problems may require not to take account of all inhabitants, but only of a portion of them. Therefore, rather than full/empty covering formulations which have extensively been introduced in past work (see e.g. [6] for a comprehensive overview of such models in a planar setting), their partial-covering versions may be more appropriate for semi-obnoxious facility location. The aim of this paper is to present a polynomial-time algorithm to construct the complete efficient solution set and the corresponding tradeoffs within such a push–pull partial covering context. In view of its partial-covering nature our model is related to several recent studies. Brimberg and ReVelle [7], Carrizosa and Plastria [3] and Daskin and Owen [8] all propose to locate purely desirable facilities, but allowing some inhabitants to remain unserved. In Daskin and Owen [8], such location models are called partial location problems. Inversely, Drezner and Wesolowsky [9], Muñoz-Pérez and SaameñoRodríguez [10] and Plastria and Carrizosa [11] consider purely undesirable facilities to be constructed, but allow a number of inhabitants to remain in the neighborhood. To date all work considered these two covering aspects separately, either inhabitants attracting the facility or inhabitants repelling the facility. In contrast, our analysis considers simultaneously both types of negotiation in order to lessen opposition by affected minority groups. The first negotiation is used to move out some affected inhabitants who oppose locating a facility in their neighborhood. The second negotiation is used to withhold the service of the facility from some inhabitants. From the algorithmic point of view, our methodology generalizes the work of Ohsawa [5] and Ohsawa and Tamura [12]. Combining the closest and farthest-point Voronoi diagrams Ohsawa [5] developed a polynomial-time algorithm to compute a full description of the efficient outcomes for a semi-obnoxious facility using maximin and minimax Euclidean distances as push and pull objectives. Ohsawa and Tamura [12] provided a polynomial-time algorithm for this same model using rectangular distances. Here we
3568
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
obtain the efficient locations associated with the push–pull partial covering bicriteria problems by replacing the standard and the farthest-point Voronoi diagrams by higher-order Voronoi diagrams. We start by considering the technically simplest situation in which all inhabitants are considered to be both positively and negatively affected, and they all carry the same weight. Although apparently restricting, such situations do appear in practice. A typical example of semi-obnoxious facilities which both push and pull all inhabitants are wireless communication base stations. These stations generate electromagnetic waves which are said to be harmful to the health of people who live close to them. On the other hand, they are located such that the power required to serve receivers is minimized. Thus, users can suffer from both positive and negative effects simultaneously from these stations. On the other hand weighted situations may be approximated by the following simple trick: replace each original inhabitant by duplicating it by unweighted inhabitants as many times as indicated by its weights and by relocating these randomly within its neighborhood. Nevertheless, the extension to different sets of inhabitants for push and pull effects, and to weighted inhabitant points and their implications on algorithm design and complexity are also discussed. The remainder of this paper is organized as follows. Section 2 first looks at the two objectives separately, thereby introducing the notions and notations needed in the sequel, as well as a geometric characterization of the solutions of partial anti-center and center problems. In Section 3 both objectives are combined, considering the facility as both attracting and repelling to all inhabitants. Theoretical findings are obtained allowing the construction of the set of efficient solutions for this basic bicriteria model, and we indicate how additional sensitivity information to changes in the covered portions may be obtained. Section 4 shortly discusses the two extensions of the basic model hinted at above: on the one hand distinction is made between the attracting and repelling inhabitant sets, and on the other hand individuals are replaced by sites weighted by population-size. Section 5 contains our conclusions. 2. Single-objective models 2.1. Formulations Given a convex polygon on a Euclidean plane where a facility can be built, denote its boundary by j, and the number of straight-line segments forming it by |j|. Let I and {p1 , . . . , p|I | } be the index and location sets of the affected inhabitants on the plane, respectively. In what follows, the index set I is used interchangeably with the location set {p1 , . . . , p|I | }. To avoid the technicalities of degenerate cases, we assume that |I | 2 and that the pu ’s are in general position. In the partial anti-center location problem, in order to mitigate opposition to locating a facility to be constructed, an exogenously specified number n− of inhabitants will be resettled farther from the facility, and it may therefore be considered that their current location will be neglected. The problem then consists of finding the location within which maximizes the nearest distance from the facility to |I | − n− inhabitants. Hence, this is defined by max Fn− (x) ≡ min x − pu max . (1) x∈
J − ⊆I,|J − |=|I |−n−
u∈J −
Thus, the objective function Fn− (x) stands for the (n− + 1)th shortest distance from x to the original set I. This problem seeks for the center of the largest open circular disk enclosing n− inhabitants. We
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
3569
denote its solution by an∗− . It should be noted that n− = 0 means empty cover, or the traditional maximin problem. Our formulation is equivalent to the unweighted version of the maxquantile location problem in Plastria and Carrizosa [11], and also a special case of the obnoxious facility location in Muñoz-Pérez and Saameño-Rodríguez [10]. In the partial center location problem, in order to reduce the covering distance, an exogenously specified number n+ of inhabitants far from the facility will remain unserved. The problem is to determine a location within in such a way that the farthest distance from the facility to |I | − n+ inhabitants is minimized. Its mathematical description is max x − pv min . (2) min Gn+ (x) ≡ J + ⊆I,|J + |=|I |−n+
x∈
v∈J +
So the objective function Gn+ (x) stands for the (n+ + 1)th largest, i.e., (|I | − n+ − 1)th shortest distance from x to the original set I. In other word, in this problem the smallest closed circular disk uncovering n+ inhabitants is determined. We denote its optimal location by cn∗+ . It should be noted that n+ = 0 means full covering or the traditional minimax problem. The problem is the unweighted version of the minquantile location problem in Carrizosa and Plastria [3]. 2.2. Geometrical solutions Let I1k , . . . , Itk(k) be all possible subsets out of I whose cardinality is k, where t (k) ≡
|I |! k!(|I |−k)! . Let VIik
be the set of all points of the plane for which the set of the k closest points of I is Iik , i.e. from which the largest distance to all pu ’s with u ∈ Iik is equal to or less than the shortest distance to the other points. Its formulation is given by VI k ≡ x ∈ R2 | max x − pu min x − pv . u∈Iik
i
(3)
v ∈I / ik
This set is often empty. When non-empty, it is called the order-k Voronoi polygon associated with Iik : see Okabe et al. [13]. The union of all VI k ’s is the order-k Voronoi diagram. As special cases, the diagrams i satisfying k = 1 and k = |I | − 1 reduce to the ordinary Voronoi diagram and the farthest-point Voronoi diagram, respectively. It follows from (3) that all VI k are defined by the intersection of half-planes, so the i feasible region can be partitioned, by intersection with the VI k , into bounded convex regions delimited i
by j and jV k , where jV k is the union of the parts of boundaries of all VI k within . The geometrical i properties of higher-order Voronoi diagrams can be found in detail in Lee [14]. In the partial anti-center problem (1), n− users in the neighborhood of the facility are neglected. Hence for any x ∈ VI n− +1 we have Fn− (x) = maxu∈I n− +1 x − pu . So the level set of Fn− for a fixed within i i − VI n− +1 , i.e. x ∈ VI n− +1 | Fn− (x) , is given by the intersection of the disks centered at pu u ∈ Iin +1 i
i
with radius , so any level set within VI n− +1 has to be convex. The level sets of the partial anti-center i
problem with n− = 1, and the order-2 Voronoi diagram are illustrated in Fig. 1, where five inhabitants p1 , . . . , p5 are denoted by black dots. Thus, on each cell VI n− +1 ∩ the function Fn− (x) is the restriction i
3570
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
Fig. 1. Partial anti-center location with n− = 1 and order-2 Voronoi diagram.
of a quasiconvex function with strictly convex level sets, which is well known to be maximized only at some extreme point. This implies: Proposition 1. The solution an∗− to the partial anti-center problem (1) has to lie ateither (1) a vertex of − − jV n +1 , or (2) a vertex of j, or (3) an intersection point of jV n +1 and j. This was implicitly pointed out by Plastria and Carrizosa [11]. It is evident from the definition of higher-order Voronoi diagrams (3) that the farthest order-k Voronoi diagram coincides with the order-(|I | − k) Voronoi diagram. Hence, similarly as for Fn− (x), Gn+ (x) = min |I |−n+ −1 x − pu for x ∈ V |I |−n+ −1 . Accordingly, the level set of Gn+ within V |I |−n+ −1 consists of u∈Ij Ij Ij |I |−n+ −1 with the same radius intersected with V |I |−n+ −1 . the union of the disks centered at pv v ∈ Ij This implies that any vertex of a level set of Gn+ in the interior of V
Ij
|I |−n+ −1 Ij
cannot be cusped. Fig. 2
shows the level sets of the partial anti-center problem with n+ = 1, and the order-3 (farthest order-2) Voronoi diagram. Hence we see that the cusped vertices of any level set occur only along a segment within + jV |I |−n −1 . This leads to Proposition 2. The solution cn∗+ of the partial center problem (2)must be either at (1) a vertex of + + jV |I |−n −1 , (2) a midpoint on jV |I |−n −1 between two inhabitants, (3) a vertex of j, or (4) a projection of some inhabitant onto j.
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
3571
Fig. 2. Partial center location with n+ = 1 and order-3 Voronoi diagram.
This is an extension of Ohsawa [5]. 3. Biobjective models 3.1. Formulation The biobjective problem generated by combining the maximization problem (1) with the minimization one (2), which are both neither convex nor concave, is called the push–pull partial covering model. This is formulated as min{−Fn− (x), Gn+ (x)}. x∈
(4)
As a special case, we term the problem with n− = n+ = 0 the push–pull full covering model, which has already been explored in Ohsawa [5]. As usual, x ∈ is efficient if and only if there does not exist a y ∈ dominating x, i.e. such that either (1) Fn− (y) > Fn− (x) and Gn+ (y) Gn+ (x) or (2) Fn− (y) Fn− (x) and Gn+ (y) < Gn+ (x). Throughout this paper, we consider the objective space where the horizontal (resp. vertical) axis measures the values of Fn− (x) (resp. Gn+ (x)). Since the right and lower directions in objective space are better in terms of Fn− (x) and Gn+ (x) respectively, any efficient location has no alternative lying in a southeasterly quadrant direction from it. We denote by En∗− ,n+ the set of efficient points and by tn∗− ,n+ the set of biobjective values corresponding to En∗− ,n+ in objective space. Since tn∗− ,n+ shows the performance of all alternatives within
3572
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
En∗− ,n+ we call tn∗− ,n+ the tradeoffs between Fn− (x) and Gn+ (x). To make our notation simpler, we denote {(Fn− (x), Gn+ (x))|x ∈ S} by (Fn− (S)), Gn+ (S)) for any setS ⊆ . Thus, tn∗− ,n+ is given by Fn− En∗− ,n+ , Gn+ En∗− ,n+ . 3.2. Geometrical solution We assume that n− + n+ < |I | because it would make no sense to consider a neglected inhabitant to also remain unserved. This assumption means that Fn− (x) < Gn+ (x) at any point x ∈ . − + Consider any point x ∈ but not in jV n +1 ∪ jV |I |−n −1 ∪ j. Then such a point is at the same time − + interior to , to some cell VI n− +1 of V n +1 and some cell V |I |−n+ −1 of V |I |−n −1 . Therefore the level set Ij
i
of Fn− through x is (locally) an intersection of at most two disks of radius r = Fn− (x), and better (higher) values of Fn− are found outside this level set. Similarly, the level set of Gn+ through x is (locally) a disk of larger radius Gn+ (x) > r, and better (smaller) values for Gn+ are found inside this disk. It is then easy to construct a circular arc of intermediate radius passing through x, and lying respectively outside the smaller and inside the larger of the two former level sets, thus containing points dominating x within any neighborhood, which proves that x is not efficient. Thus we obtain the following result similar to Ohsawa and Tamura [12]. Proposition 3. The efficient set En∗− ,n+ is a subset of jV n
− +1
∪ jV |I |−n
+ −1
∪ j.
When n− = n+ = 0 this proposition reduces to the result by Ohsawa [5]. In geometric terms this is equivalent to saying that the southeasterly envelope of the loci (Fn− (x), Gn+ (x)) for the two-dimensional area , that is, the tradeoff, is described by the southeasterly envelope of only the loci for the set of − + line-segments jV n +1 ∪ jV |I |−n −1 ∪ j. As shown in Ohsawa [5], for any line segment l and point x ∈ l whose (n− + 1)th nearest inhabitant is pf and (|I | − n+ − 1)th nearest one is pg , we have, denoting any p’s projection onto the line containing l by p , ⎧ 2 2 2 + p − p ⎪ ⎪ − F (x) − p − p + pg − pg 2 , for pf between pg f n ⎨ g f f Gn+ (x)2 = (5) and x; ⎪ ⎪ ⎩ F − (x)2 − p − p 2 − p − p 2 + p − p 2 , otherwise. n
f
f
f
g
g
g
As a consequence of Proposition 3, an algorithm for construction of the efficient solutions and the tradeoffs can be given by modifying the technique by Ohsawa and Tamura [12] as follows: − + Step 1: Set up the planar graph N ≡ jV n +1 ∪ jV |I |−n −1 ∪ j. Step 2: Split the links of N into sublinks along which the (n− + 1)th and (|I | − n+ − 1)th nearest inhabitants, denoted as pf and pg , are both constant. Step 3: Draw (Fn− (N), Gn+ (N)) in objective space based on (5). Step 4: Detect the south-eastward envelope of (Fn− (N), Gn+ (N)). Step 5: Specify the sublinks of N corresponding to the envelope in geographical space. Any higher-order Voronoi diagram for |I | inhabitants is constructed in at most O(|I |2 log |I |) time: see [15]. As shown in Lee [14], the number of edges and vertices of any higher-order Voronoi diagram
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582 −
3573
+
are both bounded by O(|I |2 ), so both graphs jV n +1 ∪ j and jV |I |−n −1 ∪ j can be constructed in O(|I |2 + |j|) time because j is a closed polygonal line. After this, the graph N is generated in O(|I |4 ) − + by merging jV n +1 ∪ j and jV |I |−n −1 ∪ j. Thus, Step 1 takes O(|I |4 + |j|). As implicitly pointed out by Okabe et al. [13], any kth nearest-point Voronoi diagram is generated by superimposing the order-k Voronoi diagram on the order-k − 1 Voronoi diagram, so the (n− + 1)th and (|I |−n+ −1)th nearest-point Voronoi diagrams are built in O(|I |2 log |I |) time. Since the number of edges − + and vertices of theseVoronoi diagrams are both bounded by O(|I |2 ), all edges within jV n +1 ∪jV |I |−n −1 can be partitioned into sublinks along which the (n− + 1)th and (|I | − n+ − 1)th nearest inhabitants are constant in O(|I |4 ) time by grouping the calculations along each Voronoi edge. On the other hand, the (n− + 1)th and (|I | − n+ − 1)th nearest-point Voronoi diagrams intersect j at most O(|I |2 + |j|) times. Hence such partition on j runs in O(|I |2 + |j|) time by traversing once each edges of j. Thus, Step 2 can be done in O(|I |4 + |j|). The graph defined in Step 2 possesses O(|I |4 + |j|) sublinks, so Step 3 runs in O(|I |4 + |j|) time. The Eq. (5) means that the curves corresponding to any pair of links intersect each other at most twice. This means that the lower envelope of these curves can be found in O((|I |4 + |j|) log(|I |4 + |j|)) by a divide-and-conquer method, and the number of links on the envelope is O(|I |4 + |j|): see Boissonnat and Yvinec [16]. Applying the same divide-and-conquer method in horizontal direction to the sublinks corresponding to the lower envelope yields the south-eastward envelope. This can again be carried out in O((|I |4 + |j|) log(|I |4 + |j|)). Thus, Step 4 requires O((|I |4 + |j|) log(|I |4 + |j|)) effort. Step 5 is done in O(|I |4 +|j|) time since the number of sublinks on the south-eastward envelope is O(|I |4 +|j|). In total, our solution requires O((|I |4 + |j|) log(|I |4 + |j|)). As a proposition we state: Proposition 4. The efficient set En∗− ,n+ and its tradeoff tn∗− ,n+ can be found in O((|I |4 + |j|) log(|I |4 + |j|)) time. ∗ , consisting For the same inhabitant set (|I | = 5) as in Figs. 1 and 2, Fig. 3 shows the efficient set E1,1 of two solutions c1∗ , w1 , the (two-piece) path between w2 and w3 , and the (two-piece) path between w4 and a1∗ . Fig. 4 shows the loci corresponding to the boundaries jV 2 ∪ jV 3 ∪ j. The boundaries jV 2 , jV 3 and j in Fig. 3, and the plots corresponding to them in Fig. 4 are indicated by thin, broken and thick lines, respectively. Note that the tradeoff cannot be defined over the open interval (F1 (c1∗ ), F1 (w1 )). This shows by example that, contrary to the full covering case (see [5]), the tradeoffs do not form a connected set.
3.3. Sensitivity analysis We have explored the bicriteria problems only for fixed n− and n+ . As we noted, some inhabitants in the neighborhood of the facility have obtained subsidies and tax rebates in compensation for the negative effect due to the semi-obnoxious facility. Some inhabitants far from the facility have been served in different manners such as alternative facilities in compensation for the local unavailability of the semiobnoxious facility. Undoubtedly, as more inhabitants are neglected, both objective functions (1) and (2) are improved, but such compensation costs increase at the same time. As a result, in the partial anti-center problem, the obnoxious level and the compensation cost contradict, and their tradeoff is examined in Plastria and Carrizosa [11]. In the partial center problem, there is a tradeoff between the service level and
3574
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
Fig. 3. Efficient set for push–pull partial covering with n− = 1 and n+ = 1.
Fig. 4. Tradeoff for push–pull partial covering with n− = 1 and n+ = 1.
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
3575
Fig. 5. Four efficient sets.
the compensation cost, which is explored in Carrizosa and Plastria [3]. However, Plastria and Carrizosa [11], Carrizosa and Plastria [3] examine tradeoffs only in terms of a single criterion. Different from these previous works, we here examine tradeoffs in terms of both criteria. We take up following simple schemes generated by varying n− and n+ over a narrow range via our example as shown in Figs. 1 and 2: (1) a full covering, i.e., n− = n+ = 0; (2) one inhabitant hating the facility is neglected, i.e., n− = 1, n+ = 0; (3) one inhabitant desiring the facility is neglected i.e., n− = 0, n+ = 1; and (4) one inhabitant hating the facility and one inhabitant desiring it are neglected, i.e., n− = n+ = 1: see Figs. 3 and 4. ∗ , E∗ , The effect of varying n− and n+ can be observed in Figs. 5 and 6, where all four efficient sets E00 10 ∗ and E ∗ and their corresponding tradeoffs t ∗ , t ∗ , t ∗ and t ∗ are identified by thin, single-dot-dash, E01 11 00 10 01 11 ∗ (E ∗ , E ∗ and E ∗ ) includes its two single broken and solid lines, respectively. Of course each set E00 10 01 11 criterion optimal solutions a0∗ and c0∗ (a1∗ and c0∗ , a0∗ and c1∗ , a1∗ and c1∗ ) as extreme points. The efficient set ∗ consists of the path between c∗ and s , and the one between s and a∗ . The set E ∗ for full covering E00 1 2 0 0 10 consists of the path between c0∗ and v1 , the path between v2 and w1 , and the one between v3 and a1∗ . The ∗ comprises the path between c∗ and u , and the one between u and a∗ . Even though the efficient set E01 1 2 1 0 ∗ and E ∗ overlap between s and a∗ , the figure clearly shows that the efficient set usually changes sets E00 2 01 0 significantly with n− and n+ . ∗ and Fig. 6 shows the situation in objective space. Horizontally, so in terms of Fn+ , the trade-offs t00 ∗ ∗ ∗ ∗ ∗ ∗ ∗ t01 (t10 , t11 ) reach values up to F0 (a0 ) (F1 (a1 )); vertically, in terms of Gn− , the trade-offs t00 and t10 ∗ ∗ ∗ ∗ ∗ ∗ (t01 , t11 ) take values starting at F0 (a0 ) (F1 (a1 )). We also see that the tradeoff of partial-covering t10 (t01 , ∗ ) is located at the east (south, southeast) of that of full covering t ∗ . An increase in n− and/or n+ will t11 00
3576
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
Fig. 6. Four tradeoffs.
improve the maximin and/or minimax functions, so it will shift the tradeoff to the right and/or the bottom, respectively, as we would expect. Thus, such sensitivity analysis within a partial bicriteria covering framework enables us to perceive clearly and quickly to what extent the biobjective functions can be improved by relaxing the constraint that all inhabitants should be covered.
4. Extensions 4.1. Different affected sets As a rule, the group of inhabitants wanting the semi-obnoxious facility far away may differ from those wanting the facility close by. This subsection extends the basic model (4) by considering such difference. Let I and p1 , . . . , p|I | be the index and location sets of the negatively affected inhabitants. Let I and p1 , . . . , p|I | be the index and location sets of the positively affected inhabitants. We assume that |I | 2, |I | 2, and all pi ’s (respectively pi ’s) are in general position, but we allow the possibility that pi = pj
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
3577
for some i ∈ I and j ∈ I . We consider the biobjective problem by combining the following problems: max Fn− (x) ≡ x∈
max
J − ⊆I ,|J − |=|I |−n−
min Gn+ (x) ≡ x∈
min x − pu
u∈J −
min
(6)
.
(7)
J + ⊆I ,|J + |=|I |−n+
,
max x − pv
v∈J +
k Let jV k and jV be the boundary of the order-k Voronoi diagram generated by p1 , . . . , p|I | , and generated by p1 , . . . , p|I | , respectively. Let Lk,l i,j be the half-line from pj in the opposite direction of pi within the intersection of the kth nearest-point Voronoi polygon generated by p1 , . . . , p|I | and
the lth nearest-point Voronoi polygon generated by {p1 , . . . , p|I | }. Let Lk,l be the union of Lk,l i,j ’s, i.e., k,l Lk,l ≡ i∈I ,j ∈I Li,j . What is different from the basic model is that some previously not considered points may be efficient. Indeed, it might now happen that Fn− (x) > Gn+ (x) at some points x ∈ i.e. the curvature of the boundary of the level set of Fn− is less than that of Gn+ , even when these boundaries are tangent at x. Such exceptional − + points must be located on Ln +1,|I |−n −1 where the disk determining the level set of Fn− is inscribed in −
the disk determining the level set of Gn+ . Hence, apart from jV n +1 ∪ jV − + to consider Ln +1,|I |−n −1 as containing candidate efficient locations. Proposition 5. The efficient set En∗− ,n+ is a subset of jV n Based on this proposition, the complete algorithm is: −
− +1
∪ jV
|I |−n+ −1
|I |−n+ −1
|I |−n+ −1
−
∪ Ln
∪ j, we also have
− +1,|I |−n+ −1
∪ j.
+
Step 1: Establish the planar graph N ≡ jV n +1 ∪ jV ∪ Ln +1,|I |−n −1 ∪ j. Step 2: Split the links of N into sublinks along which the (n− + 1)th nearest inhabitant of I , denoted as pf , and the (|I | − n+ − 1)th nearest inhabitant of I , denoted as pg , are both constant. Step 3: Delineate (Fn− (N), Gn+ (N)) in objective space using (5). Step 4: Find the south-eastward envelope of (Fn− (N), Gn+ (N)). Step 5: Identify the sublinks of N corresponding to the envelope. −
|I |−n+ −1
As basic model, the planar graph jV n +1 ∪ jV ∪ j can be constructed in 2in the 2 O |I | |I | + |j| . The polygons of the (n− + 1)th and (|I | − n+ − 1)th nearest-point Voronoi di− + in agrams are bounded by O(|I |2 ) and O(|I |2 ), respectively. Hence, Ln +1,|I |−n −1 can be detected O(|I |2 |I |2 + |j|) using these Voronoi diagrams and j. Thus, Step1 takes O |I |2 |I |2 + |j| . Since the graph N has O |I |2 |I |2 + |j| edges, Step 4 requires O (|I |2 |I |2 + |j| log |I |2 |I |2 + |j|) effort, which dominates Steps 2, 3 and 5.
3578
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
p3
V235
p2
p5
V245
V345 p
4
V135 a ∗1
p5 p3 w2
w1 c ∗1
p4
p1
p1 V134
p2
V145
Fig. 7. Efficient set for different affected partial covering with n− = 1 and n+ = 1.
Proposition 6. The efficient set En∗− ,n+ and its tradeoff tn∗− ,n+ for the different affected version can be determined in O |I |2 |I |2 + |j| log |I |2 |I |2 + |j| time. Hence, although the negatively affected set differs from the positively one, the computational complexity does not change in essence. A simple numerical example with |I | = |I | = 5 is given in Figs. 7 and 8. The pushing and pulling 3 inhabitants are indicated by bullets and open circles, respectively in Fig. 7. The boundaries jV 2 , jV , L2,3 and j in Fig. 7, and the plots corresponding to them in Fig. 8 are indicated by thin, broken, dotdash and thick lines, respectively. The repelling set coincides with the affected set in Fig. 1, so only the 3 Voronoi polygons associated with the attracting set, i.e., jV are labelled. Note that L2,3 consists of only 2,3 ∗ consists of the (two-piece) path between c∗ and one segment L1,4 . It follows from Fig. 7 that the set E1,1 1 w1 , and the (three-piece) path between w2 and a1∗ . 4.2. Weighted inhabitants Another situation is when inhabitants are weighted. This subsection extends the basic model (4) by treating such weighting. Let i (> 0) be the weight of the ith inhabitant and denote by − and + the maximum total weight of the set of negatively affected inhabitants which will be resettled and the maximum total weight of those that will remain unserved. Writing w(J ) = j ∈J j for any J ⊂ I we may clearly assume − + + < w(I ), like in Section 3.2. This leads to the following redefinitions of our
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
3579
G1(x) *
G1 ( a 1 )
G1(w2) G1(w1) *
G1 ( c 1 )
*
*
F1 ( c1 ) F1(w1) = F1(w2)
F1 ( a1)
F1(x)
Fig. 8. Tradeoff for different affected partial covering with n− = 1 and n+ = 1.
two objectives: max F− (x) ≡ x∈
min G+ (x) ≡ x∈
max
J − ⊆I,w(I \J − ) −
min
J + ⊆I,w(I \J + ) +
min x − pu
u∈J −
(8)
.
(9)
max x − pv
v∈J +
,
Define jV by jV ≡ ∪jV 1 ∪ jV 2 ∪ . . . ∪ jV |I | , that is, jV coincides with the collection of the perpendicular bisectors of all pairs of pu ’s. It should be noted that all points x within a same polygon delimited by jV have the same kth nearest inhabitant for all k (1 k |I |), and therefore the running index sets J − in (8) and J + in (9), respectively determining the values of F− (x) and G+ (x) are constant within this polygon. In addition, thanks to the assumption − + + < w(I ) which implies J − ∩ J + = ∅ for any x ∈ , the curvature of the boundary of the level set of F− through x is greater than that of G+ (x) through it, similar to the basic model. Therefore, we have Proposition 7. The efficient set E∗ − ,+ is a subset of jV ∪ j. This proposition leads to the following algorithm: Step 1: Set up the planar graph N ≡ jV ∪ j. Fig. 1 are indicated in Figs. 9 and 10, Step 2: For each polygon of N, determine the running index sets J − in (8) and J + in (9), and assign the nearest inhabitant of I \J − , denoted as pf , and the farthest inhabitant of I \J + , denoted as pg , to each link of N.
3580
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
Fig. 9. Efficient set for weighted partial covering with − = 1 and + = 2.
Step 3: Draw (F− (N), G+ (N)) based on (5). Step 4: Define the south-eastward envelope of (F− (N), G+ (N)). Step 5: Specify the sublinks of N corresponding to the envelope. Since the number bisectors is O(|I |2 ), the graph jV can be established in O(|I |4 ) time. Hence, the graph N can be constructed in O(|I |4 + |j|), as in the case of the algorithm for the basic model. Thus, Step1 takes O(|I |4 + |j|). Once distances within one polygon to all pu are sorted in O(|I | log |I |), the ordering within any adjacent polygon is obtained in constant time, because moving from one polygon to an adjacent polygon across one Voronoi edge interchanges only the order of the two consecutive inhabitants associated with this edge. At the same time, if the running index sets J − and J + are determined in one polygon based on the sorting and the weights i ’s, then the sets J − in (8) and J + in (9) of any adjacent polygon is also identified in constant time. The number of polygons of the graph N is bounded by O(|I |4 + |j|), so Step 2 can be done in O(|I |4 + |j|). Since the graph N also has O(|I |4 + |j|) edges, Step 4 requires O((|I |4 + |j|) log(|I |4 + |j|)) effort, which dominates Steps 2, 3 and 5. Proposition 8. The efficient set E∗ − ,+ and its tradeoff t∗ − ,+ for the weighted version can be determined in O |I |4 + |j| log |I |4 + |j| + |j||I |2 time. Thus, although the inhabitants are weighted, the computational complexity does not change. It should be noted that the complexity of the approximation method to generate unweighted inhabitants by duplicating an original inhabitant as many times as indicated by its weights increases with the size of
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
3581
Fig. 10. Tradeoff for weighted partial covering with − = 1 and + = 2.
the weights, and is therefore quite different from the complexity of our procedure which is independent of such size. The efficient set and its tradeoff for the same inhabitant set (|I | = 5) as in where, where the boundaries jV and j in Fig. 9, and the plots corresponding to them in Fig. 10 are indicated by thin and thick lines, respectively. In Fig. 9 where the weights are indicated by using parentheses, twenty = 25 perpendicular bisectors partition the study area into polygons. The solution a1∗ is located along the perpendicular bisector of p2 and p5 . The solution c2∗ is located at the circumcenter of p2 , p4 and p5 . Note that u1 with p2 , c2∗ and p5 makes a rhombus, so F1 (c2∗ ) = c2∗ − p5 = u1 − p5 = F1 (u1 ). We see from ∗ consists of the isolated point c∗ , and the (one-piece) path connecting u Fig. 9 that the efficient set E1,2 1 2 ∗ anda1 . 5. Conclusions and future research In this paper we formulated new bicriteria location problems where partial covering is introduced to model the siting of a semi-obnoxious facility with the aim of enhancing its practical applicability. We have developed (fourth or slightly more, but less than fifth degree) polynomial-time algorithms to delineate the efficient locations and the full tradeoff information associated with these problems.
3582
Y. Ohsawa et al. / Computers & Operations Research 33 (2006) 3566 – 3582
Although a theoretical basis for the push–pull partial covering has been established, the full sensitivity analysis against all possible combination of resettled inhabitants and unserved inhabitants also remains a possible topic for future research. Acknowledgements This work was partially supported by the Kajima Foundation’s Research Grant (2002,2003). The early version of this paper was presented at the International Symposium on Voronoi Diagrams in Science and Engineering, University of Tokyo, September 13–15th, 2004. We wish to acknowledge the comments received from the conference participants, Masahiro Hachimori as well as two anonymous referees. References [1] Lesbirel H. NIMBY Politics in Japan. Ithaca: Cornell University Press; 1998. [2] Quah E, Tan KC. Siting environmentally unwanted facilities. Cheltenham: Edward Elgar; 2002. [3] Carrizosa E, Plastria F. Polynomial algorithms for parametric minquantile and maxcovering planar location problems with locational constraints. TOP 1998;6:179–94. [4] Blanquero R, Carrizosa E. A D.C. biobjective location model. Journal of Global Optimization 2002;23:139–54. [5] Ohsawa Y. Bicriteria Euclidean location associated with maximin and minimax criteria. Naval Research Logistics 2000;47:581–92. [6] Plastria F. Continuous covering location problems. In: Hamacher H, Drezner Z, editors. Location analysis: theory and applications. Springer; 2001. p. 39–83. [7] Brimberg J, ReVelle C. A multi-facility location model with partial satisfaction of demand. Studies in Locational Analysis 1999;13:91–101. [8] Daskin MS, Owen SH. Two new location covering problems: the partial p-center problem and the partial set covering problem. Geographical Analysis 1999;31:217–35. [9] Drezner Z, Wesolowsky G. Finding the circle or rectangle containing the minimum weight of points. Location Science 1994;2:83–90. [10] Muñoz-Pérez J, Saameño-Rodríguez JJ. Location of an undesirable facility in a polygonal region with forbidden zones. European Journal of Operational Research 1999;114:372–9. [11] Plastria F, Carrizosa E. Undesirable facility location with minimal covering objectives. European Journal of Operational Research 1999;119:158–80. [12] Ohsawa Y, Tamura K. Efficient location for a semi-obnoxious facility. Annals of Operations Research 2003;123:173–88. [13] Okabe A, Boots B, Sugihara K, Chiu SN. Spatial tesselations. Chichester: Wiley; 1999. [14] Lee DT. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Transactions on Computers 1982;C-31:478–87. [15] Agarwal PK, de Berg M, Matousek J, Schwarzkopf O. Constructing levels in arrangements and higher order Voronoi diagrams. SIAM Journal on Computing 1998;27:654–67. [16] Boissonnat J-D, Yvinec M. Algorithmic geometry. Cambridge: Cambridge University Press; 1998. [17] Carrizosa E, Plastria F. Location of semi-obnoxious facilities. Studies in Locational Analysis 1999;12:1–27.
