A DC biobjective location model

Journal of Global Optimization 23: 139–154, 2002. © 2002 Kluwer Academic Publishers. Printed in the Netherlands. 139 A D.C. biobjective location model RAFAEL BLANQUERO and EMILIO CARRIZOSA Departamento de Estadística e Investigación Operativa, Facultad de Matemáticas, Universidad de Sevilla, C/. Tarfia S.N., 41012 Sevilla, Spain Fax: +34-954622800; (e-mail: [email protected], [email protected]) Abstract. In this paper we address the biobjective problem of locating a semiobnoxious facility, that must provide service to a given set of demand points and, at the same time, has some negative effect on given regions in the plane. In the model considered, the location of the new facility is selected in such a way that it gives answer to these contradicting aims: minimize the service cost (given by a quite general function of the distances to the demand points) and maximize the distance to the nearest affected region, in order to reduce the negative impact. Instead of addressing the problem following the traditional trend in the literature (i.e., by aggregation of the two objectives into a single one), we will focus our attention in the construction of a finite ε-dominating set, that is, a finite feasible subset that approximates the Pareto-optimal outcome for the biobjective problem. This approach involves the resolution of univariate d.c. optimization problems, for each of which we show that a d.c. decomposition of its objective can be obtained, allowing us to use standard d.c. optimization techniques. Key words: Biobjective Programming; Semi-obnoxious facility location; Univariate D.C. optimization 1. Introduction We consider the biobjective problem of locating a facility in a region Sin the plane, which installation is beneficial for a set of potential users, but, at the same time, it has negative effects on the population or the environment, so we can distinguish a set of negatively affected elements. A facility with these characteristics, called semiobnoxious, involves two opposed and irreconcilable aims: on the one hand, the new facility must be located as near its potential clients as possible and, on the other hand, it must be placed far from the residents, which are affected in a negative way. In this sense, the model considered here will take into account the following criteria for locating the new facility at x∈S: Criterion 1: Minimize the service cost from the new facility to the clients, min x∈ST1(x). (C1) Criterion 2: Maximize the distance between the new facility and the nearest resident, max x∈ST2(x). (C2) 140 R. BLANQUERO AND E. CARRIZOSA The biobjective problem obtained when both criteria are simultaneously considered can be written as: min x∈S(T1(x), −T2(x)). (1.1) The usual approach for this problem has been the aggregation into a single objective (see Carrizosa and Plastria, 1999; Chen et al., 1992; Maranas and Floudas, 1994; Nickel and Dudenhoffer, 1997 and Tuy et al., 1995 for an updated review on the topic on semiobnoxious facility location). However, since the problem is essentially multiobjective, we propose to construct a finite approximation for the Pareto-optimal outcome, through the concept of ε-dominating set [Carrizosa et al., 1997; Hansen and Thisse, 1981; Lemaire, 1992; White, 1996, 1998). In other words, given ε=(ε1,ε 2)with ε1>0,ε 2>0, our aim is to obtain a finite subset S∗⊂Ssuch that, for any x∈Swe can find x∗∈S∗with: T1(x∗)⩽T1(x) +ε1 −T2(x∗)⩽−T2(x) +ε2. If just a singleton is sought, we can use any M.C.D.A. methodology (Vincke, 1992), to choose one element out of this finite set S∗. In order to obtain a more tractable problem, we make several assumptions that will be introduced in the following section. 2. The Model The users of the facility are modeled by a set of npoints in the plane A+= {a1,... ,a n}, whereas the negatively affected elements are modeled by means of a set of mregions in the plane A−={R1,... ,R m}, where each Riisacompact and convex set, whose boundary can be written (perhaps after an approximation process using splines (Ahlberg et al., 1967) as a finite union of line segments and circumference arcs, i.e., bd(Ri)= ni  j=1 L(i) j with L(i) jbeing a line segment or a circumference arc. Note that these assumptions include the case in which Riis a polygonal region, decomposed into convex polygons via a triangulation process. Note also that, as a particular case, a region Ri reduced to a point is allowed. We consider the particular case of (1.1) with T1and T2defined as T1(x) =h(D1(γ1(x −a1)), . . . , Dn(γn(x −an))) (2.2) T2(x) =min 1⩽i⩽mdR(x, Ri)(2.3) A D.C. BIOBJECTIVE LOCATION MODEL 141 where: •xis the (unknown) location for the new facility. •aiare the coordinates of the i-th demand point, i=1,... ,n. •γiis a guage providing a measure of the distance between aiand any point of the plane, that is, a (convex) function γi:R2→ Rdefined as γi(x) =inf{t>0:x∈tBi}x∈R2(2.4) where Biis a convex set, the interior of which contains the origin (Michelot, 1993). •Di:R→ R+is a convex, non-decreasing and non-constant function providing the service cost to the i-th demand point per unit of distance. •h:Rn→ Ris a monotonic norm, (Bauer et al., 1961), i.e., a norm satisfying (u, v ∈Rn,|ui|⩽|vi|∀i) ⇒h(u) ⩽h(v). In particular, the Lp-norms, · p, are monotonic for 1 ⩽p⩽∞. •Sis the feasible set for locating the new facility, which is assumed to be compact, not necessarily convex, and its boundary is a finite union of arcs of conic curves. •dR(x, Ri)=minxi∈Rix−xi2 In particular, the first objective includes, among others, the classical criteria in Location Theory (Plastria, 1995: minisum(h =· 1),minimax (h =· ∞)and cent-dian (h =(1−λ)· 1+λ· ∞). 3. The algorithm In this section we describe a procedure for building a finite ε-dominating set for Problem (1.1). Roughly speaking, such a procedure is based on the search of an ε-dominating set for a finite set of subproblems, obtained by decomposing the feasible set Sinto pieces within which the objective T2has a simpler structure. In this sense, given a region Rj,letVjdenote the Voronoi cell associated with Rj: Vj={x∈R2:dR(x, Rj)⩽dR(x, Ri), i = j,1⩽i⩽m}. Hence, since {Vj}n j=1covers the plane, and ε-dominating set can be obtained by merging ε-dominating sets for the subproblems min x∈S∩Vj (T1(x), −T2(x)). (3.5) From the fact that the boundary of each Rjis made of line segments and circumference arcs, we conclude that the boundary of each Vjwill consist of conic arcs, (Okabe et al., 1995). The construction of an ε-dominating set for Subproblem (3.5) is simplified due to the fact that it can be reduced to solving a finite number of univariate d.c. optimization problems (see Remarks 3.7 and 3.13 below). To do this, the following result, proposed in Blanquero (1999) and Blanquero and Carrizosa (2000), is needed. 142 R. BLANQUERO AND E. CARRIZOSA PROPOSITION 3.1. Let ⊂Rnbe a convex set. Let γ:Rq→Rbe a guage in Rqwith unit ball B,letf=(f1,... ,f q):→Rqbe a d.c. mapping, with d.c. decomposition known: fi=f+ i−f− i, with f+ i,f− iconvex. For any i=1,... ,q,letMi⩾max{γ(e i), γ (−ei)},whereeiis the ith unit vector of Rq. Then, γ◦f:→Ris a d.c. function and a d.c. decomposition for it is given by γ◦f=γ◦f+ q  i=1 Mi(f + i+f− i)− q  i=1 Mi(f + i+f− i). (3.6) Now we present a detailed description of the algorithm. Step 0. Choose ε1>0andε2>0 and set ε=(ε1,ε 2). Step 1. Solve the unconstrained minimization problem associated with the first criterion: min x∈R2T1(x) := h(D1(γ1(x −a1)), . . . , Dn(γn(x −an))). (P0) The assumptions on Diand hallow us to ensure that (see Hiriart-Urruty and Lemaréchal, 1993) PROPOSITION 3.2. Function T1is convex. and (see Blanquero, 1999) PROPOSITION 3.3. Problem (P0)has always a finite optimal solution An optimal solution for (P0)can be obtained by the usual techniques in Convex Optimization, although there exist particular cases for which we can use specific methods (see Plastria, 1995 and the references therein). In what follows, x∗ 0will denote an optimal solution for (P0). Step 2. Construct the set of Voronoi cells V(A−)={V1,... ,V m}associated with the negatively affected regions Ri,i=1,... ,m. Once V(A−)has been built we must find a Voronoi cell Vkcontaining the point x∗ 0: dR(x∗ 0,R k)=min 1⩽i⩽mdR(x∗ 0,R i). If x∗ 0belongs to more than one Voronoi cell, we select anyone of them. If x∗ 0is feasible, we define the index set I={i:1⩽i⩽m, i = k,Vi∩S=∅} andgotoStep3.Otherwise,wedefineI={i:1⩽i⩽mVi∩S=∅}and go to Step 4. Step 3. Obtain a finite ε-dominating set for the set Vk∩S. The following result asserts that x∗ 0ε-dominates every point in a given subset of Vk∩S. A D.C. BIOBJECTIVE LOCATION MODEL 143 PROPOSITION 3.4. Given Ek={x∈Vk:dR(x, Rk)⩽dR(x∗ 0,R k)}, the point x∗ 0, optimal solution of (P0), (0,0)-dominates every point ˜x∈Ek∩S. Proof. By the choice of x∗ 0one has that T1(x∗ 0)⩽T1(˜x) for every ˜x∈Ek∩S. On the other hand: min 1⩽i⩽mdR(˜x,Ri)=dR(˜x,Rk)⩽dR(x∗ 0,R k)=min 1⩽i⩽mdR(x∗ 0,R i) from where it follows that T2(x∗ 0)⩾T2(˜x). Taking into account both inequalities we conclude that x∗ 0(0,0)-dominates ˜x. Now our aim is to obtain a finite ε-dominating set for (Vk\Ek)∩S. We consider the sequence {rj}∞ j=0, recursively defined as r0=dR(x∗ 0,R k)r j=rj−1+ε2j∈N, as well as the sets Ck j={x∈R2:dR(x, Rk)=rj}j=0,1,... Dk j={x∈R2:rj⩽dR(x, Rk)⩽rj+1} The boundary of Rkis composed by line segments and circumference arcs, from where we conclude that Ck jcan be written as a finite union of these elements. On the other hand, Sis bounded and, therefore, we can ensure the existence of an index Jk∈Nin such a way that the set j⩽JkDk j∩Vk∩Scovers (Vk\Ek)∩S. We are now going to describe a procedure for obtaining a point that ε-dominates the set Dk j∩Vk∩S, yielding a finite ε-dominating set for j⩽JkDk j∩Vk∩S.In order to find these ε-dominating points we consider, for each index j=0,... ,J k, the set ˜ Ck jdefined as ˜ Ck j=(Ck j∩Vk∩S) ∪(Dk j∩bd(Vk∩S)) as well as the optimization problem min{T1(x) :x∈˜ Ck j}.(Pk j) Observe that bd(Vk∩S) =(bd(Vk)∩S) ∪(Vk∩bd(S)) since Vkand Sare closed. EXAMPLE 3.5. Consider a biobjective location problem with two negatively affected regions R1and R2, defined as the square of vertices (−1,1),(−1,−1), (1,−1)and (1,1), and the point (5,0), respectively, as well as three demand points P1=(1,2),P2=(3,−1)and P3=(4,1)(see Figure 1). The transportation cost from the facility to each demand point is imposed to be proportional to the 144 R. BLANQUERO AND E. CARRIZOSA Figure 1. Example of set ˜ Ck j Euclidean distance separating them, the weighting factors being w1=5, w2=4 and w3=3. The feasible region Sis assumed to be the rectangle with vertices (−2,−3),(−2,5),(8,5)and (8,−3). The Voronoi cells V1and V2associated with R1and R2have a common edge consists of two rays and a parabolic arc connecting them. On the other hand, the optimal solution for (P0)is the point (2.6030, 0.6673), that belongs to the Voronoi cell V1,(k =1), and it is feasible. In Figure 1 we show, for ε2=1, the sets C1 0,C1 1and C1 2,aswellas ˜ C1 1using wide line.  The set ˜ Ck jcan be expressed as a finite union of Uk jclosed conic arcs, since Ck j, bd(Vk)and bd(S) satisfy this property. For all of these arcs it is possible to obtain a d.c. parametric representation with known d.c. decomposition (Blanquero, 1999) (for the sake of simplicity, we omit the indices jand k): Au:t∈[0,1] → (xu(t), yu(t)) u =1,... ,Uk j. Hence, the resolution of (P k j)reduces to solving a finite number Uk jof univariate problems of the form min t∈[0,1]h(D1(γ1(Au(t) −a1)), . . . , Dn(γn(Au(t) −an))) u =1,... ,Uk j. (3.7) The following result asserts that a d.c. decomposition for every component of the objective in (3.7) can be obtained. A D.C. BIOBJECTIVE LOCATION MODEL 145 PROPOSITION 3.6. For every index i=1,... ,n and u=1,... ,Uk j,ad.c. decomposition for the function Giu(t) =Di(γi(Au(t) −ai)) t ∈[0,1] can be computed. Proof. First, note that Auis d.c. with known d.c. decomposition, since it is a parameterization of a conic arc, and also that γi(Au(t) −ai)is d.c. since it is the composition of a guage with a d.c. function; moreover, by Proposition 3.1, one has a d.c. decomposition for this function: γi(Au(t) −ai)=F+ iu(t) −F− iu(t). Taking into account the continuity of the functions involved and the compactness of the domain of definition, we can assume without loss of generality that F+ iu and F− iu are non-negative. On the other hand, let Li⩾max{γi(x −ai):x∈S}, so one has that: 0⩽γi(Au(t) −ai)⩽Li∀t∈[0,1]. Then, Proposition 3.7 in Tuy (1998) provides the following d.c. decomposition for Giu(t) : Giu(t) =(Giu(t) +Hiu(t)) −Hiu(t) where Hiu(t) =K(Li+F− iu(t) −F+ iu(t)) and Kis any constant satisfying K⩾ D i−(Li). REMARK 3.7. By Proposition 3.1 we have that an optimal solution for (P k j)can be obtained by solving a finite number of univariate d.c. optimization problems, with known d.c. decomposition for their objectives. In order to solve these one-dimensional problems, we can use any d.c. optimization method, such a Branch & Bound or covering algorithms (Baritompa and Cutler, 1994; Blanquero, 1999; Blanquero and Carrizosa, 2000; Breiman and Cutler, 1993). In the search of an ε-dominating point for the set Dk j, the following lemma will be needed. LEMMA 3.8. For every point ¯x∈Dk j∩Vk∩S, with j⩾0, one has that [x∗ 0,¯x]∩ ˜ Ck j=∅ Proof. We can assume that j>0, since x∗ 0∈˜ Ck 0.Given ¯x∈Dk j∩Vk∩S, one has that dR(x∗ 0,R k)=r0<r j⩽dR(¯x,Rk), and then, by continuity of the distance, [x∗ 0,¯x]∩Ck j=∅. 146 R. BLANQUERO AND E. CARRIZOSA Let ¯y∈[x∗ 0,¯x]∩Ck j.If ¯y∈Vk∩S, it follows immediately that ¯y∈˜ Ck j,and the result is shown in that case. Therefore, assume that ¯y∈ Vk∩Sand consider a point ˆybelonging to bd(Vk∩S) ∩[¯x, ¯y], which is non-empty, since ¯y∈ Vk∩S, ¯x∈Vk∩Sand Sis robust. We are now going to show that ˆy∈Dk j. In order to achieve this, first recall that the inf-distance function dR(·,R i)is quasi-convex, (Hiriart-Urruty and Lemaréchal, 1993), so the set N(i) α={x∈R2:dR(x, Ri)⩽α}is convex for all α⩾0. The point ˆymust satisfy that dR(ˆy,Rk)⩾rjsince, in other case, we consider d=max{dR(ˆy,Rk), r0}, that it is strictly less than rj. Taking into account that ¯y∈[x∗ 0,ˆy]and that dR(¯y,Rk)=rj>d, we conclude that ¯y∈ N(k) d, and this contradicts the convexity of this set, since ˆy∈N(k) dand x∗ 0∈N(k) d. On the other hand, from ¯y∈Ck j,¯x∈Dk jand the quasi-convexity of the function dR(·,R i), it follows that dR(ˆy,Rk)⩽rj+1and, therefore, ˆy∈Dk j, showing the result.  Using this lemma, the following proposition provides a finite ε-dominating set for the feasible points in the Voronoi cell Vklocated at a distance from Rkbetween rjand rj+1. In the sequel, x∗ kj will denote an ε1-optimal solution for Problem (P k j). PROPOSITION 3.9. Given j⩾0, the point x∗ kj ε-dominates each point ˜x∈Dk j∩ Vk∩S. Proof. Given a point ˜x∈Dk j∩Vk∩Swe have that: min 1⩽i⩽mdR(˜x,Ri)=dR(˜x,Rk) ⩽rj+1(3.8) =rj+ε2 ⩽dR(x∗ kj ,R k)+ε2(3.9) =min 1⩽i⩽mdR(x∗ kj ,R i)+ε2(3.10) where (3.8) is a consequence of ˜x∈Dk j, whereas (3.9) and (3.10) follow from x∗ kj ∈Dk j∩Vk. This shows the ε-dominance of x∗ kj with regard to the second objective. On the other hand, Lemma 3.8 asserts the existence of a point ˆx∈[x∗ 0,˜x]∩ ˜ Ck j⊂ Sand, by convexity of the first objective, it follows that: T1(x∗ 0)⩽T1(ˆx) ⩽T1(˜x). The point x∗ kj is an ε1-optimal solution of minimizing T1over ˜ Ck jand, hence: T1(x∗ kj )−ε1⩽T1(ˆx) ⩽T1(˜x) completing the proof.  A D.C. BIOBJECTIVE LOCATION MODEL 147 Step 4. Obtain a finite ε-dominating set for every set Vl∩S, with l∈I. Consider the problem min{T1(x) :x∈bd(Vl∩S)}(Pl) which has a finite optimal solution, by the compactness of the feasible set and the continuity of the objective. Taking into account that bd(Vl∩S) consists of conic arcs, for which we can obtain a d.c. parameterization, an optimal solution for (Pl) can be found by solving a finite number of univariate d.c. optimization problems. The following result asserts that any ε1-optimal solution of (Pl)(ε 1,0)-dominates every point in Vl∩Snot further from Rlthan the former. We omit the proof of this and the remaining results proposed in this stage, since they are similar to those provided in Step 3 (see Blanquero, 1999, for details). PROPOSITION 3.10. For l∈I,letx∗ lbe an ε1-optimal solution for Problem (Pl) and El={x∈Vl:dR(x, Rl)⩽dR(x∗ l,R l)}.Thenx∗ l(ε1,0)-dominates every point ˜x∈El∩S. We consider the sequence {rj}∞ j=0, recursively defined as r0=dR(x∗ 0,R k)r j=rj−1+ε2j∈N, as well as the sets Cl j={x∈R2:dR(x, Rl)=rj} Dl j={x∈R2:rj⩽dR(x, Rl)⩽rj+1}. The outline of the procedure consists of obtaining an ε-dominating point for every set Dl j∩Vl∩S,j⩾0, as in Step 3, for which we consider the set ¯ Cl j,definedas ¯ Cl j=((Cl j−1∪Cl j)∩Vl∩S) ∪(Dl j−1∩bd(Vl∩S)), as well as the optimization problem min{T1(x) :x∈¯ Cl j}.(Pl j)) EXAMPLE 3.11. In Figure 2 we show the sets C2 0,C2 1and C2 2,aswell ¯ C2 2using wide line, for the problem considered in Example 3.5, taking ε2=0.8inthis case.  The set ¯ Cl jcan be written as a finite union of Ul jclosed conic arcs, since Cl j−1, Cl j,bd(Vl)and bd(S) satisfy this property. For all of these arcs it is possible to obtain a d.c. parametric representation wit known d.c. decomposition (for the sake of simplicity, we omit the indices jand l): Au:t∈[0,1] → (xu(t), yu(t)) u =1,... ,Ul j. 154 R. BLANQUERO AND E. CARRIZOSA Breiman, L. and Cutler, A. (1993), A deterministic algorithm for global optimization, Mathematical Programming 58, 179–199. Carrizosa, E., Conde, E. and Romero-Morales, M.D. (1997), Location of a semiobnoxious facility: a biobjective approach, in Advances in Multiple Objective and Goal Programming, R. Caballero, F. Ruiz and R.E. Steuer (Eds.), Springer, Berlin. Carrizosa, E. and Plastria, F. (1999), Location of semi-obnoxious facilities, Studies in Locational Analysis 12, 1–27. Chen, P.C., Hansen, P., Jaumard, B. and Tuy, H. (1992), Weber’s problem with attraction and repulsion, Journal of Regional Science 32, 467–486. Hansen, P. and Thisse, J.F., The generalized Weber-Rawls problems, in Operations Research 1981, J.P. Brans (Ed.), North-Holland, Amsterdam. Hiriart-Urruty, J.B. and Lemaréchal, C. (1993), Convex Analysis and Minimization Algorithms I, Springer, Berlin. Lemaire, B. (1992), Approximation in multiobjective optimization, Journal of Global Optimization 2, 117–132. Mehlhorn, K. and Näher, S. (1995), LEDA, a platform for combinatorial and geometric computing, Communications of the ACM 38, 96–102. Mehlhorn, K. and Näher, S. (1999), LEDA, a Platform for Combinatorial and Geometric Computing, Cambridge University Press, Chichester. Maranas, C.D. and Floudas, C.A. (1994), A global optimization method for Weber’s problem with attraction and repulsion, in Large Scale Optimization: State of the Art, W.W. Hager et al. (Eds.), Kluwer Academic Publishers, Dordrecht. Michelot, C. (1993), The mathematics of continuous location, Studies in Locational Analysis 5, 59– 83. Nickel, S. and Dudenhoffer, E.M. (1997), Weber’s problem with attraction and repulsion under polyhedral gauges, Journal of Global Optimization 11, 409–432. Okabe, A., Boots, B. and Sugihara, K. (1995), Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley & Sons, Chichester. Plastria, F. (1995), Continuous location problems, in Facility location. A Survey of Applications and Methods, Z. Drezner (ed.), Springer, New York. Tuy, H. (1995), D.C. optimization: theory, methods and algorithms, in Handbook of Global Optimization, Kluwer Academic Publishers, Dordrecht. Tuy, H., Al-Khayyal, F. and Zhou, F. (1995), A D.C. optimization method for single facility location problems, Journal of Global Optimization 7, 209–227. Tuy, H. (1998), Convex Analysis and Global Optimization, Kluwer Academic Press, Dordrecht. Vincke, P. (1992), Multicriteria Decision Aid, Wiley, New York. White, D.J. (1996), Epsilon efficiency, Journal of Optimization Theory and Applications 49, 319– 337. White, D.J. (1998), Epsilon dominance and constraint partitioning in multiple objective problems, Journal of Global Optimization 12, 435–448.