Locating Two Transfer Points on a Network with a Trip Covering Criterion and Mixed Distances

Locating Two Transfer Points on a Network with a Trip Covering Criterion and Mixed Distances M.C. L´opez-de-los-Mozos ∗Juan A. Mesa †Anita Sch¨obel ‡ Abstract In this paper we consider a set of origin-destination pairs in a mixed model in which a network embedded in the plane represents an alternative high-speed transportation system, and study a trip covering problem which consists on locating two points in the network which maximize the number of covered pairs, that is, the number of pairs which use the network by acceding and exiting through such points. To deal with the absence of convexity of this mixed distance function we propose a decomposition method based on formulating a collection of subproblems and solving each of them via discretization of the solution set. Keywords: Location; Network; Covering Problem; Mixed Distances 1 Introduction In a previous paper [5], a location problem on a mixed planar-network space was tackled. In the problem dealt with in that paper, there are existing facilities in the Euclidean plane whereas new facilities are to be located in a straight-line segment or in a tree network. Instead of covering facilities the objective aims at covering trips between each pair of existing facilities. These trips can be done either by using the plane with the Euclidean distance or by a combination planenetwork in which the section on the network is supposed to be traversed faster than those on the plane. Therefore, there is a competition between the mode that only uses the planar distance and the combined one. Each pair of existing facilities has an associated demand and the objective is to maximize the number of trips for which the combined mode is preferable to the planar one. In this paper we extend the approach applied in [5] to the case of general networks by taking into account the loss of convexity of the distance function between pairs of points through the network. The problem of locating stations in a railway network was indirectly tackled in [13], in which they considered the problem of optimal interstation spacing in a commuter line. The objective of this problem was to minimize the total time of passengers going to a city center along a railway line. A commuter line competing with a freeway was considered in [14] in order to maximize the number of passengers on the basis if the shortest travel time. The aim was also to determine the optimal interstation space between pairs of adjacent stations. Apart from the papers [6, 7] in which the feasible solution space for locating stations was discrete, and the objective was to maximize the passengers and trip coverage, respectively, several objective functions have been considered in those in which stations can be located along the edges of the railway network ([2, 10, 11, 8]). In order to avoid duplications the reader is referred to the Introduction of the paper [5] for an overview of other related papers. ∗Dpto. Matem´atica Aplicada I. Universidad de Sevilla, Spain. [email protected] †Dpto. Matem´atica Aplicada II. Universidad de Sevilla, Spain. j[email protected] ‡Institut f¨ur Numerische and Angewandte Mathematik. Universit¨at G¨ottingen, Germany. schoeb[email protected]goettingen.de 1 The case of locating only one facility regarding transfer facilities already located in the network is a particular case of that dealt with in this paper and can be categorized as a conditional location problem. Thus, adding the extra demand captured by both pairs consisting of a new facility and an already located one, and those consisting of two new facilities, the global contribution of the two new transfer points is computed. The paper is organized as follows. After this introduction the problem is formulated in Section 2. The necessary definitions and results on the distance on networks are summarized in Section 3. Section 4 is devoted to solve the two cases arisen from the properties of the distance. The paper ends with some conclusions and further research. 2 The problem Hereinafter we will use the notation introduced by [5]. Let A={Ai= (ai, bi), i = 1,...,n} ⊂ IR2be a set of existing facilities on the plane. We assume that travel time distances between two points in the plane can be estimated by the Euclidean metric. Let T= (tij )∈IRn×nbe an origin-destination (O/D) matrix in which trip patterns are codified, i.e., tij is the weight of the ordered pair (Ai, Aj) (or (i, j), if there is no confusion). This matrix is known a priori: for example, in a transportation context each tij can be viewed as the number of trips from an origin Aito a destination Aj, and in a telecommunication setting it could represent the amount of data transfered from server ito server j. In order to formulate the problem with a mixed mode of transportation, we consider an embedded network N(V, E) representing a high-speed system, with |V|vertices and |E|edges. Each vertex v∈Vrepresents a junction or a node, and we assume that each undirected edge e∈Ehas a length leand it can be modeled as a straight-line segment. The embedding of N in the Euclidean plane as well as the coordinates of the nodes in Nwill allow us to compute the travel distances between each pair of points. Let Nbe the continuum set of points on the edges. The edge lengths induce a distance function don N, such that for any two points x, y ∈ N,d(x, y) is the length of any shortest path connecting xand y. Moreover, if xand y are on the same edge, d(x, y) = ||x−y||. For any two points x, y ∈ N, let us define the high-speed distance dN(x, y) = αd(x, y), with α∈(0,1). Parameter αis a speed factor. It is straightforward to see that (N, dN) is a metric space. Given an O/D pair (i, j), the transportation time by using the network is obtained by selecting two points X1∈ N and X2∈ N (or a 2-facility point (X1, X2)∈ N2) such that the transportation path from ito jenters the network at one of such points and exits the network at the other one. If X1is the access point from Aiand X2the exit point towards Aj, the length of the travel-path (Ai, X1, X2, Aj) is given by: hij (X1, X2) = ||Ai−X1||2+dN(X1, X2) + ||X2−Aj||2 Moreover, if X2is the access point from Aiand X1the exit point towards Aj, the length of the travel-path (Ai, X2, X1, Aj) is hij (X2, X1) = ||Ai−X2||2+dN(X2, X1) + ||X1−Aj||2 Although algebraically hij(X1, X2) = hji(X2, X1) and hij (X2, X1) = hji(X1, X2), in this context the subindex ij indicates the origin/destination pair (i, j), which is different from the O/D pair (j, i). For this reason, with each O/D pair (i, j) we only associate the subindex ij. The distance between the O/D pair (Ai, Aj) by using the transit points X1, X2∈ N is: fij (X1, X2) = min{hij(X1, X2), hij (X2, X1)}=fij(X2, X1) Let D= (dij )∈IRn×nbe a symmetric matrix, with 0 ≤dij <||Ai−Aj||2. The values of D represent the acceptance levels for using the network, meaning that the O/D pair (i, j) chooses 2 the high-speed network if and only if the traveling time by using it is less than or equal to dij . In other words, the O/D pairs always choose the faster option. Definition 1 The O/D pair (i, j) is covered by (X1, X2)∈ N2if and only if fij(X1, X2)≤dij. Let C(X1, X2) be the set of O/D pairs covered by (X1, X2), that is: C(X1, X2) = {(Ai, Aj)∈ A×A :fij(X1, X2)≤dij } Symmetry of the acceptance level matrix and both the Euclidean and the network distances implies that (i, j)∈C(X1, X2) if and only if (j, i)∈C(X1, X2). The objective function measures the amount of trip patterns captured by each 2-facility- point (X1, X2)∈ N2, and it is given by the trip-sum function: F(X1, X2) = X (i,j)∈C(X1,X2) tij Finally, the O/D-pair 2-location problem is to find a point (X1, X2)∈ N2such that the sum of trip patterns of all O/D pairs covered by such a point is maximized: max F(X1, X2) := X (i,j)∈C(X1,X2) tij s.t. (X1, X2)∈ N2 (1) The problem (1) has been first solved for the particular case where Nis a segment of a straight line, and later the method was extended to the case where Nis a tree network T(see [5]). However, the approach applied for the tree network case cannot be directly extended to a general network Ndue to the absence of convexity of distance functions on a cyclic network. Ir order to solve the problem, we next summarize some concepts on the behavior of distance on networks. 3 Previous results on distances on networks Let e= [u, w]∈Ebe an edge of the network Nof length le=l(u, w), and let Pbe a point on e. Let x=l(u, P) be the length of the subedge from the left vertex uto P, and l(w, P) = le−xbe the length of subedge [P, w]. It is well known that for any node vi∈V, the distance d(vi, P) = di(x) = min{d(vi, u) + x, d(vi, w) + le−x}is concave and piecewise linear on x∈[0, le], with at most two pieces with slopes 1 and −1. If l(u, w)≤ |d(vi, u)−d(vi, w)|, then the distance function d(vi, P) on [u, w] is linear. The following concepts and definitions can be found in [3] and references therein. Definition 2 Given a point Q∈ N and an edge [u, w], the point P∈[u, w] at which d(Q, P) is maximized is called antipodal to Qin [u, w]. Note that if Pis antipodal to Qdoes not imply that Qis antipodal to P; if it is Pand Q are antipodal to each other. Definition 3 A point ¯vi∈[u, w], other than a node, is called an arc bottleneck point if there is a vertex vifor which ¯viis antipodal to vi. In this case, d(vi, u) + l(u, ¯vi) = d(vi, w) + l(w, ¯vi). Clearly, [u, w] contains at most |V|arc bottleneck points (since each vertex videfines at most one arc bottleneck point ¯vion the edge). Such a point ¯vican be identified by the length of the subarc [u, ¯vi] given by: l(u, ¯vi) = d(vi, w)−d(vi, u) + l(u, w) 2. 3 Definition 4 Let Bebe the set of arc bottleneck points of edge e= [u, w], and let ¯vi, ¯vjbe two adjacent points of Be∪{u, w}. Then Li= [¯vi,¯vj], the closed subedge limited by such points, is called a linear arc segment (or a treelike segment [3]). On each linear arc segment the distance d(vi, P) is linear. If Be=∅the entire edge [u, w] (including nodes) is a linear arc segment. The set of all linear arc segments of an edge eis denoted by L(e). Let [up, wp] and [uq, wq] be two edges of the network N, and let [ ¯wp,¯up]⊆[uq, wq], [ ¯wq,¯uq]⊆ [up, wp] be the subedges for which the extreme points are antipodal points as follows: ¯up,¯wp are the antipodal points to up, wprespectively, and ¯uq,¯wqare the antipodal points to uq, wq, respectively (see Figure 1(a)). From previous definitions we have l( ¯wq,¯uq) = l( ¯wp,¯up) and d( ¯wq,¯wp) = d(¯uq,¯up) (see [3] for a more detailed explanation). uq upwp wq uq wq up wp u ww u d(u, w)< l(u, w) (a) (b) Figure 1. Antipodal points on: (a) different edges, (b) the same edge Definition 5 Let Lp,Lqbe two linear arc segments of different edges [up, wp] and [uq, wq], respectively, and let [ ¯wq,¯uq]⊆[up, wp] and [ ¯wp,¯up]⊆[uq, wq] be the subedges for which ¯up,¯wp are the antipodal points to up, wprespectively, and ¯uq,¯wqare the antipodal points to uq, wq, respectively. If Lp⊆[ ¯wq,¯uq] and Lq⊆[ ¯wp,¯up], then Lp,Lqare called antipodal segments to each other. (This definition includes the case [ ¯wq,¯uq] = [up, wp] and [ ¯wp,¯up] = [uq, wq]). The following result summarizes the behavior of distance d(P, Q) on linear arc segments of different edges (see Hooker, Garfinkel and Chen [3]). Lemma 6 Let Pbe restricted to linear arc segment Lpof edge [up, wp]and Qto linear arc segment Lqof edge [uq, wq], with [up, wp]6= [uq, wq]. 1. If Lp, Lqare antipodal segments to each other, d(P, Q)is concave. 2. Otherwise, d(P, Q)is linear. In case 1, the distance between a point Pon the segment [ ¯wq,¯uq] and a point Qon the segment [ ¯wp,¯up] behaves like the distance on the parallelogram in Figure 1(a), and it is concave. Distance on any other pair of segments behaves like distance on a line segment and is therefore linear. By denoting x=l(up, P), with x∈[0, l(up, wp)] and y=l(uq, Q), with y∈[0, l(uq, wq)], we can compute the distance d(P, Q) for the cases considered in this lemma. d(P, Q) =          min{x+d(up, uq) + y, l(up, wp)−x+d(wp, wq) + l(uq, wq)−y}, Lp, Lqantipodal x+d(up, uq) + y, Lp⊆[up,¯wq], Lq⊆[uq,¯wp] or Lq⊆[ ¯wp,¯up] x+d(up, wq) + l(uq, wq)−y, Lp⊆[up,¯wq], Lq⊆[¯up, wq] 4 Note that in the case Lp, Lqantipodal segments, with up6= ¯wq, ¯uq6=wpand similarly uq6= ¯wp, ¯up6=wq, the distance d(P, Q) can also be computed by min{x+d(up, wq) + l(uq, wq)− y, l(up, wp)−x+d(wp, uq)+y}. Finally, the remaining cases obtained by combining Lp, Lqcan be reduced to one of these by symmetry (for example, for the case Lp⊆[up,¯wq], Lq⊆[¯up, wq] the distance can also be equivalently obtained as l(up, wp)−x+d(wp, uq) + y). We now study the case in which P, Q lie on the same edge [u, w], with d(u, w)≤l(u, w). Let ¯u, ¯wbe the antipodal points to u, w respectively. The sequence {u, ¯w, ¯u, w}induces a partition of [u, w] in (at most) three consecutive subedges: [u, ¯w], [ ¯w, ¯u] and [¯u, w] (Figure 1(b)). Lemma 7 Let Lp,Lqbe two linear arc segments of [u, w]such that Pis restricted to Lpand Qis restricted to Lq. 1. If Lp=Lqthe distance d(P, Q)is convex. 2. If Lp6=Lq, and Lp,Lqlie respectively in non-adjacent subedges of the partition, d(P, Q) is concave. 3. Otherwise, d(P, Q)is linear. Clearly, if Lp=Lqthe distance d(P, Q) is convex because the arc segment between Pand Q is the shortest path between them, and it is concave if Lp⊆[u, ¯w], Lq⊆[¯u, w] (or vice-versa), with ¯w6= ¯u(which arises when d(u, w)< l(u, w), that is, when the edge [u, w] is not the shortest path between u, w, as in Figure 1(b)). As above, by denoting x=l(u, P) and y=l(u, Q), we have: d(P, Q) =          |x−y|, Lp=Lq min{y−x, x +d(u, w) + l(u, w)−y}, Lp⊆[u, ¯w], Lq⊆[¯u, w],¯w6= ¯u |y−x|,otherwise Note that in the third case, the distance |y−x|becomes linear, according with the order in which Lpand Lqare placed. If d(u, w) = l(u, w), then u= ¯wand ¯u=w, therefore the distance d(P, Q) is convex (if Lp=Lq), or linear (if Lp6=Lq). 4 Solving the problem on a network The solution method is based on decomposing the problem (1) in a collection of subproblems independent to each other, and solving each of them via discretization of the solution set. To this end and with purposes of readability, we will describe the process in three phases: the first one is devoted to both decomposing the problem (1) and identifying the two type of subproblems, the second one deals with the subproblems of type 1, and finally in the last step we will study the subproblems of type 2. Next it will be described both type of subproblems. 4.1 Decomposing the problem To decompose the problem we first need the matrix ∆ = (d(vi, vj))i,j of shortest distances between all pairs of nodes of the network N. This matrix can be calculated in O(|V||E|) running time. Then, for each edge e∈Ewe compute, and sort, the arc bottleneck points of the set Be(in O(|V|log |V|) time). At the end of this process we have, for each edge eof the network, the ordered sequence L(e) of all linear arc segments of the edge. Besides, given a pair of different edges ep= [up, wp] and eq= [uq, wq] we know if two linear arc segments Lp∈ L(ep) and Lq∈ L(eq) are, or not, antipodal to each other. If epand eqare the same edge e= [u, w] (which is the case of Lemma 7), we also know the location of the linear arc segments on the subedges of the partition induced by {u, ¯w, ¯u, w}. 5 Let L=[ e∈EL(e) be the set of all linear arc segments of the overall network. Thus problem (1) is decomposed into a set of subproblems, where each of them is obtained by restricting the feasible space N × N to Lp×Lq, with Lp, Lq∈ L. By imposing that X1∈Lp,X2∈Lqwe obtain the restricted problem: max F(X1, X2) := X (i,j)∈C(X1,X2) tij s.t. (X1, X2)∈Lp×Lq, Lp, Lq∈ L (2) A solution to problem (1) is found by solving the collection of all |L|2restricted problems (2), and then selecting the best solution. The classification of the restricted problem (2) is done according to the concavity of the distance d(X1, X2). If d(X1, X2) is either linear or convex, we classify the restricted problem as type 2. Otherwise, as type 1. More specifically, consider the restricted problem formulated in (2). Then the pair {Lp, Lq}is called of type 1 if one of the following two conditions holds: (Lemma 6-1): Lp∈ L(ep), Lq∈ L(eq), with ep6=eq, and Lp,Lqare antipodal to each other. (Lemma 7-2): Lp, Lq∈ L(e), with e= [u, w] such that d(u, w)< l(e), and Lp, Lqlie in not adjacent subedges of partition {u, ¯w, ¯u, w}. For the remaining cases, the pair {Lp, Lq}is said of type 2. 4.2 The concave case: The restricted problem of type 1 The problem can be formulated as follows max F(X1, X2) := X (i,j)∈C(X1,X2) tij s.t. (X1, X2)∈Lp×Lq Lp, Lq∈ L,{Lp, Lq}of type 1 (3) Each linear arc segment is a rectifiable subedge in which all distance functions d(vi, P) are linear, and each vertex vi∈Vlinks with all points of such subedge via one of their extreme points. On the other hand, we have: 1. For each Ai∈ A, the Euclidean distance ||Ai−X||2is convex when Xvaries in any linear arc segment. In effect, from convexity theory (see [1, 9]), if fis a convex function in an open set Uthen the restriction of fto any interval (i.e., straight line segment) inside U is convex. Since every norm on IRnis convex, the result follows straightforwardly. 2. When (X1, X2)∈Lp×Lq, with {Lp, Lq}of type 1, the distance d(X1, X2) is concave (Lemmas 6 and 7), and also is concave dN(X1, X2) = α d(X1, X2) (where α∈(0,1) is the speed factor). Therefore the function hij (X1, X2) = ||Ai−X1||2+dN(X1, X2) + ||X2−Aj||2is neither convex nor quasiconvex on Lp×Lq(and similarly for hij (X2, X1)). To illustrate some concepts and properties associated to this case, we will use the small network with trapezoidal shape shown in Figure 2. Length of basis of trapezoid are 7 and 5, respectively, and the four vertices up, wp, uqand wqof network are the points (0,2√6), (5,2√6), (−1,0) and (6,0), respectively. The only arc bottleneck points are ¯wp= (0,0) and ¯up= (5,0) opposite to wpand up, respectively. By selecting Lp= [up, wp] and Lq= [ ¯wp,¯up], then Lp, Lqare antipodal to each other (note that in this example, Lpis the whole edge). Subsequent 6 examples on this network deal with the O/D pair (i, j), corresponding to points Ai(2.5,6) and Aj(1,−4). (−1,0) uq (6,0) wq (0,2√6) up (5,2√6) 5 5 wp (0,0) (5,0) Lp Lq wpup Ai(2.5,6) Aj(1,−4) Figure 2. Antipodal linear arc segments Lp= [ ¯wq,¯uq] = [up, wp] and Lq= [ ¯wp,¯up] The strategy for solving this problem is based on identifying a Finite Dominating Set (FDS) such that an optimal solution can be found by selecting the best solution from the FDS. To this end we first introduce some definitions and a collection of sublevel sets which will be used in the construction of such a set. When (X1, X2)∈Lp×Lq, and {Lp, Lq}are two linear arc segments of type 1, the distance d(X1, X2) is a concave function obtained from the lower envelope of two linear functions: da(X1, X2) and db(X1, X2). That is, d(X1, X2) = min{da(X1, X2), db(X1, X2)}, where this expression is obtained from Lemmas 6 and 7 (according to whether or not Lpand Lqlie in different edges), by replacing Pand Qby X1and X2, respectively. More specifically, 1. From Lemma 6, da(X1, X2) = x+d(up, uq) + y, and db(X1, X2) = l(up, wp)−x+d(wp, wq)+ l(uq, wq)−y 2. From Lemma 7, da(X1, X2) = y−x, and db(X1, X2) = x+d(u, v) + l(u, w)−y For simplicity of notation, henceforth we will use (x, y) and (X1, X2) indistinctly. In the example of Figure 2, denoting by xand ythe lengths of subedges [up, X1] and [ ¯wp, X2], respectively, the distance d(X1, X2) is given by d(X1, X2) = min{6 + x+y, 16 −x−y},with (x, y)∈[0,5] ×[0,5] Therefore, the length hij (X1, X2) of travel path (Ai, X1, X2, Aj) can be expressed as: hij (X1, X2) = ||Ai−X1||2+αmin{da(X1, X2), db(X1, X2)}+||X2−Aj||2 and consequently hij(X1, X2) = min{ga ij(X1, X2), gb ij (X1, X2)} 7 where ga ij (X1, X2) = ||Ai−X1||2+α da(X1, X2) + ||X2−Aj||2 gb ij (X1, X2) = ||Ai−X1||2+α db(X1, X2) + ||X2−Aj||2 Since d(X2, X1) = d(X1, X2), in a similar manner we can define the length hij(X2, X1) of travel path (Ai, X2, X1, Aj): hij(X2, X1) = min{ga ij(X2, X1), gb ij (X2, X1)} with gt ij(X2, X1) = ||Ai−X2||2+α dt(X1, X2) + ||X1−Aj||2, where the superindex t∈ {a, b} refers to the case determined by the formula for d(X1, X2). For example, when X1∈Lp,X2∈Lq, Figure 3 (left) shows the function hij (X1, X2) of network of Figure 2 for α= 0.3. Note the pagoda roof-shape of the surface. For each O/D pair (i, j), the functions hij (X1, X2) and hij(X2, X1) indicate the length of travel paths (Ai, X1, X2, Aj) and (Ai, X2, X1, Aj), respectively. Therefore, the following notation uses the superindex “12” for the first path and “21” for the second path (this notation was also used in [5]). Definition 8 [Sublevel Sets] Let {Lp, Lq}be two linear arc segments of type 1 such that (X1, X2)∈Lp×Lq. For η≥0, let us consider: 1. The (η)-sublevel set S12 ij (η) of function hij(X1, X2), given by: S12 ij (η) = {(X1, X2)∈Lp×Lq:hij(X1, X2)≤η} Analogously, S21 ij (η) = {(X1, X2)∈Lp×Lq:hij (X2, X1)≤η}. 2. For t∈ {a, b}, the (η)-sublevel sets G12(t) ij (η) and G21(t) ij (η), of functions gt ij(X1, X2) and gt ij(X2, X1), respectively, given by: G12(t) ij (η) = {(X1, X2)∈Lp×Lq:gt ij(X1, X2)≤η} G21(t) ij (η) = {(X1, X2)∈Lp×Lq:gt ij(X2, X1)≤η} For several η-values, Figure 3 (right) displays the corresponding level sets S12 ij (η) of the surface on the left of the figure. 8 Figure 3. Surface hij (X1, X2) for α= 0.3 (left), and sets S12 ij (η) of such a surface (right) For t∈ {a, b}, the functions gt ij(X1, X2) are the sum of the convex term ||Ai−X1||2+||Aj− X2||2and the linear function α dt(X1, X2). Similarly, gt ij(X2, X1) is also the sum of a convex and a linear term. Therefore, the convexity of the sets G12(t) ij (η) and G21(t) ij (η), for t∈ {a, b}, is a straightforward consequence (see [1]). From these definitions, we have Lemma 9 Sτ ij(η) = Gτ(a) ij (η)∪Gτ(b) ij (η), for τ∈ {12,21}. Proof: We prove the lemma by double inclusion. Without loss of generality, we assume τ= 12. Let (X1, X2)∈S12 ij (η) = {(X1, X2)∈Lp×Lq:hij(X1, X2)≤η}be such that hij(X1, X2) = min{ga ij(X1, X2), gb ij (X1, X2)}=gt ij(X1, X2), for some t∈ {a, b}. Since gt ij(X1, X2)≤η, then (X1, X2)∈G12(t) ij , which implies S12 ij (η)⊆G12(a) ij (η)∪G12(b) ij (η). Conversely, if (X1, X2)∈G12(a) ij (η)∪G12(b) ij (η), then (X1, X2) belongs to (at least) one of such sets, suppose (X1, X2)∈G12(a) ij (η). If (X1, X2)/∈G12(b) ij (η), then gb ij(X1, X2)> η, therefore hij(X1, X2) = ga ij(X1, X2)≤ηwhich implies (X1, X2)∈S12 ij (η). If (X1, X2)∈G12(b) ij (η), then hij(X1, X2)≤max{ga ij(X1, X2), gb ij(X1, X2)} ≤ η, consequently (X1, X2)∈S12 ij (η). In this case we have obtained the converse inclusion G12(a) ij (η)∪G12(b) ij (η)⊆S12 ij (η), which concludes the proof. ⊗ From this result, both S12 ij (η) = G12(a) ij (η)∪G12(b) ij (η) and S21 ij (η) = G21(a) ij (η)∪G21(b) ij (η) are the union of two convex (but possibility not disjoint) sets. The following example shows that G12(a) ij (η)∩G12(b) ij (η)6=∅, for some η-values, with η < ||Ai−Aj||2. In Figure 2, we have ||Ai−Aj||2=√409 2≃10.11. Figure 4 (a) displays, for α= 0.4 and η= 10, the boundaries of the sublevel sets G12(a) ij (η) and G12(b) ij (η). It can be observed that the intersection of both sets is not empty. Proposition 10 For any 0≤η < ||Ai−Aj||2,S12 ij (η)∩S21 ij (η) = ∅. Proof: Let ηbe any value such that 0 ≤η < ||Ai−Aj||2. To establish the result it is sufficient to prove that, for t∈ {a, b},G12(t) ij (η)∩S21 ij (η) = ∅. Without loss of generality, we will prove G12(a) ij (η)∩S21 ij (η) = ∅. Assume (X1, X2)∈G12(a) ij (η). Then ga ij(X1, X2) = ||Ai−X1||2+α da(X1, X2) + ||X2−Aj||2≤η < ||Ai−Aj||2 This implies ||Ai−X1||2+||X2−Aj||2<||Ai−Aj||2. By combining this inequality with the triangular property, we can write ||Ai−Aj||2≤ ||Ai−X1||2+||X1−Aj||2<||Ai−Aj||2−||X2−Aj||2+||X1−Aj||2 By applying again the triangular property ||Ai−Aj||2≤ ||Ai−X2||2+||X2−Aj||2to the right hand side, we finally obtain ||Ai−Aj||2<||Ai−X2||2+||X1−Aj||2. Consequently η < ||Ai−Aj||2<||Ai−X2||2+||X1−Aj||2+αmin{da(X1, X2), db(X1, X2)}=hij (X2, X1) Since η < hij (X2, X1) = min{ga ij(X2, X1), gb ij(X2, X1)}, then (X1, X2)/∈G21(a) ij (η)∪G21(b) ij (η) = S21 ij (η), which concludes the proof. ⊗ 9 References [1] S.P. Boyd and L. Vanderberghe.Convex Optimization. Cambridge University Press, 2004. [2] H. Hamacher, A. Liebers, A. Sch¨ obel, D. Wagner, F. Wagner.Locating new stops in a railway network. Electronic Notes Theoretical Computers Science 50 (2001), 1-11 [3] J.J. Hooker, R.S. Garfinkel, C.K. Chen.Finite dominating sets for network location problems. Operations Research 39 (1991), 100-118. [4] F. Kirwan.Complex Algebraic Curves. Cambridge University Press, 1992. [5] M-C. K¨ orner, J.A. Mesa, F. Perea, A. Sch¨ obel, D. Scholz.A Maximum trip covering location problem with alternative mode of transportation on tree networks and segments. TOP (2012): DOI: 10.1007/s11750-012-0251-y. [6] G. Laporte, J.A. Mesa, F.A. Ortega.Locating stations on rapid transit lines. Computers & Operations Research 29 (2002), 741-759. [7] G. Laporte, J.A. Mesa, F.A. Ortega, I. Sevillano.Maximizing trip coverage in the location of a single rapid transit line alignment. Annals of Operations Research 136 (2005), 49-61. [8] H.M. Repolho, A.P. Antunes, R.L. Church.Optimal location of railway stations: The Lisbon-Porto High-Speed rail Line. Transportation Science 47 (2013), 330-343. [9] R.T. Rockafeller.Convex Analysis. Princeton University Press, 1970. [10] A. Sch¨ obel.Locating stops along bus or railway lines. A bicriteria problem. Annals of Operations Research 136 (2005), 211-227. [11] A. Sch¨ obel, H. Hamacher, A. Liebers, D. Wagner.The continuous stop location problem in public transportation networks. Asia-Pacific Journal of Operational Research 26 (2009), 13-30. [12] A. Sch¨ obel, D. Scholz.The Big Cube Small Cube Solution Method for Multidimensional Facility Location Problems. Computers & Operations Research 37 (2010), 115-122. [13] V.R. Vuchic, G.F. Newell.Rapid transit interstation spacing for minimum travel time. Transportation Science 2(1968), 303-309. [14] V.R. Vuchic.Rapid transit interstation spacings for maximum number of passengers. Transportation Science 3(1969), 214-232. 16