The path-variance problem on tree networks

The path-variance problem on tree networks Teresa C%aceresa, M. Cruz L%opezdelosMozos a, Juan A. Mesab aDepartamento de Matematica Aplicada I, E.T.S. de Ingeniera Informatica, Avda. Reina Mercedes, s/n, Sevilla 410 12, Spain bDepartamento de Matematica Aplicada II, Universidad de Sevilla, E.T.S. de Ingeniera Informatica, Avda. Reina Mercedes, s/n, Sevilla 410 12, Spain Abstract Extensive facility location models on graphs deal with the location of a special type of subgraphs such as paths, trees or cycles and can be considered as extensions of classical point location models. Variance is one of the measures applied in models in which some equality requirement is imposed. In this paper the problem of locating a minimum variance path in a tree network is addressed, and an O(n2 log n) time algorithm is proposed. Keywords: Location on networks; Equality; Extensive facilites 1. Introduction During the last two decades there has been increasing attention paid to the application of balancing or equality objectives in location analysis. Papers on equality location models can be roughly classi;ed into two groups: First, those dealing with general aspects such as how to measure equality, how to de;ne and what properties should have equality measures ([2,3,10]), and secondly, those oriented to design e@cient algorithms for solving the corresponding problems ([5,8,9]). On the other hand, when the facility to be located is too large to be modelled as a point, extensive facility location models arise. Several papers have investigated the problem of locating, on a network, a path, tree or other types of facilities which may not be considered as points (see [11,7] for a survey of this literature). Examples of problems in which structures instead of points are required include the location of pipelines, evacuation routes, mass transit routes or routing a highway through a road network. For the optimal selection of a site in which to locate an extensive facility the criteria used are, in almost all cases, the minimax criterion, the minisum criterion or a covering model, (see [6,12–16]). In addition, although most of these problems can be solved in polynomial time in tree networks, they are NP-hard in cyclic networks (see [4] for an analysis of the complexity of these problems). For this reason the main eDort has been orientated to design e@cient algorithms to solve the aforementioned problems in tree networks. In particular the path-center and the path-median (or core) of a tree (which arise from the application of the minimax criterion and the minisum criterion, respectively) can be found by means of linear time algorithms (see [15,13]). The above discussion shows that the equity (as suitable objective) has not been considered in the criteria used hitherto in the location of extensive facilities. However, in certain public sector problems, an equity criterion is needed to generate acceptable decisions. The variance of distance travelled by all customers to the facility has been an equity criteria widely studied in point location problems. The purpose of this work is to apply this criterion for locating a path-shaped facility in a tree network. This problem, which will be called the Path-Variance Problem, will be studied in the continuous version in which partial edges are allowed, that is, when the extreme points of the path can be interior points of an edge. In general these extreme points will belong to diDerent edges. However, the case in which both points are in the same edge will be analyzed separately, since this gives rise to the particular case in which the path degenerates to a single point. The remainder of the paper is organized as follows. In the next section the formulation of the problem is introduced and properties of the objective function when the extreme points belong to diDerent edges are studied. Section 3is devoted to the case in which the extreme points of the path belong to the same edge. In order to design the algorithm for the problem, a data structure to describe the tree is incorporated at the beginning of Section 4. In that section the algorithm is also proposed, and its complexity is discussed. 2. The path-variance problem on dierent edges Let T=(V; E) be an undirected tree network with vertex set V={v1;:::;v n}, edge set E, and edge lengths {lj:ej∈E}. Denote by Tthe set of points in Twhich comprises both set Vand the set of all the points on edges. We will consider paths not only containing complete edges but also partial edges, and they will be denoted as P(x1;x 2) in which x1;x 2∈T are the end points of the path. If P(x1;x 2)⊂Tis a path, then d(x; P) = miny∈Pd(x; y), where d(x; y):x; y ∈T,isthe distance between points given by the length of the only path joining xand y, which makes Ta metric space. We suppose that demand originates at the vertices of the tree, and we associate a positive weight wiwith each vertex vi∈V. Without loss of generality we may assume that n i=1 wi= 1 and interpret each wias the fraction of demand originated at vi. For a subset of vertices V⊂Vlet W(V)=vi∈Vwibe the weight of V, and let W(V)=vi∈V\V wi=1−W(V) be the weight of the complement of Vin V. For any point x∈T, the median function (distancesum) of xover V⊂Vis given by zm(x; V )=vi∈Vwid(vi;x). Similarly the median function of a path P(x1;x 2)inV⊆Vis given by zm(P(x1;x 2);V)=vi∈Vwid(vi;P(x1;x 2)). For simplicity, when V=Vwe will use zm(x) and zm(P(x1;x 2)) instead of zm(x; V ) and zm(P(x1;x 2);V), respectively. The variance function for a path P(x1;x 2) is de;ned as zs(P(x1;x 2)) = n  i=1 wi[d(vi;P(x1;x 2)) −zm(P(x1;x 2)]2: The Continuous Path-Variance Problem (CPVP) consists of ;nding points x1;x 2such that the path joining these points minimises the function zson all the paths P⊂T. Given a pair of edges ej;e kthe Continuous Path-Variance Problem Restricted to (ej;e k), (CPVP)jk , is that of minimising the restricted function zs(P(x1;x 2)), where x1∈ej,x2∈ek, whose domain is [0;l j]×[0;l k]. Consequently a solution of the problem (CPVP)jk is a pair (x∗ 1;x ∗ 2)∈[0;l j]×[0;l k] such that zs(P(x∗ 1;x ∗ 2)) 6zs(P(x1;x 2));∀(x1;x 2)∈[0;l j]×[0;l k]: As usual when an edge ejis ;xed, any real number x∈[0;l j] will denote the point on the edge whose exact location is determined by its distance (along the edge) from a prescribed endpoint of the edge. In order to avoid a decomposition into two cases, and therefore the subsequent case analysis, the reference vertices to measure distances between any two points x1∈ej=(uj;v j) and x2∈ek=(uk;v k) will be the farthest vertices among those of both edges. We will suppose that ujand vkare these farthest vertices, consequently x1∈ejmeans the length of subedge (uj;x 1) and x2∈ekmeans the length of subedge (vk;x 2). For a vertex uof edges ej;e k, let Vudenote the vertex set of the subtree Turooted at uwhich does not contain the edge ejnor ekwhich is incident to u.W(Vu)=vi∈V uwiis the total weight of Vuand W(Vu)=1−W(Vu) is the weight of the complementary vertex set. In accordance with this notation, Tujand Tvkwill represent the subtrees rooted at the farthest vertices ujand vkrespectively, and do not contain the edges ejand ek(and therefore neither do they contain the path P(x1;x 2)). Likewise we denote by V(P(x1;x 2)) the vertex set of the path P(x1;x 2) and by T1;T 2;:::;T rthe connected components (subtrees) that result from the deletion of V(P(x1;x 2)) and the corresponding incident edges from the tree T\(Tuj∪Tvk). Then the median function for the path P(x1;x 2)is zm(P(x1;x 2)) =  vi∈V wid(vi;P(x1;x 2)) =  vi∈V uj wi[d(vi;u j)+x1] + r  h=1   vi∈V h wid(vi;P(x1;x 2)) + vi∈V vk wi[d(vi;v k)+x2] =zm(P(uj;v k)) + W(Vuj)x1+W(Vvk)x2: In the following we will denote by zm(P) the value zm(P(uj;v k)). The variance of the path P(x1;x 2) can be decomposed in the following manner: zs(P(x1;x 2)) =  vi∈V uj wi[(d(vi;u j)−zm(P))2+(W(Vuj))2x2 1 +(W(Vvk))2x2 2+2(d(vi;u j)−zm(P))W(Vuj)x1 −2(d(vi;u j)−zm(P))W(Vvk)x2−2W(Vuj)W(Vvk)x1x2] + r  h=1   vi∈V h wi[(d(vi;P)−zm(P))2+(W(Vuj))2x2 1+(W(Vvk))2x2 2 −2(d(vi;P)−zm(P))W(Vuj)x1−2(d(vi;P)−zm(P))W(Vvk)x2 +2W(Vuj)W(Vvk)x1x2] + vi∈V vk wi[(d(vi;v k)−zm(P))2+(W(Vuj))2x2 1+(W(Vvk))2x2 2 +2(d(vi;v k)−zm(P))W(Vvk)x2−2(d(vi;v k)−zm(P))W(Vuj)x1 −2W(Vvk)W(Vuj)x1x2]: By associating terms with equal degree, zs(P(x1;x 2)) = W(Vuj)W(Vuj)x2 1+W(Vvk)W(Vvk)x2 2 −2W(Vuj)W(Vvk)x1x2 +2(zm(uj;V uj)−W(Vuj)zm(P))x1 +2(zm(vk;V vk)−W(Vvk)zm(P))x2+zs(P):(1) By imposing the necessary conditions for stationary points the following system results: W(Vuj)W(Vuj)x1−W(Vuj)W(Vvk)x2+(zm(uj;V uj)−W(Vuj)zm(P))=0; W(Vuk)W(Vuk)x2−W(Vuj)W(Vvk)x1+(zm(vk;V vk)−W(Vvk)zm(P))=0: Let W(P)=vi∈V(P(x1;x2)) wibe the weight of the vertex set of the path P(x1;x 2). Clearly W(P)¿0 since the set V(P(x1;x 2)) is not empty when the extreme points x1;x 2of the path belong to diDerent edges. By simplifying the unique solution of the last system, we obtain x1=1 W(P)zm(P)−zm(vk;V vk)−zm(uj;V uj)W(Vvk) W(Vuj) x2=1 W(P)zm(P)−zm(uj;V uj)−zm(vk;V vk)W(Vuj) W(Vvk):(2) Furthermore, 0 6x16ljand 0 6x26lkmust hold. The Hessian matrix is H=2W(Vuj)W(Vuj)−W(Vuj)W(Vvk) −W(Vuj)W(Vvk)2W(Vvk)W(Vvk): Since W(Vuj)=W(P)+W(Vuk) and W(Vuk)=W(P)+W(Vuj), then |H|=W(Vuj)W(Vvk)(4W(Vuj)W(Vvk)−W(Vuj)W(Vvk)) ¿0 and also 2W(Vuj)W(Vuj)¿0. Therefore, the Hessian matrix is de;nite positive, which guarantees that the variance function is strictly convex on the compact set [0;l j]×[0;l k] and the stationary point given by (2) is the minimum, which implies that it is the solution (x∗ 1;x ∗ 2) of the restricted problem (CPVP)jk . When the minimum (x1;x 2) does not belong to the above compact set then the optimum is reached in the boundary. There are several cases. (1) If x160 and 0 6x26lkthen the minimum (x∗ 1;x ∗ 2) of the restricted problem is reached at the point 0;W(Vvk)zm(P)−zm(vk;V vk) W(Vvk)W(Vvk): (2) If x1¿ljand 0 6x26lkthen the optimum is lj;W(Vvk)(zm(P)+W(Vuj)lj)−zm(vk;V vk) W(Vvk)W(Vvk): (3) If x260 and 0 6x16ljthen the minimum is given by W(Vuj)zm(P)−zm(uj;V uj) W(Vuj)W(Vuj);0: (4) If x2¿lkand 0 6x16ljthen W(Vuj)(W(Vvk)lk+zm(P)) −zm(uj;V uj) W(Vuj)W(Vuj);l k: (5) Finally, (x∗ 1;x ∗ 2)=             (lj;0) if x1¿ljand x260; (0;0) if x160 and x260; (lj;l k)ifx1¿ljand x2¿lk; (0;l k)ifx160 and x2¿lk: 3. The path-variance problem on an edge In this section the path location problem, in which the two ends of the path are in the same edge, is considered. We are looking for the path that minimises the variance function zs(P(x1;x 2)) among those paths P(x1;x 2) such that x1;x 2∈ej=(uj;v j). Following the notation introduced in the previous section, ujand vjare now the farthest vertices. Consequently x1,x2represent the lengths of the subedges (uj;x 1) and (vj;x 2), respectively, and if Vuj,Vvjare the vertex sets of the subtrees Tuj,Tvjrooted at uj,vj, respectively, which do not contain the edge ej, then they are complementary vertex sets, i.e. Vuj∪Vvj=V. This implies that W(P) = 0, which justi;es a separate study of this case. The expression for the median function is the same as in the previous case, zm(P(x1;x 2))=zm(P(uj;v j))+W(Vuj)x1+ W(Vvj)x2. By using the simpli;ed notation zm(P) and zs(P) instead of zm(P(uj;v j)) and zs(P(uj;v j)), respectively, and taking into account that Vuj=Vvj, the variance function can be written as follows: zs(P(x1;x 2)) = W(Vuj)W(Vvj)x2 1+W(Vuj)W(Vvj)x2 2 −2W(Vuj)W(Vvj)x1x2+2{zm(uj;V uj)−W(Vuj)zm(P)}x1 +2{zm(vj;V vj)−W(Vvj)zm(P)}x2+zs(P)=W(Vuj)W(Vvj)[x1−x2]2 +2{zm(uj;V uj)W(Vvj)−zm(vj;V vj)W(Vuj)}[x1−x2]+zs(P): Fig. 1. It can be seen that when x1=x2(i.e. the path degenerates to the medium point of the edge), then the value zs(P(x1;x 2)) coincides with the variance zs(P) of the complete edge. Moreover, the edge variance also coincides with the variance of any path centered at the medium point and contained in the edge. The necessary conditions for stationary points give rise to the following system: W(Vuj)W(Vvj)(x1−x2)+(zm(uj;V uj)−W(Vuj)zm(P))=0; W(Vuj)W(Vvj)(x2−x1)+(zm(vj;V vj)−W(Vvj)zm(P))=0; in which zm(uj;V uj)−W(Vuj)zm(P)=W(Vvj)zm(P)−zm(vj;V vj), since zm(P)=zm(uj;V uj)+zm(vj;V vj) and W(Vuj)+W(Vvj)=1. This implies that the system is undetermined compatible, and it provides the only condition given by x1−x2=zm(P) W(Vvj)−zm(uj;V uj) W(Vuj)W(Vvj) or equivalently x1−x2=zm(vj;V vj) W(Vvj)−zm(uj;V uj) W(Vuj)=K; (3) with 0 6x16lj,06x26lj, and 0 6x1+x26lj. Since the Hessian matrix is also de;nite positive the stationary points are minima. In accordance with these expressions, the following cases can be considered (see Fig. 1). Case 1: If −lj¡K¡l jthen any path for which x1−x2=K; 0¡x 1+x2¡l j;0¡x 16x2¡l j is a path of minimum variance whose variance value is: zs(P(x1;x 2)) = zs(P)+K2W(Vuj)W(Vvj) +2K{W(Vvj)zm(uj;V uj)−W(Vuj)zm(vj;V vj)} =zs(P)−[zm(vj;V vj)W(Vuj)−zm(uj;V uj)W(Vvj)]2 W(Vuj)W(Vvj) =zs(P)−K2W(Vuj)W(Vvj): Let us note that the point (x1;x 2)∈[0;l j]×[0;l j] such that x1+x2=lj;x 1−x2=K is the point of minimum variance of this edge. Case 2: If K¿ljthen the path degenerates to the point vj, which corresponds to the pair (lj;0), and also is the point of minimum variance of the edge. Case 3: If K6−ljthen the path reduces to the point of minimum variance of the edge, uj. Fig. 2. 4. Algorithm and complexity For each pair of edges ej,ek, the determination of the local optimum x1;x 2either by (2) and subsequent expressions (if j=k)orby(3) and subsequent expressions (if j=k), requires the previous computation of a set of auxiliary values associated to each vertex uas well as the evaluation of the function zmon the path joining the farthest vertices of the edges ejand ek. In order to obtain all these values the recursive procedure designed by Maimon [9] will be applied. Let vrbe the root with sons v1;:::;v s,(s¿0), (i.e. there exists an edge (vi;v r)∈Efor each i=1;:::;s). A postorder traversal of Tis de;ned recursively as follows: (1) Visit in postorder the subtrees with roots v1;:::;v sin that order. (2) Visit the root vr. The postorder de;ned in Tinduces the following order of edges of E: (u1;v t(1));(u2;v t(2));:::;(un−1;v r); where each vt(i)is the father of uiin the postorder, and for each two edges ej=(uj;v t(j)) and ek=(uk;v t(k)), k¿j means that vt(k)can be (not necessarily) a common ancestor of the remaining three vertices. This fact provides an identi;cation of the farthest vertices of pair ej=(uj;v t(j));e k=(uk;v t(k)) (with k¿j) as follows (see Fig. 2). Case (i): If vt(j)is a descendant of uk(that is, vt(j)∈Vukin the de;ned postorder), then uj;v t(k)are the farthest vertices. In this case, the vertices belonging to P=P(uj;v t(k)) can be found by successively adding the vertex father of each vertex son (starting with the ;rst son uj, and ending with the last father vt(k)). Case (ii): Otherwise, the farthest vertices are uj;u k. In this case, uj;u khave a common ancestor v∗, which can be either one of the fathers vt(j);v t(k)(or both, if they coincide), or a vertex not in ej;e k. In this last case, the path Pjoining uj;u kcan be found by a binary search among the fathers of the vertices uj;u kas follows: starting with ujand uk, the successive fathers are tested (and added to path P=P(uj;u k)) until a common father v∗is found). If vkdenotes the farthest vertex from uj(where as we have already seen, vkcan be either vt(k)or uk), the point x2in the edge ekis identi;ed by its distance from vk. Note that in case (i) the identi;cation of the second point when using the postorder can be obtained from that used in Section 2, by applying the simple change x 2=lk−x2. However, the point x1in the edge ejis always identi;ed by its distance from the lower vertex ujof the edge. If Tu=(Vu;E u) denotes (in the postorder) the subtree rooted in each u∈V, the necessary vertex information for computing the local optimum (x∗ 1;x ∗ 2) can be determined in a preprocessing phase, in which the tree is twice traversed following the postorder (toward the root of the tree and conversely). By applying the recursive relationships of Maimon [9], at the end of this phase the aforementioned vertex information is available. This information (accumulated in a vector of auxiliary values associated to each vertex) is: W(Vu);z m(u; Vu);z m(u);z(2) m(u; Vu);z(2) m(u); where z(2) m(u; Vu)=vi∈V uwid(vi;u)2, and z(2) m(u)=z(2) m(u; V ). It is easy to see that for a path P zs(P)= vi∈V wid(vi;P)2− vi∈V wid(vi;P)2 =z(2) m(P)−(zm(P))2: Therefore the aforementioned auxiliary values will be necessary for computing zs(P). If Vu=V\Vu, and Suis the set of sons of uand vits father, the set C(u)=Su∪{v}contains all the nearest vertices (from u) in the connected components obtained by deleting uand the incident edges. The preprocessing phase also provides the values associated to the connected components whose nearest vertices belong to Su: {W(Vui);z m(ui;V ui);z(2) m(ui;V ui)∀ui∈Su} as well as the values associated to the connected component father: W(Vu)=1−W(Vu); zm(v; V u)=zm(u)−zm(u; Vu)−luv(1 −W(Vu)); z(2) m(v; V u)=z(2) m(u)−z(2) m(u; Vu)−l2 uvW(Vu)−2luvzm(v; V u): The knowledge of these auxiliary values allows us to obtain zm(P) and z(2) m(P) by means of a progressive procedure. Let P=P(uj;v k) be the path joining the farthest vertices in the pair of edges {ej;e k};k¿j, let V(P) be the vertex set of the path Pand let C(uj)={uj1;:::;u js};C(vk)={vk1;:::;v kt}be the respective nearest vertices in the connected components associated to uj;v k. Initially zm(P)=zm(uj)− uji∈C(uj)∩V(P) zm(uj;T uji)+zm(vk)− vki∈C(vk)∩V(P) zm(vi;T vkj): When a vertex vis added to Paccording to the aforementioned described cases (i) or (ii), the values of zm(P) and z(2) m(P) are successively updated by adding the corresponding auxiliary values of vin the connected components whose nearest vertices are not in P: zm(P)←zm(P)+zm(v)− v i∈C(v)∩V(P) zm(v;T v i): Note that the cardinality of the set C(v)∩V(P) is bounded by 2 (since there exists at most two vertices in Pwhich are adjacents to v). Likewise, z(2) m(P) is obtained by the same procedure by considering z(2) minstead of zm. Finally, before describing the pseudocode of the algorithm, it is necessary to make some observations with respect to the value W(Vvk) which appears in the expression (2). For a given pair of edges ej=(uj;v t(j));e k=(uk;v t(k)) whose farthest vertices are uj;v k, for the case (ii) W(Vvk) coincides with the auxiliary value provided by the postorder, that is : W(Vvk)=1−W(Vvk). However, in the case (i) such a value represents the weight of the connected component associated to vkwhose nearest vertex is uk, that is, uk∈C(vk)∩V(P). Therefore, in the case (i), W(Vvk)=W(V(Tuk)), and W(Vvk)=1−W(Vvk). Thus, the pseudocode of the algorithm is as follows: Input: A tree network given by a postorder traversal. Preprocessing phase For (u∈V)do Compute the auxiliary values. endfor Let Zbe a suitable large number. Main step For (j=1 to n−1) do For (k=jto n−1) do If (k¿j)then By a binary search determine the vertex set of P=P(uj;v k) and simultaneously compute zm(P) and z(2) m(P). Compute zs(P)=z(2) m(P)−(zm(P))2. Compute the point (x∗ 1;x ∗ 2) (by applying (2) and subsequent relationships). Otherwise (k=j)then Compute (x∗ 1;x ∗ 2) (by applying (3) and subsequent relationships). endif Compute zs=zs(P(x∗ 1;x ∗ 2)). If (zs¡Z)then P∗←P(x∗ 1;x ∗ 2), Z←zs. endif endfor endfor Output: The path P∗=P(x∗ 1;x ∗ 2) that minimises the variance and Z=zs(P∗). For each considered path, obtaining the optimum requires identifying and adding a set of auxiliary values associated to the corresponding nodes of the path. By using the postorder structure, such nodes (and their auxiliary values) are added by means of a binary search process over the set of fathers. Since the complexity of the binary search is O(log n) (see [1]) and n2paths are tested, the overall complexity of the algorithm is O(n2log n) time. Acknowledgements The authors are partially supported by Project: MCyT BFM2000-1052-C02-01. References [1] A. Aho, J. Hopcroft, J. Ullman, Data Structures and Algorithms, Addison-Wesley, Reading, MA, 1983. [2] H.A. Eiselt, G. Laporte, Objectives in location problems, in: Zvi Drezner (Ed.), Facility Location: A Survey of Applications and Methods, Springer Series in Operations Research, Springer, New York, 1995, pp. 151–180. [3] E. Erkut, Inequality measures for location problems, Location Sci. 1 (1993) 199–217. [4] S.L. Hakimi, E.F. Schmeichel, M. Labb%e, On locating path or tree-shaped facilities on networks, Networks 23 (1993) 543–555. [5] P. Hansen, M. Zheng, An algorithm for the minimum variance point of a network, RAIRO Operations Research/Recherche Op%erationnelle 25 (1991) 119–126. [6] R.K. Kincaid, T.J. Lowe, T.L. Morin, The location of central structures in trees, Comput. Oper. Res. 15 (1988) 103–113. [7] M. Labb%e, G. Laporte, I. Rodr% Qguez-Mart% Qn, Path, tree and cycle location, in: T.G. Crainic, G. Laporte (Eds.), Fleet Management and Logistics, Kluwer, Boston, 1998, pp. 187–204. [8] M.C. L%opez de los Mozos, J.A. Mesa, The variance location problem on a network with continuously distributed demand, RAIRO Operations Research/Recherche Op%erationnelle 34 (2000) 155–181. [9] O. Maimon, The variance equity measure in locational decision theory, Ann. Oper. Res. 6 (1986) 147–160. [10] M.T. Marsh, D.A. Schilling, Equity measurement in facility location analysis: A review and framework, European J. Oper. Res. 74 (1994) 1–17. [11] J.A. Mesa, T.B. BoDey, A review of extensive facility location in networks, European J. Oper. Res. 95 (1996) 592–603. [12] E. Minieka, The optimal location of a path or tree in a tree network, Networks 15 (1985) 309–321. [13] C.A. Morgan, P.J. Slater, A linear algorithm for a core of a tree, J. Algorithms 1 (1980) 247–248. [14] S. Peng, A.B. Stephens, Y. Yesha, Algorithms for a core and k-tree core of a tree, J. Algorithms 15 (1993) 143–159. [15] P.J. Slater, Locating central paths in a graph, Transportation Sci. 16 (1982) 1–18. [16] P.J. Slater, Some de;nitions of central structures, Lecture Notes in Mathematics, Vol. 1073, Springer, Berlin, 1984, pp. 169–178.