Extensive facility location problems on networks with equity measures

ARTICLE IN PRESS Discrete Applied Mathematics ( ) – Contents lists available at ScienceDirect Discrete Applied Mathematics journal homepage: www.elsevier.com/locate/dam Extensive facility location problems on networks with equity measures Justo Puertoa,∗, Federica Riccab, Andrea Scozzaric aUniversidad de Sevilla, Dep. Estadistica e Investigación Operativa, Spain bUniversità di Roma “La Sapienza”, Dip. Statistica, Probabilità e Statistiche Applicate, Italy cUniversità di Roma “La Sapienza”, Dip. Matematica per le Decisioni Economiche, Finanziarie ed Assicurative, Italy article info Article history: Received 20 July 2007 Accepted 28 March 2008 Available online xxxx Keywords: Path location Range criterion Hurwicz criterion Pareto-optimal paths abstract This paper deals with the problem of locating path-shaped facilities of unrestricted length on networks. We consider as objective functions measures conceptually related to the variability of the distribution of the distances from the demand points to a facility. We study the following problems: locating a path which minimizes the range, that is, the difference between the maximum and the minimum distance from the vertices of the network to a facility, and locating a path which minimizes a convex combination of the maximum and the minimum distance from the vertices of the network to a facility, also known in decision theory as the Hurwicz criterion. We show that these problems are NP-hard on general networks. For the discrete versions of these problems on trees, we provide a linear time algorithm for each objective function, and we show how our analysis can be extended also to the continuous case. © 2008 Elsevier B.V. All rights reserved. 1. Introduction Network facility location problems consist of locating a specified number of facilities in a network in order to supply a set of costumers. Commonly used objective functions are either the sum of the distances from each client to its nearest facility (median criterion), or the maximum of these distances (center criterion). Starting from the location of one or a set of points, which can be either vertices or points along the edges, several authors extended the theory to facilities with a connected structure (extensive facilities), such as path-shaped or tree-shaped facilities [5,17,19]. For a comprehensive review, see, for example, [3,15,21]. Although median and center are the most representative objective functions in location problems, none of these two criteria alone is able to capture all the essential elements of a location problem. In recent years some papers considered the problem of finding an optimal location of a path or a tree using the two criteria simultaneously, or a convex combination of them [1,2,13,20], or by considering the general ordered median objective [16]. Nevertheless, also in these cases some salient features of real problems, like the dispersion of the clients’ demand with respect to a facility, are not captured. The dispersion is a concept strictly related to the variability of the distribution of the distances from the demand points to a facility. In particular, the issue of equity seems to be relevant when locating facilities in the public sector applications. In the literature there are two main lines of research about equity measures. The first one deals with how to measure equity and which properties equity measures should have. The second line of research is concerned with providing efficient algorithms for the location of facilities in a network according to some equity measure. A review of the existing literature about equity measures in location theory is given in [10]. In point location problems, efficient algorithms have been provided for the minimization of the variance of the distance travelled by a customer to a facility, as well as, for minimizing the range objective function, which is given by the difference between the maximum and the minimum ∗Corresponding author. E-mail addresses: [email protected] (J. Puerto), [email protected] (F. Ricca), [email protected] (A. Scozzari). 0166-218X/$ – see front matter © 2008 Elsevier B.V. All rights reserved. doi:10.1016/j.dam.2008.03.035 Please cite this article in press as: J. Puerto, et al., Extensive facility location problems on networks with equity measures, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.035 ARTICLE IN PRESS 2J. Puerto et al. / Discrete Applied Mathematics ( ) – distance from a facility [11]. Almost all the papers focusing on equity measures deal with the location of a single point on a network. An exception is [4] where the authors provide an O(n2log n)time algorithm for the location, on a tree network, of a path-shaped facility which minimizes the variance. In [14] the same problem is solved in O(n2)time. In this paper we consider the range objective function, as well as, the Hurwicz objective, which originates in decision theory [7,12] and is given by a convex combination of the maximum and the minimum distance from the vertices of the network to the facility. We study the problem of locating path-shaped facilities of unrestricted length on a tree where all the vertices have the same weight, while positive real lengths are associated to the edges. We focus on two main problems: locating a path which minimizes the range, and locating a path which minimizes the Hurwicz objective function. Moreover, we study the following two additional range-type constrained optimization problems: locating a path which minimizes the maximum distance subject to the minimum distance bounded below by a constant, and locating a path which maximizes the minimum distance subject to the maximum distance bounded above by a constant. Similarly, we study the following two additional Hurwicz-type problems: locating a path which minimizes the maximum distance subject to the minimum distance bounded above by a constant, and locating a path which minimizes the minimum distance subject to the maximum distance bounded above by a constant. To the best of our knowledge these six problems have not been considered in the literature, yet. We consider both the discrete version of the above problems, that is, when the endpoints of the path are vertices, and the continuous version, that is, when at least one endpoint belongs to the interior of an edge. For general networks we show that both versions of the six problems are NP-hard. For tree networks we provide the following results. In the discrete case, we solve all the six problems by adopting a bicriterion approach similar to those provided in [1,15], that is, we embed each of them into a suitable bicriteria problem related to the maximum and the minimum distance criteria. We provide two linear time dynamic programming algorithms for the range-type and Hurwicz-type problems, respectively. Given a tree with nvertices, each algorithm finds in O(n)time a superset that includes the representation of the set of Pareto-optimal paths in the outcome space, along with some extra points. We also show that the cardinality of this superset is O(n). Thus, solving the discrete versions of the above six problems is done in linear time by scanning this superset and evaluating the objective functions at each of its elements. Moreover, we show that the set of Pareto-optimal paths can be extracted from this superset in O(nlog n)time by using the algorithm provided by Kapoor [8]. In the continuous case, we provide an O(n2)time algorithm to solve the problem of minimizing the range function. We also provide algorithms that solve the range-type constrained optimization problems in O(n)time. For the Hurwicz-type problems we show that either no optimal path exists, or it reduces to the problem of locating a path which minimizes the maximum distance. For the implementation of our algorithms we need some quantities associated to each vertex of the tree. These quantities are computed in a preprocessing phase in time O(n). Some of the recursive functions adopted in this phase are already known in the literature, but some others are presented in this paper for the first time. The paper is organized as follows. In Section 2, we introduce the notation and definitions and prove the complexity results on general graphs. Section 3provides the recursive formulas for computing all the quantities needed in our algorithms. Section 4describes the algorithms for solving the range-type and the Hurwicz-type problems on trees. The paper ends with some concluding remarks and extensions. 2. Definitions, complexity results and basic properties Let T=(V,E)be a tree with |V| = n. Suppose that a weight equal to one is associated to each vertex of the tree, while a positive real length `(e)is assigned to each edge e∈E. Suppose that Tis rooted at a vertex rand denote by Trthe rooted tree. For any vertex v, let Tvbe the subtree of Trrooted at vertex v,S(v)the set of children of vin Tr, and p(v)the parent of vin Tr. Clearly, a vertex vis a leaf if and only if |S(v)| = 0. For any pair of points xand yin T, that may be vertices or may belong to the interior of an edge, we denote by P(x,y)the unique path connecting xand y. We denote by d(x,y)the length of P(x,y). In the following, we will avoid specifying one or both the endpoints of a path if not necessary. A path is discrete if both its endpoints are vertices of T, otherwise it is continuous. We denote by diam the diameter of T, i.e., the length of a longest path in T, and by cits absolute center, i.e., the middle point of the longest path in T. We denote by d(u,P)the distance from a vertex uto a path P, that is, the length of the shortest path from uto a vertex or an endpoint of P. For any point xin T, the eccentricity of xis E(x)=maxu∈Vd(u,x), while for any path Pthe eccentricity of Pis E(P)=maxu∈Vd(u,P). The absolute center cis the point in Tthat minimizes the eccentricity. The absolute center could be either a vertex, or a point along an edge. Finally, PC denotes the path center of T, that is, the shortest path that minimizes the eccentricity in T. It is well known that c∈PC and that PC is unique [6,18]. For a tree T=(V,E), we consider the range objective function which is defined as follows: R(P)=max u∈V\Pd(u,P)−min u∈V\Pd(u,P). (1) Given a path P, for any 0 ≤α≤1, we also consider the Hurwicz objective function: H(P)=αmax u∈V\Pd(u,P)+(1−α)min u∈V\Pd(u,P). (2) Both R(P)and H(P)are non negative variability measures. In this paper we suppose that the tree Tis not a path. Actually, since we are concerned with desirable facilities, when Tis a path, the solution is assumed to be the path itself. Please cite this article in press as: J. Puerto, et al., Extensive facility location problems on networks with equity measures, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.035 ARTICLE IN PRESS J. Puerto et al. / Discrete Applied Mathematics ( ) – 3 Table 1 Summary of results Range-type problems Hurwicz-type Problems Problem Discr. Cont. Problem Discr. Cont. P1 min R(P)O(n)O(n2)P4 min H(P)O(n)No optimal path exists P2 min E(P)s.t.µ(P)≥γO(n)O(n)P5 min E(P)s.t.µ(P)≤γO(n)O(n) P3 max µ(P)s.t.E(P)≤γO(n)O(n)P6 min µ(P)s.t.E(P)≤γO(n)No optimal path exists Given a path Pwe denote by µ(P)=minu∈V\Pd(u,P)the minimum distance from a vertex u6∈ Pto P. Given a subset I⊂V and a path Pwhose vertices are all in I, we denote by µI(P)=minu∈I\Pd(u,P)the minimum distance to Pfrom any vertex u∈Inot belonging to P. Clearly, µV(P)=µ(P). Given a path P, since d(u,P)=0 for each u∈P,(1) and (2) can be rewritten in the equivalent form: R(P)=E(P)−µ(P)(3) and H(P)=αE(P)+(1−α)µ(P). (4) In this paper we study six different path location problems of unrestricted length, both in their discrete and continuous version (see, Table 1). We show that these problems are NP-hard on general networks, while we provide new complexity results for all the problems on trees. These results are summarized above. Problems P1 and P4 are unrestricted optimization problems, while P2, P3, P5, and P6 arise when we want to locate a path which optimizes one criterion subject to a constraint on the other. Note that, problem P2 does not have any solution if γ > max{`(e)|e∈E}, while the discrete version of problem P5 does not have any solution if γ<min{`(e)|e∈E}. For problems P3 and P6 we assume E(PC)≤γ, otherwise the problems are infeasible. To the best of our knowledge the continuous and discrete versions of problems P1–P6 have not been considered in the literature yet, either on general networks, or on trees. It can be shown that problems P1–P6 are NP-hard on general networks, both in the continuous and in the discrete version. We first consider the discrete case. Problems P2 and P5 contain as a special case the problem of finding a path that minimizes the maximum distance from the vertices of a network to the facility. For P2 this happens when γ≤min{`(e)|e∈E}, while for P5 this happens when γ≥max{`(e)|e∈E}. Problem P4 contains as a special case the problem of finding a path that minimizes the maximum distance when α=1. Thus, Problems P2, P4, and P5 are NP-hard on general networks [5]. It can be shown that also problems P1, P3 and P6 are NP-hard on general networks by using arguments similar to those given in [5]. Let us start with the decision version of problem P1. Given an arbitrary graph G=(V,E)and a non negative number R0, decide if there exists a path Psuch that R(P)≤R0. We show that the Hamiltonian Path problem can be reduced to this problem. Let |V| = n, and suppose that a length equal to one is assigned to each edge e∈E. For each vi∈V,i=1, . . . , n, consider two additional vertices vi1and vi2, and construct a new graph G0=(V0,E0)such that V0=V∪Sn i=1{vi1,vi2}and E0=E∪Sn i=1{(vi,vi1), (vi,vi2)}. Assume that the edges added to Ghave length equal to 1/2. Set R0=0. It is easy to see that problem P1 has a solution in G0if and only if Ghas a Hamiltonian Path. Let us now consider the decision version of problem P3: given two non negative numbers µ0and M, decide if there exists a path Psuch that µ(P)≥µ0and E(P)≤M. We refer to the same reduction as above. We assign length equal to 1 to the original edges e∈E, and length equal to Mto the new edges. It is easy to see that, by setting µ0=2 and M≥2, problem P3 has a solution in G0if and only if Ghas a Hamiltonian Path. Finally, consider problem P6, and the same reduction as above. We still assign length equal to 1 to the original edges e∈E, and length equal to 1/2 to the new edges (vi,vi1),i=1, . . . , n, while a length equal to M0 is assigned to the new edges (vi,vi2),i=1, . . . , n. Consider the decision version of problem P6: given a positive number µ0, decide if there exists a path Psuch that µ(P)≤µ0and E(P)≤M. Set µ0=1/2. Also in this case, it is easy to see that problem P6 has a solution in G0if and only if Ghas a Hamiltonian Path. For the continuous versions of problems P2, P4 and P5, NP-hardness follows since each of them contains as a special case the problem of finding a continuous path that minimizes the maximum distance from the vertices of a network to the facility [5]. For the continuous versions of problems P1, P3 and P6, NP-hardness can be proved applying the same reduction as in the discrete case. Now we turn to consider the discrete version of our problems on trees. In the following we study the case when the absolute center is a vertex of T. Later, we will show that our analysis applies also when the absolute center is a point along an edge of T. Let Πdenote the set of all discrete paths of the tree T. For solving problems P1–P3, it is necessary to find the maximum of the minimum distances to a path P∈Π, while for solving P4–P6 we have to find the minimum of the minimum distances to a path P∈Π. Given a set S⊆Π, we define MS=maxP∈Sµ(P), for problems P1–P3, and mS=minP∈Sµ(P), for problems P4–P6. We root Tat the absolute center c. Suppose that PC 6= {c}, then we partition the set of vertices of Tcin the following way. Denote by v1one of the two vertices adjacent to calong PC. Let T1=Tv1=(V1,E1)be the subtree of Tcrooted at v1, and let Please cite this article in press as: J. Puerto, et al., Extensive facility location problems on networks with equity measures, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.035 ARTICLE IN PRESS 4J. Puerto et al. / Discrete Applied Mathematics ( ) – Fig. 1. The path P=P(a,b)has E(P)=101 and µ(P)=100. Any path connecting two leaves is dominated by Pw.r.t. 1. T2=(V2,E2), with V2=V\V1. Clearly, c∈V2. Thus, once T2has been identified, we consider T2rooted at c. On the basis of this decomposition, Πcan be partitioned into the three following sets: –P1, the paths that contain only vertices of V1; –P2, the paths that contain only vertices of V2; –P, the paths that pass through cand have exactly one endpoint in V1. Note that, if PC 6= {c}, any path P∈Pintersects PC in at least one edge. When PC = {c}we do not need to partition either the tree, or the set Π. Actually, in this case the rooted tree Tcis analyzed as a whole. For problems P1–P6, the idea of all the algorithms is similar to those presented in [1,15]. We consider our six problems embedded into bicriteria path problems with respect to the functions E(·)and µ(·). More precisely, we define the following two partial orders. Given a path P, a point (E(P), µ(P)) is non-dominated in the partial order 1, i.e., is a Pareto-optimal point with respect to 1, if there is no other path P∗with (E(P∗), µ(P∗)) such that E(P∗)≤E(P),µ(P∗)≥µ(P), and E(P∗)−µ(P∗) < E(P)−µ(P). A point (E(P), µ(P)) is non-dominated in the partial order 2, i.e., is a Pareto-optimal point with respect to 2, if there is no other path P∗with (E(P∗), µ(P∗)) such that E(P∗)≤E(P),µ(P∗)≤µ(P), and E(P∗)+µ(P∗) < E(P)+µ(P). For solving problems P1–P3 and P4–P6 we are interested in finding all the Pareto-optimal paths w.r.t the partial order 1and the partial order 2, respectively. We denote by πi⊆Πthe set of Pareto-optimal paths with respect to the partial order i,i=1,2. Note that |πi| ≤ O(n2), since the total number of paths in Tis O(n2). Proposition 1. Every optimal solution of problem P1 is also Pareto-optimal with respect to E(·)and µ(·), for the partial order 1. Moreover, for both problems P2 and P3 there is at least an optimal solution which is also Pareto-optimal for the partial order 1. In addition, every optimal solution of problem P4 is also Pareto-optimal with respect to E(·)and µ(·)for the partial order 2 and for both problems P5 and P6 there is at least an optimal solution which is also Pareto-optimal for the partial order 2. From an algorithmic viewpoint, for each of the above two partial orders, we consider a superset Wi,i=1,2 that includes the set of the Pareto-optimal paths in the outcome space (E(·), µ(·)) along with some extra paths, and we generate the following representation sets φ(Wi),i=1,2: φ(Wi)= {(E(P), µ(P)) ⊂R2|P∈Wi}i=1,2.(5) Given the tree rooted at c, we identify groups of paths in Tcwith the same value of the eccentricity (see Section 3). For problems P1–P3, among all the paths with the same eccentricity, we search for a path Pthat maximizes µ(·)and we include its representation in φ(W1). Similarly, for problems P4–P6, among all the paths with the same eccentricity, we search for a path Pthat minimizes µ(·)and we include its representation in φ(W2). Note that a Pareto-optimal path – both for 1and 2– does not necessarily connect two leaves of the tree. An example for 1is shown in Fig. 1. 3. Recursive formulas In order to solve efficiently the problems presented in this paper, a preprocessing phase is needed to compute some quantities that will be used in the algorithms. In the following we describe the recursive formulas computed during this preprocessing phase. First of all we consider paths in P1or in P2. We identify each path Pwith the vertex at which the maximum distance to Pis attained from a vertex u6∈ P. Given the rooted tree Tcand a vertex v∈V, denote by Pva path in Tvpassing through vor having vas an endvertex, and by P(Tv)the set of all such paths. Since each vertex v∈Videntifies all the paths in P(Tv), and these paths have the same eccentricity, we denote this common value by EP(Tv). For each v∈V, the value of this maximum distance can be computed in constant time applying the following result provided in [1]: Please cite this article in press as: J. Puerto, et al., Extensive facility location problems on networks with equity measures, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.035 ARTICLE IN PRESS J. Puerto et al. / Discrete Applied Mathematics ( ) – 5 Theorem 1 ([1]). For any path P∈P(Tv), we have: E(P)=EP(Tv)=d(v,c)+diam 2.(6) On the basis of the results of Proposition 1, our algorithms visit the rooted tree bottom-up and compute the set φ(·)w.r.t. the partial orders 1and 2. Actually, w.r.t. paths in P1and P2, when 1is considered, for each vertex v∈V, among all the paths Pv∈P(Tv), with E(Pv)=EP(Tv), the algorithm computes the maximum value of µ(·)(problems P1–P3). When 2is considered, for each vertex v∈V, among all the paths Pv∈P(Tv), with E(Pv)=EP(Tv), the algorithm computes the minimum value of µ(·)(problems P4–P6). First of all, we consider problems P1–P3 in which, besides minimizing E(·), we are interested in maximizing µ(·). To this purpose, among all the paths Pv∈P(Tv), we want to find a path which maximizes the minimum distance from a vertex u∈Tv\Pvto Pv. A path with such a property, will be called best path of type 1. Let us define: β(v)=max Pv∈P(Tv) vendvertex ofPv µTv(Pv). Let d1(v)=min w∈S(v)`(v,w), with w1∈arg min{`(v,w)|w∈S(v)}; d2(v)=min w∈S(v)|w6=w1 `(v,w), with w2∈arg min{`(v,w)|w∈S(v), w6= w1}; d3(v)=min w∈S(v)|w6∈{w1,w2}`(v,w). We set d1(v)= +∞ when vis a leaf of Tc,d2(v)= +∞ when |S(v)| ≤ 1, and d3(v)= +∞ when |S(v)| ≤ 2. We define the label flag(v)which is equal to 0 either if the subtree Tvis a path, or if vis a leaf, and it is equal to 1 otherwise. It can be computed in a bottom-up level-by-level visit of the rooted tree Tc. For each vertex vof Tcwe have: flag(v)=0 if |S(v)| = 1 and flag(w)=0,or if |S(v)| = 0 1 otherwise,(7) where w∈S(v). Property 1. Let Pv∈P(Tv)be a path starting at vand connecting vto the descendants of a child w6= w1of v. We have: µTv(Pv)≤µTv({v})=d1(v).  After Property 1, in order to compute β(v), besides the single vertex vwith µTv({v})=d1(v), we need to evaluate only the paths connecting vand the descendants of w1, while all the other paths in Tvwith vas an endvertex can be ignored. Thus, for each vertex vof Tc,β(v)can be recursively computed as follows: β(v)=           +∞ if |S(v)| = 0 d1(v)if flag(v)=0 and |S(w1)| = 0 max{d1(v), β(w1)}if |S(v)| = 1 d2(v)if |S(v)|>1 and flag(w1)=0 max{d1(v), min{d2(v), β(w1)}} if |S(v)|>1 and flag(w1)=1. (8) Note that in the computation of β(v)we consider both the case in which the best path of type 1, Pv∈P(Tv)having vas an endvertex, is vitself and the case in which it includes at least one edge. Property 2. Let Pf,g v∈P(Tv)be a path passing through v, with |S(v)| ≥ 3, and connecting the descendants of two children fand gof v. Then, we have –if f=w1and g6= w2, then any best path Pvstarting at vand connecting vwith the descendants of w1has µTv(Pv)=d2(v)≥ µTv(Pw1,g v)(similarly if f6= w2and g=w1); –if f=w2and g6= w1, then any best path Pvstarting at vand connecting vwith the descendants of w2has µTv(Pv)=d1(v)≥ µTv(Pw2,g v)(similarly if f6= w1and g=w2); –if f,g6= w1,w2, then µTv({v})=d1(v)≥µTv(Pf,g v). Please cite this article in press as: J. Puerto, et al., Extensive facility location problems on networks with equity measures, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.035 ARTICLE IN PRESS 6J. Puerto et al. / Discrete Applied Mathematics ( ) – Fig. 2. Possible configurations for Tv. After Property 2, we need to evaluate only the paths connecting vand the descendants of w1and w2, while all the other paths in Tvpassing through v, can be ignored. Note that for any path Pw1,w2 vwe always have µTv(Pw1,w2 v)≤d3(v). Thus, the maximum of the minimum distances MP(Tv)of a best path of type 1, Pv∈P(Tv)(passing through vor having vas an endvertex) with respect to the whole tree Tccan be computed as follows MP(Tv)=   min{`(v,p(v)), β(v)}if |S(v)| ≤ 1 min{`(v,p(v)), max{β(v), min{β(w1), β(w2)}}} if |S(v)| = 2 min{`(v,p(v)), max{β(v), min{β(w1), β(w2), d3(v)}}} if |S(v)| ≥ 3, (9) where we set `(v,p(v)) = +∞ if vis the root of the tree. We note that for any given rooted tree Tr, formulas (7)–(9) can be applied to Trfor finding the maximum of the minimum distances of a best path of type 1 in P(Tv)w.r.t. the whole tree (see the example in Section 3.1). In our approach, when PC = {c}we must apply these formulas to Tc. On the other hand, when PC 6= {c}, formulas (7)–(9) must be computed on T1and T2separately. In this case, since the vertex cis evaluated as the root of T2, with EP(Tc)=diam 2, in formula (9) we set `(c,p(c)) =`(c,v1). Proposition 2. The labels (8) and (9) correctly compute the maximum of the minimum distances of a best path of type 1 Pv∈P(Tv)from all the other vertices in Tcnot belonging to Pv. Proof. First consider formula (8), which refers to the best paths of type 1 having vas an endvertex. When vhas exactly one child corresponding to a leaf, the best path is Pv= {v}with µTv({v})=d1(v). In all the other cases we base our analysis on Property 1. If |S(v)| = 1 (see Fig. 2(a)), we have to compare Pv= {v}only with a best path connecting vwith the descendants of its child w1. When |S(v)|>1 and flag(w1)=0 (see Fig. 2(b)), the maximum of the minimum distances of a best path of type 1 Pvis always equal to d2(v). In fact, consider β(w1): the maximum of the minimum distances to Pvwill be equal to d2(v)either if d2(v)≤β(w1), or d2(v)> β(w1), since, in the latter case, one can always extend Pvup to the leaf in Tw1. Note that in this case the path Pv= {v}is discarded in any case since d1(v)≤d2(v). When |S(v)|>1 and flag(w1)=1 (see Fig. 2(c)), if d2(v)≤β(w1), then the maximum of the minimum distances is d2(v) itself, but it is equal to max{d1(v), β(w1)}if d2(v)> β(w1)since, in this case, also the path Pv= {v}must be evaluated. On the basis of Properties 1 and 2, formula (9) first identifies the best path of type 1, Pv∈P(Tv), comparing, when necessary, the best path having vas an endvertex with the best path passing through vand connecting vwith the descendants of w1and w2. Then, the maximum of the minimum distances of a best path of type 1 Pv∈P(Tv)w.r.t. the whole tree Tcis computed by considering also the length of the edge (v,p(v)). In all the problems P1–P3 some additional considerations arise when PC 6= {c}and we have to compute the labels with respect to the paths in P. Given a pair of vertices p1,p2∈PC, the eccentricity of the subpath P(p1,p2)⊆PC is given by E(P(p1,p2)) =max diam 2−d(p1,c), diam 2−d(p2,c).(10) For any given subpath P(p1,p2)⊆PC, when diam 2−d(p1,c)≥diam 2−d(p2,c), we denote by P(p1)the set of all paths in P containing P(p1,p2), and having eccentricity equal to diam 2−d(p1,c). A generic path belonging to P(p1)will be denoted by Pp1p2. Similarly, we denote by P(p2)the set of all paths containing P(p1,p2)and having eccentricity equal to diam 2−d(p2,c). Since these two cases are symmetrical, w.l.o.g., we restrict our attention to paths belonging to P(p1). We denote the eccentricity of all the paths in P(p1)by EP(p1). Among all the paths Pp1p2∈P(p1), we are interested in finding a path which maximizes the minimum distance from all the vertices u∈T\Pp1p2. A path with such a property will be called a best path of type 2. Please cite this article in press as: J. Puerto, et al., Extensive facility location problems on networks with equity measures, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.035 ARTICLE IN PRESS J. Puerto et al. / Discrete Applied Mathematics ( ) – 7 Denote by ci,i=1,2 the endvertices of the path center PC. Let (p1,t)be the edge belonging to PC \P(p1,p2)such that t is a child of p1in Tp1. Assume that p16= c1,c2and p26= c1,c2. In order to find a best path of type 2, we have to find a best path of type 1 starting from p2in the subtree Tp2and a best path of type 1 starting from p1in the subtree Tp1\ {Tt∪(p1,t)}. We denote this latter particular best path of type 1 byb Pp1. The maximum of the minimum distances of a best path Pp2in Tp2 is computed by formula (8), while for b Pp1in Tp1\ {Tt∪(p1,t)}it is given by b β(p1)=min{qβ(p1), `(p1,t)},(11) where the new label qβ(v)can be computed during the bottom-up visit of the tree Tcfor all the vertices v∈PC and corresponds to formula (8) rewritten by considering the subtree Tv\ {Tt∪(v,t)}, where (v,t)∈PC and tis a child of v in Tv. Note that the maximum of the minimum distances of the best paths of type 1 b Pci,i=1,2, is computed by formula (8) w.r.t. the subtrees Tci,i=1,2, respectively. Thus, we set b β(ci)=β(ci),i=1,2. For a path P(u1,u2)we define the function mil(P(u1,u2)), i.e., the minimum incident length, as the minimum length of an edge not belonging to P(u1,u2), but incident to P(u1,u2)in one of the vertices g, with g6= u1,u2: mil(P(u1,u2)) =min (f,g)|g∈P(u1,u2)\{u1,u2} f6∈P(u1,u2) `(f,g). (12) Hence, for any given pair of vertices p1,p2∈PC for which a best path of type 2, Pp1p2belongs to P(p1), we denote by b MP(p1)(p2)the maximum of the minimum distances from Pp1p2to all the other vertices of the tree. On the basis of formulas (8),(11) and (12) we have: b MP(p1)(p2)=min{b β(p1), β(p2), mil(P(p1,p2))}.(13) Now, we turn to consider problems P4–P6 in which, besides minimizing E(·), we want to minimize µ(·). Given a rooted tree Tcand a vertex v∈V, among all the paths Pv∈P(Tv)we are interested in finding a path which minimizes the minimum distance from a vertex u∈Tv\Pv, to Pv. Also for the Hurwicz-type problems we refer to such a path as a best path of type 1, as long as this does not cause any confusion with a best path of type 1 of the range-type problems. Since the minimum distance from a vertex to a path is always given by the length of the shortest edge incident to the path, the value of the minimum distance from a vertex u∈Tv\Pv, to a best path of type 1, Pv∈P(Tv), corresponds to the length of the shortest edge contained in Tvthat we denote by eTv(if the shortest edge is not unique, we choose one arbitrarily). More precisely, the following property holds. Property 3. Given a rooted tree Tcand a vertex v∈V, a best path of type 1 (w.r.t. the Hurwicz problems) Pv∈P(Tv)is always given by the path in Tvconnecting vto the endvertex of eTvcloser to v. After Property 3, in order to compute the minimum of the minimum distances from a vertex u∈Tv\Pv, to a best path of type 1 Pv, for each vertex vit suffices to compute the minimum length of an edge in Tvin a bottom-up visit of the tree. We denote this quantity by h(v)and we have: h(v)=(min{d1(v), min w∈S(v){h(w)}} if |S(v)| ≥ 1, +∞ if |S(v)| = 0.(14) Then, the minimum of the minimum distances from a best path of type 1, Pv∈P(Tv), to all the other vertices of the tree is given by: mP(Tv)=min{`(v,p(v)), h(v)}if |S(v)| ≥ 1, `(v,p(v)) if |S(v)| = 0.(15) where `(v,p(v)) = +∞ if vis the root of T. When PC 6= {c}we evaluate the vertex cas the root of T2and, therefore, in formula (15) we set `(c,p(c)) =`(c,v1). We now analyze the paths in Pfor problems P4–P6 when PC 6= {c}. As before, we focus our attention only on paths in P(p1). Among all the paths Pp1p2∈P(p1)we are interested in finding a path which minimizes the minimum distance from all the vertices u∈T\Pp1p2. A path with such a property will be called a best path of type 2 (as long as this does not cause any confusion with a best path of type 2 of the range-type problems). Assume that p16= c1,c2and p26= c1,c2. Let (p1,t)be the edge belonging to PC \P(p1,p2)such that tis a child of p1∈Tp1. The minimum of the minimum distances of a best path of type 1, b Pp1in Tp1\ {Tt∪(p1,t)}is: b h(p1)=min{qh(p1), `(p1,t)},(16) where the new label qh(v)can be computed by formula (14) during the bottom-up visit of the tree Tcfor all the vertices v∈PC, but it has to be rewritten by considering the subtree Tv\ {Tt∪(v,t)}where (v,t)∈PC and tis a child of vin Tv. For vertex p2we compute the minimum of the minimum distances of a best path of type 1, Pp2in Tp2by formula (14). The minimum of the minimum distances of the best paths of type 1,b Pci,i=1,2, is computed by formula (14) w.r.t. the subtrees Tci,i=1,2, respectively. Thus, we setb h(ci)=h(ci),i=1,2. Please cite this article in press as: J. Puerto, et al., Extensive facility location problems on networks with equity measures, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.035 ARTICLE IN PRESS 8J. Puerto et al. / Discrete Applied Mathematics ( ) – Table 2 Bottom up labelling procedure Vertex 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 flag(v)0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 β(v)∞14 ∞ ∞ ∞ 14 ∞19 ∞9 19 20 ∞4∞15 10 MP(Tv)14 1 17 19 2 12 9 6 20 4 4 7 15 9 33 16 10 Fig. 3. An example. Finally, for any given pair of vertices p1,p2∈PC for which a best path of type 2, Pp1p2, belongs to P(p1), we denote by b mP(p1)(p2)the minimum of the minimum distances from Pp1p2to all the other vertices of the tree: b mP(p1)(p2)=min{b h(p1), h(p2), mil(P(p1,p2))}.(17) 3.1. An example In this subsection, given a rooted tree Tr(rdoes not need to be the central vertex), we provide an example showing how formulas (7)–(9) work in order to find the maximum of the minimum distances of a path among all the paths Pv∈P(Tv), ∀v∈V. In this example we are not considering either the eccentricity of the paths Pv∈P(Tv)or the partition of the tree Tinto the two subtrees T1and T2. Here (see Fig. 3), we suppose vertex 17 to be the root of the tree. The values along the edges represent their lengths. For each vertex v,Table 2 reports the values of flag(v),β(v), and MP(Tv). 4. The algorithms In order to solve problems P1–P6 we adopt a bicriteria approach similar to those presented in [1,15]. Recall that πi⊆Π, i=1,2, denotes the set of Pareto-optimal paths with respect to the partial order i,i=1,2. The algorithms that follow find two supersets φ(Wi),i=1,2, that contain the representations of all the Pareto-optimal paths in the outcome space (E(·), µ(·)) with respect to the two partial orders 1and 2, respectively. 4.1. The Pareto-optimal path representation algorithm for 1 Let us first consider the partial order 1(i.e., problems P1–P3), and let φ(W1)be such that φ(π1)⊂φ(W1)⊂φ(Π), that is, φ(W1)contains the representation of all the Pareto-optimal paths w.r.t. 1, along with some extra points. We will show that φ(W1)has cardinality O(n). The idea of the algorithm for computing the set φ(W1)is the following: first, the relevant functions are evaluated at all the vertices v∈Vi,i=1,2, and the pairs (EP(Tv),MP(Tv))are included in φ(W1). This guarantees that the Pareto-optimal paths belonging to P1and P2are identified. Then, paths belonging to Pare considered, and the pairs (EP(p1),b MP(p1)(p2)) are added to φ(W1). In the latter case, it is not necessary to evaluate all the possible subpaths P(p1,p2)⊆PC, implying an overall time complexity O(n2). Indeed, it can be shown that it is sufficient to evaluate only a sequence of O(n)subpaths P1, . . . , Pq of the path center PC such that, for any given Pareto-optimal path P∈P,Pis a best path of type 2 for which P∩PC ⊇Pifor some i=1,2, . . . , q. The following proposition provides a result similar to the one given in [1]. Please cite this article in press as: J. Puerto, et al., Extensive facility location problems on networks with equity measures, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.035 ARTICLE IN PRESS J. Puerto et al. / Discrete Applied Mathematics ( ) – 9 Fig. 4. An Example of a best path of type 2 in P(p1). Proposition 3. Let PC =P(c1,c2)6= {c}and P(p1,p2)be a subpath of PC such that c∈P(p1,p2),p16= c1,p16= c,p26= c. Suppose that diam 2−d(p1,c)≥diam 2−d(p2,c). Let (p1,t)be the edge belonging to PC \P(p1,p2)such that tis a child of p1in Tp1. Consider a path P∈Psuch that P∈π1and P(p1,p2)⊆P∩PC. Then, either t∈P, or P=Pp1p2∈P(p1)is a best path of type 2 that satisfies the following two conditions: (i) E(Pp1p2)=EP(p1)=diam 2−d(p1,c); (ii) µ(Pp1p2)=b MP(p1)(p2). Proof. If tis not in P, then, under the assumptions of the proposition, (i) holds, and the path Pcorresponds to a best path of type 2 in P(p1)that can be found only by maximizing µ(·)through formula (13) (see Fig. 4).  According to Proposition 3, the Pareto-optimal paths belonging to Pcan be identified by considering the sequence of subpaths P1, . . . , Pq. This sequence can be obtained starting from cand adding one edge at a time. Suppose PC 6= {c}and recall the decomposition of Tpresented in Section 2. Let v1and v2be the two vertices adjacent to cin PC. W.l.o.g., we may refer to v1as the vertex such that diam 2−d(v1,c)≥diam 2−d(v2,c). Thus, after Proposition 3, we have P1=(c,v1), while the rest of the sequence P2, . . . , Pqis generated according to the algorithm for the path center provided in [6] with Pq=PC. Actually, we do not consider the absolute center cas a subpath of PC since, when PC 6= {c}, vertex calone is evaluated as the root of T2. Note that the sequence P1, . . . , Pqis ordered in non-increasing order w.r.t. the eccentricity, that is, E(P1)≥E(P2)≥ · · · ≥ E(Pq). The following pseudocode describes the algorithm for finding the set φ(W1)with respect to the partial order 1when PC 6= {c}. Note that the same algorithm can be adopted when PC = {c}. In this case Step 4 is skipped, Step 5 must be executed for all v∈V, while Step 6 is dropped. The Pareto-optimal Path Representation Algorithm for 1 Input: An edge-weighted tree T. Output: The superset φ(W1). 1. φ(W1)= ∅ 2. Compute the absolute center cand the path center PC. Let v1and v2be the two vertices adjacent to cin PC such that diam 2−d(v1,c)≥diam 2−d(v2,c)and consider P1,P2, . . . , Pq, with P1=(c,v1)and Pq=PC. 3. Root Tat the absolute center c. 4. Identify the two subtrees T1and T2(see page 7). 5. For all v∈Vi,i=1,2do φ(W1)=φ(W1)∪ {(EP(Tv),MP(Tv))} endFor 6. For i=1to qdo Let Pi=P(p1,p2)be the current subpath of PC with diam 2−d(p1,c)≥diam 2−d(p2,c).φ(W1)=φ(W1)∪ {(EP(p1),b MP(p1)(p2))} endFor 7. output φ(W1). Proposition 4. The cardinality of the set φ(W1)is O(n). Please cite this article in press as: J. Puerto, et al., Extensive facility location problems on networks with equity measures, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.035 ARTICLE IN PRESS 16 J. Puerto et al. / Discrete Applied Mathematics ( ) – Fig. 7. The path center is P(x,y), where xand yare points in the interior of edges (1,4)and (2,4), respectively, and E(P(x,y)) =1. Moving yup to z produces the path Pε=P(x,z)that has the same eccentricity as P(x,y)and minimum distance equal to ε. However, taking for instance α=0.5, we have H(Pε)=0.5+0.5ε, but when ε=0, that is, zcoincides with vertex 2, we have H(P0)=1. Thus, limε→0H(Pε)6= H(P0), implying that the value 0.5 cannot be reached. 4.2.1. The continuous version of the Hurwicz-type problems The results for the continuous versions of problems P4–P6 rely on the following proposition. Proposition 11. Given a tree Tthat is not a path, for all ε > 0, one can always find a path Psuch that E(P)=E(PC)and µ(P)=ε. Proof. First of all, note that in the continuous case the path center PC will never have its endpoints in the leaves (unless the tree is a path), since, according to the definition of path center, the minimum length path that minimizes the maximum distance from the vertices of the tree will always end before reaching a leaf, at a distance equal to the eccentricity from that leaf. Thus, no endpoint of PC is a leaf (see, for example, the path P(x,y)in Fig. 7) and, for every ε > 0, a path Pεsuch that E(Pε)=E(PC)and µ(Pε)=εcan be obtained by enlarging PC along an edge, from one of its endpoints up to a distance equal to εfrom the next vertex (see the path P(x,z)in Fig. 7).  Proposition 11 shows that there exists no optimal solution for problems P4 and P6, since, in both cases, for any feasible path Pε, a better feasible solution Pεcan always be found with 0 <ε<ε, but the infimum of the objective function cannot be reached. This situation is shown in Fig. 7 for problem P4 with the value α=0.5. Moreover, Proposition 11 shows that problem P5 is feasible for every γ > 0, and an optimal solution can be always obtained by Pε, with ε≤γ. In this case problem P5 reduces to computing the path center. On the other hand, if γ=0 problem P5 is infeasible. 5. Concluding remarks In this paper we study the problem of locating a path on a network with different objective functions conceptually related to the variability of the distribution of the distances from the demand points to the path. We formulate six different problems (Problems P1–P6), where the first three problems are related to the range objective function and the other three to the Hurwicz objective function. We show that all the considered problems are NP-hard on general networks. We provide a dynamic programming approach to solve the discrete version of all the problems on trees in O(n)time. In addition, we define two partial orders induced by the maximum and the minimum distance criteria, and show that, for the discrete problems on a tree, a representation of the set of all the Pareto-optimal paths, with respect to these partial orders, can be obtained in O(nlog n)time. We also discuss the continuous versions of the range-type and Hurwicz-type problems on trees. For Problem P1, that is, finding a continuous path that minimizes the range function, we provide a O(n2)time algorithm for finding an optimal solution, while for problems P2 and P3 we provide linear time algorithms. For the continuous version of the Hurwicz-type problems we show that either an optimal path does not exist (Problems P4 and P6), or it can be found in constant time once the path center is available (Problem P5). We note that, since in the discrete case our algorithms are able to generate the whole Pareto-optimal path representation set, they can also be used to solve the following, more general, problem: find a discrete path Pwhich minimizes the linear combination of E(P)and µ(P):λE(P)+δµ(P), where λ≥0 and δ∈R. It is still an open problem how to extend the algorithms presented in this paper to the case in which nonnegative weights are assigned to the vertices of the tree. According to similar results in [15], we conjecture that subquadratic time algorithms exist for most of the weighted versions of these problems. Analyzing these cases will be the subject of a follow up paper. Acknowledgements The authors want to thank Prof. Arie Tamir for his contribution to better understanding problems P2 and P3 in the continuous case. The research of the first author is partially supported by Spanish research grant numbers: MTM2007- 67433-C02-01, P06-FQM-01366 and HI2006-0123. The research of the second author is supported by the Italian grant Please cite this article in press as: J. Puerto, et al., Extensive facility location problems on networks with equity measures, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.035 ARTICLE IN PRESS J. Puerto et al. / Discrete Applied Mathematics ( ) – 17 number “Azioni Integrate Italia-Spagna” 2.1.4.4.1.15 and Spanish research grant number MTM2007-67433-C02-01. The research of the third author is partially supported by the Italian research grants “Azioni Integrate Italia-Spagna” (number 2.1.4.4.1.15). References [1] I. Averbakh, O. Berman, Algorithms for path medi-centers of a tree, Computer and Operations Research 26 (1999) 1395–1409. [2] R.I. Becker, I. Lari, A. Scozzari, Algorithms for central-median paths with bounded length on trees, European Journal of Operational Research 179 (2007) 1208–1220. [3] B. Boffey, J.A. Mesa, A review of extensive facility location in networks, European Journal of Operational Research 95 (1996) 592–600. [4] T. Cáceres, M.C. López-de-los-Mozos, J.A. Mesa, The path-variance problem on tree networks, Discrete Applied Mathematics 145 (2004) 72–79. [5] S.L. Hakimi, E.F. Schmeichel, M. Labbé, On locating path- or treeshaped facilities on networks, Networks 23 (1993) 543–555. [6] S.M. Hedetniemi, E.J. Cockayne, S.T. Hedetniemi, Linear algorithms for finding the Jordan center and path center of a tree, Transportation Science 15 (1981) 98–114. [7] L. Hurwicz, Optimality criteria for decison making under ignorance. Cowles Comission Discussion Paper No. 370, 1951. [8] S. Kapoor, Dynamic maintenance of maxima of 2-d point sets, SIAM Journal of Computing 29 (2000) 1858–1877. [9] T.U. Kim, T.J. Lowe, A. Tamir, J.E. Ward, On the location of a tree-shaped facility, Networks 28 (1996) 167–175. [10] M.T. Marsh, D.A. Schilling, Equity measurement in facility location analysis: A review and framework, European Journal of Operational Research 74 (1994) 1–17. [11] J.A. Mesa, J. Puerto, A. Tamir, Improved algorithms for several network location problems with equality measures, Discrete Applied Mathematics 130 (2003) 437–448. [12] J. Milnor, Games against nature, in: R. Thrall, C. Coombs, R. Davis (Eds.), Decision Processes, John Wiley, 1954, pp. 49–59. [13] D. Pérez-Brito, J.A. Moreno-Pérez, The generalized p-centdian on networks, TOP 8 (2000) 265–286. [14] J. Puerto, F. Ricca, A. Scozzari, The continuous and discrete path-variance problems on trees. Networks (in press). [15] J. Puerto, A.M. Rodríguez-Chía, A. Tamir, D. Pérez-Brito, The bicriteria double weighted median-center path problem on a tree, Networks 47 (2006) 237–247. [16] J. Puerto, A. Tamir, Locating tree-shaped facilities using the ordered median objective, Mathematical Programming A 102 (2005) 313–338. [17] A. Shioura, M. Shigeno, The tree center problems and the relationship with the bottleneck knapsack problems, Networks 29 (1997) 107–110. [18] P.J. Slater, Locating central paths in a graph, Transportation Science 16 (1982) 1–18. [19] A. Tamir, Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem, Discrete Applied Mathematics 87 (1998) 229–243. [20] A. Tamir, J. Puerto, D. Pérez-Brito, The centdian subtree on tree networks, Discrete Applied Mathematics 118 (2002) 263–278. [21] A. Tamir, J. Puerto, J.A. Mesa, A.M. Rodríguez-Chía, Conditional location of path and tree shaped facilities on trees, Journal of Algorithms 56 (2005) 50–75. Please cite this article in press as: J. Puerto, et al., Extensive facility location problems on networks with equity measures, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.035