Polynomial algorithms for parametric minquantile and maxcovering planar location problems with locational constraints

Sociedad de Estadr e lnvestigaci6n Operativa Top (1998) Vol. 6, No. 2, pp. 179-194 Polynomial Algorithms for Parametric Minquantile and Maxcovering Planar Location Problems with Locational Constraints Emilio Carrizosa Departamento de Estadlstica e 1.0. Universidad de Sevilla Tarfia s/n, 41012 Sevilla, Spain [email protected] Frank Plastria Center ]or Industrial Location Vrije Universiteit Brussel Pieinlaan, 2, 1050 Brussels, Belgium Frank. Piastria @vub.ac.be Abstract A location is sought within some convex region of the plane for the central site of some public service to a finite number of demand points. The parametric maxcovering problem consists in finding for each R > 0 the point from which the total weight of the demand points within distance R is maximal. The parametric minimal quantile problem asks for each percentage a the point minimising the distance necessary for covering demand points of total weight at least a. We investigate the properties of these two closely related problems and derive polynomial algorithms to solve them both in case of either (possibly inflated) Euclidean or polyhedral distances. Key Words: maximal covering, minimal quantile, single facility location, Euclidean distance, polyhedral distance, sensitivity analysis AMS subject classification: 90B85, 90C31. 1 Introduction Let A = {al,... , ap} C R 2 be a set of demand points, requiring for a certain public service, the location of which is to be determined within a closed convex set X. Due to the public nature of the service, the minimisation of the maximum distance seems to be a plausible criterion. However, if some The research of the first author is partially supported by Grant PB96-1416-C02-02 of Ministerio de Educaci6n y Cultura, Spain Received: December 1997; Accepted: November 1998 180 E. Carrizosa and F. Plastria of the demand points are far away from the rest (outliers), the classical minmax solution might be very unsatisfactory, since large numbers of demand points might suffer from low-level (far off) service only due to full concern for the (few) outlying ones. Very often this leads to an unacceptable low service level for most. Two ways to avoid this drawback could be : 1. Provide a service as good as possible to a given minimal portion c~ El0, 1] of the potential demand for the service, in detriment of the rest. 2. Fix a standard R (seen as the highest acceptable distance between the server and the demand), and maximize the part of demand within this radius. We call model 1. the minimal quantile problem. In spite of its immediate practical interest this type of model seems to be new in the literature on location. Model 2. corresponds to the well-known maximal covering problem, for which some very efficient algorithms have been proposed in the unconstrained case (X = R 2) and Euclidean distance, see Drezner (1981) and Mehrez-Stulman (1982). Both models, however, rely on the choice of a parameter, either ~ or R. And although having a clear interpretation it may often be felt as artificial to fix such a parameter a priori, without any knowledge of its impact on the quality of the resulting optimal solutions. It follows that it is of high practical interest to obtain a sensitivity analysis with respect to this parameter. The existing solution methodology mentioned above for the maxcovering problem does not readily allow to analyse the effects of modifying the radius R. In this paper we show how both these problems may be solved simultaneously for all c~ and R. After stating the problems formally in section 2, a general algorithm is described in section 3. This algorithm calls for repeated solution of certain subproblems. These subproblems are studied in detail in section 4. The next two sections discuss how the proposed methodology yields polynomial algorithms in the Euclidean distance case and in the polyhedral gauges case respectively. In the concluding section some extended complexity results are stated, and the extension to the location of several facilities is discussed. Minquantile/Maxcovering Planar Location 181 2 Problem formulations For i E {1, .... ,p}, let 7i be a gauge in R 2 (the asymmetric equivalent to norms, see Durier and Michelot (1985)), and define the function giving the distance of a point x to demand point ai as k : R 2 --+ R:x := - Let wi > 0 be a weight associated with demand point ai, representing e.g. a population, frequency of demand, risk of emergency, etc. Without loss of generality we assume that P Y~i=I Wi = 1. Consider the functions C: [0,+oc[xR2~R+ : (R,x)~--~C(R,x):= ~ wi ill, (x)<R and Q : ]0,1] x IR 2 -+ R+ : (~, x) ~+ Q(&, x) :-- min maxfi(x) IESo iEI with So = {I C {1,... ,p} ] Y]ietwi >_ o~}. C(R,x) represents the covering, i.e. the total weight of demand points within distance R of x, as measured by the fi. Q(o~, x) is the smallest distance from x within which at least total weight c~ of demand points may be found, in other words, the a-quantile of the distribution of demand distances from x with the weights as frequencies. Given R E [0,+oo[ and c~ E]0,1], let MCR and MQ~ be the R- maxcovering problem and ot-minquantile problem defined by : (2llCR) C*(R):= maxC(R,x) xEX (MQo) Q*(c~) := minQ((~,z) xEX We will call any x E X such that C(R, x) = C'(R) (resp. Q(a, x) = Q*(a)) an R-maxcovering point (resp. an o~-minquantile point). Solving MCR consists in finding the point from which the total weight of the demand points covered (within distance R) is maximal. This corresponds to the problem discussed by Drezner (1981) and Mehrez-Stu|man (1982), where 182 E. Carrizosa and F. Plastria only Euclidean distances are considered and no Iocational constraints are present. MQ, asks for the point where the distance necessary for covering demand points of total weight at least c~ is minimal. This problem seems to be new in the location literature. Our aim is to show how to fully construct the functions C* and Q* in an efficient way, in other words how to solve problems MCR and MQa for all values of R and c~. We call these problems the parametric maxcovering problem and the parametric minquantile problem. 3 A general algorithm The parametric problem MQ belongs to the class of minquantile optimisation problems introduced by the authors in a recent paper (Carrizosa and Plastria, 1995), where a general solution procedure was described. In the context of location theory, as treated here, this procedure may be further detailed. Following notation will be used. For any I C_ {1,... ,p},I ~ 0 , let Z I -~ min maxfi(x), xEX iEl MI = {x E X I Vi E I : fi(x) <_ zt} SI = {x E X I Vi E I: fi(x) = zI} and consider the optimisation problem PI, P (PI) max ~witi(x) xEXt ~=1 1 if fi(x) < z1 where ti(x) = 0 otherwise for i--- 1,... ,p. If Pt is feasible, denote by xt an optimal solution, (~t the optimal value and vi := (xI, zi, st). As shown by Carrizosa and Plastria (1995) for any there exists an optimal solution to MQ~ of the form xl with card(l) < 3. In this case c~ _< st. The algorithm of Carrizosa and Plastria (1995), has the following steps: Algorithm 1. Step 1 : Generate the candidate solutions Build the list Z~ = {vt: I C_ {1,..., p}, card(l) < 3, Pt is feasible}. Minquantile/Maxcovering Planar Location 183 Step 2 : Preprocess list ~: Sort the elements in s in nondecreasing order of o~ I. Step 3 : Eliminate dominated solutions For each C = (x ~,z ~,cd) E s in turn from the last to the first : Let v = (x,z,a) be the (now) next element in s (note that by step 2 (~t _< ~): If z' _> z delete v t from s O After performing the algorithm above, we have obtained an ordered list s := {Vm I m = 1,...,t}, with Vm = (Xm,Zm,am), and thanks to step 2 we have al < a2 < ... < at = 1. Setting (~0 = 0, at+l = +oc, Q*(ao) = O, Q*(at+l) = +oc, we have Theorem 3.1. I. Vm E {1,..., t}, E]C m_l, xm is an a-minquantile point, and = zm. 2. Vm E {1,... ,t}, VR E [Q*(am),Q*(am+l)[, xm is an R-maxcovering point and C*(R) = am. Proof. This is a direct consequence of theorems 2 and 3 in Carrizosa and Piastria (1995), using the fact that the fi are gauges and hence convex, continuous and have compact level sets. [] The first part of this theorem indicates that the list s gives a complete description of Q*, and the second part shows how this also solves the parametric maxcovering problem MC. Hence, the information gathered in list s enables us to simultaneously solve both parametric problems, and clearly shows the link between minquantile and maxcovering optimisation: for any radius R we obtain from s a value a, ~(R), and an (~-minquantile solution which is also a R-maxcovering point. Remark 3.1. al ---- maxl_<i<p wi and Q*(al) = 0. Indeed list s will contain all triples (ai, 0, wi) for 1 < i < p. In step 3 all of these will be deleted except one corresponding to the maximal weight. [] 184 E. Carrizosa and F. Plastria Remark 3.2. Denoting by C(p) the complexity of step 1 in the algorithm above the resolution of the parametric problems MC and MQ has a complexity O(max{p 3 log p, C(p)}). Proof. Indeed,/2 has cardinality 0(p3), and hence step 2 can be done in 0(p 3 logp) time; once/~ has been sorted step 3 can be performed in 0(p 3) time. This gives a total complexity of 0(max{p 3 log p, C(p)}), as asserted. [] In particular, as soon as step 1 can be performed in polynomial time, i.e., C(p) is polynomial in p, then both MC and MQ can be solved in polynomial time. As shown in sections 5 and 6, this will be the case of the most popular instances of distances, namely (inflated) Euclidean and polyhedral distances. Remark 3.3. Both the radius R and the coverage c~ may be considered as criteria, the first representing a cost, the second representing quality of service. In such a situation, we face the biobjective problem of minimizing R (the cost) and maximizing at the same time C(R, .) (the coverage) by the choice of the location x E X and the radius R. As suggested in Carrizosa and Plastria (1995) the set S of solutions {Xm I 1 <_ m < t} obtained from list /:' is a minimal dominating set, i.e. for any (x, R) there exists some m (1 < m _< t) such that R > Zm and C(R,x) <_ C(zm,Xm) = am. It follows that this biobjective problem may be reduced to a discrete one, with 0(p 3) candidate solutions. Any multicriteria decision making method may thus be applied. E.g. in case a utility function r C(R, x)) applies, the problem is solved by inspecting only S. [] Remark 3.4. The general algorithm remains valid when during step 1 any number of triplets (x, R, C(R, x)) are added to list/:. Indeed by the previous remark all of these will be deleted in step 3. [] Minquantile/Maxcovering Planar Location 185 4 Solving the subproblem P1 The general algorithm calls for repeated solution of problems of type PI P (PI) max Z witi(x) xEX1 . 1, iffi(x) <_ zz , fori= l,...,p where ti(x) = 0, otherwise The following results show that, whatever the gauges are, each 1~ can be solved by evaluating a set CI of candidate points, with cardinality 0(p). Furthermore, such CI is easily obtained once the minmax problem corresponding to I has been solved. Lemma4.1. Let I C {1,...,p}, I • 0. The set MI = {x E X I Vi E I : fi(x) < Zl} is a nonempty compact segment. It is a singleton when all gauges 7i are round. Proof. First observe that MI is included in the set Ui~! {x E R 2 1 fi(x) = zt}, which has empty interior. Hence, M/ has also empty interior. As the functions fi are translated gauges, it follows that MI is a nonempty compact convex set, thus MI is a segment. It was shown in Pelegrln, Michelot and Plastria (1985) that a minmax location problem with round gauges always has a unique optimal solution, whence the last assertion, o For any segment Y, denote by ext(Y) the set of its extreme points. By convention we assume that the empty set is a segment, with ext(0) = 0. Recall that XI = (x E X I Vi E I : fi(x) -~ Zl}. Lemma 4.2. Let I C_ {1,... ,p},I ~= 0. If Xt r MI, then XI C ext(M1). Proof. The result is evident if 1141 is a singleton : in that case, X! C_ M! = ext(M/) So we can assume that MI is not a singleton. By lemma 4.1, M1 is then a nondegenerate segment, the extreme points of which are some yl, Y2 E X. 186 E. Carrizosa and F. Plastria We are going to show that, ifXi is not contained in ext(Ml) = {yl, Y2}, then MI = XI. Hence, suppose that there exists x E X! \ {Yl,Y2}. As Mr is a segment and XI C MI, there exists a ~ El0, 1[such that x = (1-,k)yl+,ky2. For any i E I we have : ZI = S (x) = S ((1 - x)vl + < (1 - *k)fi(Ul) + Aft(y2) _< (1 -- )~)Z I + ,~Z I ---- Z I -~- Z I by definition of XI by convexity of fi by definition of z! Thus fi(Yl) = fi(Y2) = zI for all i E l, i.e.: ext(Mi) _C X I. Now, for any y E MI \ {Yl, Y2, x} it follows that x is contained in the open segment whose extreme points are y and a point in ext(Ml), Yl say. Then there exists # El0, 1[ such that x = (1 - #)Yl + #Y and for any i E I we have ZI = fi(X) <_ (1 -- P)fi(Yl) + ~fi(Y) <_ (1 - It)zi -3 t- ~Zl = Zl Thus y E Xt for all y E Mr, i.e.: Mr C_ Xt. As MID XI, we would have Mr = XI. [] Theorem 4.1. Let I C_ {1,... ,p} be such that PI is feasible (XI • 0). Then the set Ci -- ext(MI) U U ext({x e Mr I fk(X) ~_ ZI}) k~l contains an optimal solution to PI. Proof. If X1 C ext(M/), there is nothing to show. So, we can assume that X1 is not included in ext(Mi), or by lemma 4.2 that Xi = MI. Let x E X1 = MI, K = {k ~ I I A(x) < Zl}, and YK = {Y E MI I A(Y) <_ zI I Vk E K}. Since Yts" = Mr N[']keK{y E R 2 I fk(Y) < zI} and x E YK, it follows that YK is a nonempty closed convex segment, with ext(YK) C_ CI. Furthermore, ~]f=l wjtj(z) = Y~deluK wj <_ P Y~d=l wjtj (y) for any y E YK and in particular for y E ext(YK) C_ CI. Hence, P p p max ~ wjtj(x) < max E wjti(Y) < max E wjtj(x) xEXI -- YECI 3=1" -- xEMI J=l" Minquantile/Maxcovering Planar Location 187 as asserted and the result follows from XI -- Mr. [] This theorem shows that finding a solution to P! reduces to inspection of at most 2p points on the segment Mr. This shows that as soon as each Zl and CI can be obtained in polynomial time, step 1 in the general algorithm (and hence the whole algorithm) can be performed in polynomial time. In the next two s~tions this is shown to be possible in presence of linear constraints for inflated Euclidean norms and also for polyhedral gauges. 5 The inflated Euclidean-norm case Let X be a polyhedron (not necessarily bounded) in R 2. Assume that, for all i, 1 < i < p, 7i = hill.l[, where I1.11 is the Euclidean norm, and hi > 0. Different values of hi might indicate differences in speed due to the use of different transportation modes. For X = R 2, algorithms for problem MCR (R fixed) have been discussed by Drezner (1982), with complexity 0(p 2 logp), and by Chazelle and Lee (1986) for the unweighted case, with complexity 0(p2). Tamir (1993) pointed out to us that this latter method may be extended to the weighted case without deterioration of the complexity. However, these techniques cannot be used for sensitivity analysis in R, and do not give any information regarding minquantile problems. The following properties of the norm and the polyhedral nature of X enable an explicit construction of the list Z: in step 1 of the algorithm: Property 1 The Euclidean norm is strictly convex. Hence, any minmax problem has a unique solution, i.e.: for any I, MI is a singleton. Property 2 For any i,j, 1 < i < j <, p, the mediatrix med(i,j) between ai and aj, med(i,j) = {x E R2I hi II x - ai II = ,Xj II x - aj II} can be easily determined. Indeed, it is well known that, if hi = hi, med(i,j) is the straight line orthogonal to the segment connecting ai and aj and passing through its midpoint. On the other hand, if hi r hi, then med(i,j) is the circle centered at + 2 2aJ )~ - )~ij a` h i - )~j 194 E. Carrizosa and F. Plastria Drezner, Z. (1981). On a modified one-center model. Management Science, 27, 848-851. Durier, R. and C. Michelot (1985). Geometrical properties of the Fermat-Weber problem. European Journal of Operational Research, 20, 332-343. Hearn, D.W. and J. Vijay (1982). Efficient algorithms for the (weighted) minimum circle problem. Operations Research, 30, 777-795. Mehrez, A. and A. Stulman (1982). The maximal covering location problem with facility placement on the entire plane. Journal of Regional Science, 22, 361- 365. Pelegrln, B., Michelot C. and F. Plastria (1985). On the uniqueness of optimal solutions in continuous location theory. European Journal of Operational Research, 20, 327-331. Tamir, A. (1993). Private communication.