A general approach for the location of transfer points on a network with a trip covering criterion and mixed distances

A general approach for the location of transfer points on a network with a trip covering criterion and mixed distances M. C. López-de-los-Mozos a, Juan A. Mesa b, Anita Schöbel c a Departamento de Matemática Aplicada I, E.T.S. de Ingeniería Informática, Avda. Reina Mercedes, s/n, 41012, Universidad de Sevilla, Spain b Departamento de Matemática Aplicada II, E.T.S. de Ingeniería, Camino de los Descubrimientos, s/n, 41092, Universidad de Sevilla, Spain c Institut für Numerische and Angewandte Mathematik. Universität Göttingen, Germany Keywords: Location Networks Covering problems Mixed distances a b s t r a c t In this paper we consider a trip covering location model in a mixed planar-network space. An embedded network in the plane represents an alternative transportation system in which traveling is faster than traveling within the plane. We assume that the demand to be covered is given by a set of origindestination pairs in the plane, with some traffic between them. An origin-destination pair is covered by two facility points on the network (or transfer points), if the travel time from the origin to destination by using the network through such points is not higher than a given acceptance level related to the travel time without using the network. The facility location problems studied in this work consist of locating one or two transfer points on the network such that, under several objective functions, the traffic through the network is maximized. Due to the continuous nature of these problems, a general approach is proposed for discretizing them. Since the non-convexity of the distance function on cyclic networks also implies the absence of convexity of the mixed distance function, such an approach is based on a decomposition process which leads to a collection of subproblems whose solution set can be found by adapting the general strategy to each problem considered. 1. Introduction Given a real or virtual underlying network, the general network design problem consists of two intertwined problems ( Contreras & Fernández, 2012 ): to select from the network a number of points for siting facilities, and to interconnect these points by choosing links of the underlying network. In our problem we have a network embedded in the plane and a set of demand points in the plane. The demand or traffic between demand points is given by an OD-matrix (Origin-Destination matrix) which is assumed to be static, and it is satisfied by traveling from one to the other point of each pair. We want to select points on the network to access/ exit to/from it. These facility points are used to transfer from the plane to the embedded given network, thus allowing the connection of the pairs of demand points by using the network. A subproblem of the general network design problem arises in the design of a railway network ( Laporte & Mesa, 2015; Laporte, Mesa, & Ortega, 20 0 0) that consists in locating a number of stations and the tracks to connect the station-facilities. The problem of locating stations in a railway network was indirectly tackled in Vuchic and Newell (1968) , in which the optimal interstation spacing problem in a commuter line was researched. The objective of this problem is 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 Vuchic (1969) in order to maximize the number of passengers on the basis of shortest travel times. The aim was also to determine the optimal interstation space between pairs of adjacent stations. Apart from the papers ( Laporte, Mesa, & Ortega, 2002; Laporte, Mesa, Ortega, & Sevillano, 2005; Repolho, Antunes, & Church, 2013 ) in which the feasible solution space for locating stations was discrete and the objectives were to maximize the passenger coverage, trip coverage and savings in travel cost, respectively, several objective functions have been considered in those models in which stations can be located along the edges of the railway network: saving in passenger travel time ( Hamacher, Liebers, Schöbel, Wagner, & Wagner, 2001 ), coverage/number of new stations ( Schöbel, 2005 ), additional travel time ( Schöbel, Hamacher, Liebers, & Wagner, 2009 ), and total travel time ( Carrizosa, Harbering, & Schöbel, 2016 ). The maximal covering location problem was introduced in Church and ReVelle (1974) in which a number of facilities are to be located on a network so that the population within a service distance is maximized. In Murawski and Church (2009) time to access the facilities is improved by upgrading edges of the transportation network. The objective function consists in maximizing the number of people who are covered by upgrading some parts of the network. In order to locate interchanges points in a highway network a cost-benefit objective function is considered in Repolho, Church, and Antunes (2010) that takes into account a route choice model. In the problem dealt with in this paper, there are existing demand points in the Euclidean plane whereas new facilities are to be located in a 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 plane-network combination in which the section on the network is supposed to be traversed faster than those on the plane. Therefore, there is competition between the mode that only uses the planar distance and the combined one. If the time spent by the trip in the combined mode is lower than that of the planar mode then the OD-pair is said to be covered by the transfer points used to access/exit the network. 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 assume the decision space is the set of points on the edges of the network. The nature of the decision space when locating new transfer points in long and medium distance railway networks as well as in underground urban/suburban rapid transit systems is continuous. As was pointed out in Laporte, Mesa, and Perea (2014) 30% of the stations of the Spanish high-speed network are situated outside cities in the countryside, thus allowing a continuous decision space. Furthermore, the continuous setting of the decision space allows the use of continuous optimization methods thus providing insight into the behavior of the objective function and the problem itself. Moreover, new development areas, congestion or environmental and energy consumption are reasons for constructing new stations. An example is the use of a section of the railway line Seville-Huelva as a new commuter line (Line 5) for the metropolitan area of Seville ( Laporte et al., 2014 ). For this line new stations were built, some of them between towns. Another example is the construction of a new station in the high-speed line Madrid-Seville between Córdoba and Puertollano stations. The new station: Villanueva de Córdoba-Los Pedroches covers an area of the north of the province of Córdoba. Since the traveling demand is given by pairs of existing points it is coherent to consider the location of pairs of transfer points acting as access/exit points on the network. Under the assumption of a network with a set of existing node-stations, there are two problems particularly relevant from an applied point of view, which deal with locating one, or two, transfer points in order to maximize the amount of OD-pairs additionally covered, that is, those OD-pairs which cannot be covered by the existing stations. In the first problem only one transfer point is located since this point in combination with each station works as an access/exit point. In the second problem, which seeks to locate two transfer points, the additional coverage refers the OD-pairs covered either by the two transfer points or by a combination of each point with some station, but not yet covered by pairs of vertices. Both problems also exclude the OD-pairs previously covered by the existing stations. Moreover, the second problem presents a more general formulation of the model, in the way that it incorporates the additional coverage provided both by the two points and by each point separately. For solving these additional covering problems, this paper proposes a methodology which is based on considering a key problem, whose solution procedure provides a general approach which can be adapted to the remaining problems. This key problem does not require any hypothesis on the network (it is possible that there is no already located station), since it seeks to locate two transfer points maximizing the amount of OD-pairs covered. The relevance of this problem derives from it allowing the development of a theoretical framework which is shared by the above one or two transfer additional covering problems, as well as by other related problems. Summarizing, the main contribution of this paper is, in the first place, to propose a comprehensive approach for solving several problems dealing with locating transfer points on cyclic transportation networks under several objective functions, all of them focused on covering OD-pairs instead of single demand points. Moreover, the proposed approach to solve the problem of maximizing the coverage obtained by 2-transfer points is used for the more real problems of locating one or two transfer points so that the additional coverage (in presence of already functioning stations) will be maximized. The problems studied deal with a continuous model, whose analysis enlarges the knowledge on both the geometric structure of the problems and the behavior and properties of the objective functions. On the other hand, such an approach describes a flexible methodology which, by incorporating slight modifications, allows to discretize the solution set of all problems considered. In a previous paper ( Körner, Mesa, Perea, Schöbel, & Scholz, 2014 ) the key problem was solved when the new facilities are to be located in segments and tree networks. In this paper we extend the approach applied in Körner et al. (2014) 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 main aim of this research is to solve that complex continuous location problem by reducing the candidate set to a finite one from which an optimal solution is selected by means of a polynomial time algorithm. The paper is organized as follows: after this introduction the elements of the model are presented in Section 2 . The necessary definitions and results on the distance on networks are summarized in Section 3 . Section 4 provides a decomposition of the first problem into two types of subproblems, such that for each subproblem a solution method is proposed in Sections 5 . Sections 6 and 7 study respectively two new problems, both related to the previous one, in which one and two transfer points are located under different objective functions, and Section 8 is devoted to presenting the corresponding algorithms and discussing its computational complexity. The paper ends with some conclusions and further research. 2. Elements of the model In order to formulate the problems with a mixed mode of transportation, we consider a connected network N (V, E) representing a high-speed system, with | V | nodes and | E | edges (where | ·| denotes cardinality). We assume that the network is embedded in the Euclidean plane and that each undirected edge e ∈ E 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 N will allow us to compute the distances along the network. More precisely, the length l(u, v ) of an edge (or a subedge) [ u, v ] is the Euclidean distance || u −v || between its endpoints, and by using shortest path algorithms we can moreover compute the distance between each pair of nodes. Moreover, the triangle inequality holds in this model. Let N be the continuum set of points of the edges. The edge lengths induce a distance function d such that, for any two points x, y ∈ N , d ( x , y ) is the length of any shortest path in N (V, E) connecting x and y . If x and y are on the same edge, then d ( x , y ) coincides with the length of the subedge [ x , y ]. For x, y ∈ N , the travel distance between both points is given by αd ( x , y ), with α∈ (0, 1). Parameter αis a speed factor, such that Ai Aj X1 X2 Ai Aj X1 X2 Fig. 1. Travel paths for: h + ij (X 1 , X 2 ) (left), and h − ij (X 1 , X 2 ) (right). αd ( x , y ) represents the traveling time between x , y by using the high-speed network. It can immediately be seen that, with these distance, N is a metric space. •Let A = { A i = (a i , b i ) , i = 1 , . . . , n } ⊂IR 2 be a set of existing demand points on the plane. We assume that distances between two points in the plane can be estimated by the Euclidean metric. •Let T = (t ij ) ∈ IR n ×n be an origin-destination matrix in which trip patterns are codified, i.e., t ij is the weight of the ordered pair ( i , j ). This matrix is known a priori: for example, in a transportation context each t ij can be viewed as the number of trips from an origin A i to a destination A j , and in a telecommunication setting it could represent the amount of data transferred from server A i to server A j . •Given an OD-pair ( i , j ), the travel distance by using the network through the points X 1 , X 2 ∈ N (or the 2-facility point ( X 1 , X 2 )) is obtained from the two possible travel paths: ( A i , X 1 , X 2 , A j ), and ( A i , X 2 , X 1 , A j ), linking origin and destination (see Fig. 1 ). For each of them, the travel distance is given by h+ ij(X 1 , X 2 ) = || A i −X 1 || + αd(X 1 , X 2 ) + || X 2 −A j || h− ij(X 1 , X 2 ) = || A i −X 2 || + αd(X 2 , X 1 ) + || X 1 −A j || . The mixed travel distance between A i and A j by using the highspeed network through the transfer points X 1 , X 2 ∈ N is given by the shortest travel distance obtained from both travel paths, and it is written as: f ij (X 1 , X 2 ) = min { h+ ij (X1 ,X2 ),h− ij (X 1 , X 2 ) } . Symmetry of such paths implies h + ij (X 1 , X 2 ) = h − ji (X 1 , X 2 ) , h− ij (X1 ,X2 )=h+ ji (X 1 , X 2 ) , and therefore f ij (X 1 , X 2 ) = f ji (X 1 , X 2 ) . •Let  D = (  d ij ) ∈ IR n ×n be a symmetric matrix, with 0 ≤ d ij < || A i −A j || , for i  = j , and  d ii = 0 , i = 1 , . . . , n . The values of  D represent the acceptance levels for using the network, meaning that the OD-pair ( i , j ) chooses the high-speed network if and only if the mixed travel distance by using it is less than or equal to  d ij . In other words, the OD-pairs always choose the faster option. In the following, we assume that i  = jto avoid the trivial case. Definition 1. The OD-pair ( i , j ) is covered by X 1 , X 2 ∈ N if f ij (X 1 , X 2 ) ≤ d ij . Let C ( X 1 , X 2 ) be the set of O/D pairs covered by X 1 , X 2 , given by C(X 1 , X 2 ) = { (i, j) , i  = j, 1 ≤i, j ≤n : f ij (X 1 , X 2 ) ≤ d ij } . From symmetry both of the acceptance level matrix  D and the mixed travel distance we have (i, j) ∈ C(X 1 , X 2 ) if and only if (j, i ) ∈ C(X 1 , X 2 ) . As it has been pointed out in the previous section, in the first place we formulate the key problem, which presents structural properties shared by the remaining problems, and whose solution procedure provides a general methodology for analyzing and solving the one and two additional covering problems, which are formulated subsequently. Ai Aj X1 X2 Ak Fig. 2. Given the nonnegative acceptance levels  d ij < || A i −A j || ,  d ik < || A i −A k || ,  d jk < || A j −A k || , and a suitable speed factor α∈ (0, 1), we have ( i , j ), ( i , k ) ∈ C ( X 1 , X 2 ). However ( j , k ) ∈ C ( X 1 , X 2 ). The objective value at ( X 1 , X 2 ) is: F (X 1 , X 2 ) = t ij + t ji + t ik + t ki . There may be several points ( X 1 , X 2 ) with the same objective value. 1. The first objective function measures the total weight of OD- pairs captured by each pair of transfer points X 1 , X 2 ∈ N , and it is given by: F (X 1 , X 2 ) =  (i,j) ∈ C(X 1 ,X 2 ) t ij . In this function whether the node set V contains already located stations or not is not relevant, since it seeks to compute the weight of pairs covered by the two transfer points when they assume the symmetric role of access/exit points (see Fig. 2 ). The key problem, briefly the 2-transfer covering problem (2- TC), is to find two transfer points X 1 , X 2 ∈ N such that the sum of weights of all OD-pairs covered by such points is maximized: max X 1 ,X 2 ∈N F (X 1 , X 2 ) :=  (i,j) ∈ C(X 1 ,X 2 ) t ij (2-TC) 2. Contrary to the above model, this problem and the following one deal with additional coverage, and they require the hypothesis of having a set of stations already located, these latter ones selected from the node set. Without loss of generality we can assume that all nodes of V are already located transfer points. From Definition 1 , the OD-pair ( i , j ) is covered by any X ∈ N if there exists v ∈ V such that f ij (X, v ) ≤ d ij . Thus, the set C ( X ) containing the OD-pairs covered by X is C(X ) = { (i, j) , i  = j, 1 ≤i, j ≤n : f ij (X, v ) ≤ d ij for some v ∈ V } Similarly, the set C V of OD-pairs already covered by the nodes of V is given by C V = { (i, j) , i  = j, 1 ≤i, j ≤n : f ij (w, v ) ≤ d ij for some w, v ∈ V } Thus, the second objective function can be stated as F V (X ) :=  (i,j) ∈ C(X) \ C V t ij And the 1-transfer additional covering problem (1-TAC) is: max X∈NF V (X ) :=  (i,j) ∈ C(X) t ij (1-TAC) Finally, in this case two transfer points ( X 1 , X 2 ) are located by addressing the additional coverage. As above, we assume that all nodes are stations, and also the set C V is excluded. The objective function integrates the above formulations since it takes into account both the amount of OD- pairs covered by ( X 1 , X 2 ) and the OD-pairs covered by each point in combination with the stations already located at nodes, as follows: F A (X 1 , X 2 ) :=  (i,j) ∈ C(X 1 ,X 2 ) ∪ C(X 1 ) ∪ C(X 2 ) \ C V t ij The 2-transfer additional covering problem (2-TAC), seeks the location of two transfer points maximizing the total weight of OD-pairs additionally covered: max X 1 ,X 2 ∈N F A (X 1 , X 2 ) :=  (i,j) ∈ C(X 1 ,X 2 ) ∪ C(X 1 ) ∪ C(X 2 ) \ C V t ij (2-TAC) Remark 2. Each pair of associated problems obtained by excluding, or not, C V from the corresponding formulation are equivalent, but not the same, in the following way: they share the same solution set (which is a straightforward consequence from the fact that C V is a constant set), although their optimal solutions could be different. That is, (2-TC) and max X 1 ,X 2 ∈N F (X 1 , X 2 ) :=  (i,j) ∈ C(X 1 ,X 2 ) \ C V t ij are equivalent, and so on. Although problems (1-TAC) and (2-TAC) present special relevance regarding the applications, the procedure for solving problem (2-TC) provides a general methodology which can be applied to all problems presented in this paper. In fact, the nature of such a methodology allows the resolution to be extended to some generalizations of these problems, as the p -transfer additional covering problem ( p > 2). This motivates that problem (2-TC) is studied in the first place. The strategy for solving this problem lies in decomposing it into a collection of subproblems such that, for each of them, a partition of the feasible solution set is constructed, and from such partition, a finite subset containing some optimal solution is selected. Problem (2-TC) has been first solved for the particular case where N is a segment of a straight line, and subsequently the method was extended to the case where N is a tree network T (see Körner et al., 2014 ). Thus, henceforth we will consider that N contains at least one cycle. Under this assumption, the approach applied to the tree network case cannot be directly extended to this case due to the absence of convexity of the distance function on a cyclic network. In order to solve this problem, we next summarize some concepts and results on distances in networks. 3. Previous results on distances on networks For evaluating the objective function of problem (2-TC) , it is first necessary to obtain an analytical expression for the distance between any two points P , Q , of the network N . The aforementioned non-convexity leads to the fact that the expression for the distance d ( P , Q ) could vary through the network. In this section we partition the network into a collection of subedges such that for each pair of subedges, the distance between their points can be computed. To this end, we first need to review some concepts dealing with the distance on networks. Hereinafter we assume a network N with a distance function d ( ·, ·) such that the triangle inequality holds. Let e = [ u, w ] ∈ Ebe an edge of N with length l e , and let P be a point on edge e . Let x = l(u, P ) denote the length of subedge [ u , P ], and let l(w, P ) = l e −x denote the length of subedge [ P, w ] . It is well known that for any node v ∈ V, the distance d(v , P ) = min { d(v , u ) + x, d(v , w ) + l e −x } is concave and piecewise linear on x ∈ [0, l e ], with at most two pieces with slopes 1 and −1 . From the triangle inequality we have l e = d(u, w ) ≤| d(v , u ) −d(v , w ) | , therefore the distance function d(v , P ) on [ u, w ] is linear. For the sake of completeness we include the following concepts and definitions, although all of them uq upwp wq uq wq wpup Fig. 3. Antipodal points. can be found in Hooker, Garfinkel, and Chen. (1991) and references therein. Definition 3. 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 Q in [ u, w ] . Definition 4. A point ¯ v ∈ [ u, w ] , other than a node, is called an arc bottleneck point if there is a node v for which ¯ v is antipodal to v . In this case, we call it the arc bottleneck point ¯ v . Clearly, the edge e = [ u, w ] contains at most | V | arc bottleneck points. If ¯ v ∈ [ u, w ] is antipodal to v we have d(v , u ) + l(u, ¯ v ) = d(v , w ) + l(w, ¯ v ) , hence such a point ¯ v can be identified by the length of the subedge [ u, ¯ v ] , given by: l(u, ¯ v ) = d (v ,w ) −d (v ,u )+ l e 2 . Definition 5. Let B e be the set of arc bottleneck points of edge e = [ u, w ] , and let ¯ v , ¯ v  be two adjacent points of B e ∪ { u, w } . Then the closed subedge L = [ ¯ v , ¯ v  ] is called a linear arc segment (or a treelike segment ( Hooker et al., 1991 )). We remark that B e has O (| V |) elements. On each linear arc segment the distance d(v , ·) is linear. If B e = ∅ the entire edge e = [ u, w ] (including nodes) is a linear arc segment. The set of all linear arc segments of an edge e is denoted by L (e ) . Let [ u p , w p ] and [ u q , w q ] be two edges of the network N , and let [ ¯ w p , ¯ u p ] ⊆[ u q , w q ] , [ ¯ w q , ¯ u q ] ⊆[ u p , w p ] be the subedges for which the extreme points are antipodal points as follows: ¯ u p , ¯ w p are the antipodal points to u p , w p , respectively, and ¯ u q , ¯ w q are the antipodal points to u q , w q , respectively (see Fig. 3 ). From previous definitions we have l( ¯ w q , ¯ u q ) = l( ¯ w p , ¯ u p ) and d( ¯ w q , ¯ w p ) = d( ¯ u q , ¯ u p ) (see Hooker et al., 1991 for a more detailed explanation). Definition 6. Let L p , L q be two linear arc segments of different edges [ u p , w p ] and [ u q , w q ] , respectively, and let [ ¯ w q , ¯ u q ] ⊆[ u p , w p ] and [ ¯ w p , ¯ u p ] ⊆[ u q , w q ] be the subedges for which ¯ u p , ¯ w p are the antipodal points to u p , w p , respectively, and ¯ u q , ¯ w q are the antipodal points to u q , w q , respectively. If L p ⊆[ ¯ w q , ¯ u q ] and L q ⊆[ ¯ w p , ¯ u p ] , then L p , L q are called antipodal segments to each other. (This definition includes the case [ ¯ w q , ¯ u q ] = [ u p , w p ] and [ ¯ w p , ¯ u p ] = [ u q , w q ] ). The following result summarizes the behavior of distance d ( P , Q ) on linear arc segments of different edges (see Hooker et al., 1991 ). Lemma 7. Let P be restricted to linear arc segment L p of edge [ u p , w p ] and Q to linear arc segment L q of edge [ u q , w q ] , with [ u p , w p ]  = [ u q , w q ] . 1. If L p , L q are 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 P on the segment [ ¯ w q , ¯ u q ] and a point Q on the segment [ ¯ w p , ¯ u p ] behaves like the distance on the parallelogram in Fig. 3 (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(u p , P ) , with x ∈ [0 , l(u p , w p )] and y = l(u q , Q) , with y ∈ [0 , l(u q , w q )] , we can compute the distance d ( P , Q ) for the cases considered in this lemma. d(P, Q) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ min { x + d(u p , u q ) + y, l(u p , w p ) −x + d(w p , w q ) + l(u q , w q ) −y } , L p , L q antipodal x + d (u p , u q ) + y, L p ⊆[ u p , ¯ w q ] , L q ⊆[ u q , ¯ w p ] or L q ⊆[ ¯ w p , ¯ u p ] x + d (u p , w q ) + l(u q , w q ) −y, L p ⊆[ u p , ¯ w q ] , L q ⊆[ ¯ u p , w q ] . Note that if L p , L q are antipodal segments, with u p  = ¯ w q , ¯ u q  = w p and similarly u q  = ¯ w p , ¯ u p  = w q , then the distance d ( P , Q ) can also be computed by min { x + d(u p , w q ) + l(u q , w q ) −y, l(u p , w p ) −x + d(w p , u q ) + y } . Finally, the remaining cases obtained by combining L p , L q can be reduced to one of these by symmetry (for example, for the case L p ⊆[ u p , ¯ w q ] , L q ⊆[ ¯ u p , w q ] the distance can also be equivalently obtained as l(u p , w p ) −x + d(w p , u q ) + y ). We now comment the case in which P , Q lie on the same edge e = [ u, w ] . Let L p , L q be two linear arc segments of e such that P ∈ L p , Q ∈ L q . The triangle inequality implies that L p and L q are not antipodal to each other, consequently the distance d ( P , Q ) is either convex (if L p = L q ), or linear (if L p  = L q ), and it is given by the length of subedge [ P , Q ]. By using the above notation x = l(u, P ) and y = l(u, Q) , we have d(P, Q) = | x −y | . 4. Decomposing the 2-transfer covering problem Summarizing the previous section, for each pair of linear arc segments the distance d ( P , Q ) between their respective points is either concave or convex, and its analytical expression can be computed. For this reason, the solution method is based on decomposing problem (2-TC) into a collection of independent subproblems (where each subproblem is the restriction of (2-TC) to a given pair of linear arc segments), and solving each of them via discretization of the solution set. To this end and for the sake of readability, we will describe the process in three phases: the first one is devoted to both decomposing the problem (2-TC) and grouping the subproblems into two cases: the concave and the convex case. The second phase deals with the subproblems of the first case, and finally in the last step we will study the subproblems of the second. These two cases will be described as follows. To decompose the problem we first compute, in O (| V || E |) time, the distance matrix between all pairs of nodes of the network. Then, for each edge e ∈ E we obtain, and sort, the set B e (in O (| V |log | V |) time). At the end of this process we have, for each edge e of the network, the ordered sequence L (e ) of all linear arc segments of the edge. Besides, given a pair of different edges e p = [ u p , w p ] and e q = [ u q , w q ] we know whether or not two linear arc segments L p ∈ L (e p ) and L q ∈ L (e q ) are antipodal. Let L =  e ∈ E L (e ) be the set of all linear arc segments of the overall network. Thus problem (2-TC) is decomposed into a set of subproblems, where each of them is obtained by restricting the feasible space N ×N to L p ×L q , with L p , L q ∈ L . By imposing that X 1 ∈ L p , X 2 ∈ L q we obtain the restricted problem: max X 1 ∈ L p , X 2 ∈ L q F (X 1 , X 2 ) :=  (i,j) ∈ C(X 1 ,X 2 ) t ij (2-TCR) A solution to problem (2-TC) is found by solving the collection of all O (|L| 2 ) restricted problems (2-TCR) (in fact, |L| (|L|−1) 2 restricted problems by symmetry), and then selecting the best solution. The classification of the restricted problem (2-TCR) is made according to the concavity of the distance d ( X 1 , X 2 ), which is related to the antipodal character of L p , L q . More specifically, problem (2- TCR) is concave if the following condition holds: Fig. 4. Network with V = { v i , i = 1 , . . . , 4 } , and linear arc segments L p , p = 1 , . . . , 8 . L p ∈ L (e p ) , L q ∈ L (e q ) , with e p  = e q , and L p , L q are antipodal to each other. For the remaining cases, the problem (2-TCR) is classified as convex. 5. A procedure for discretizing the restricted problem (2-TCR) This section is devoted to studying the restricted problem (2-TCR) for a given pair L p , L q ∈ L . Henceforth, we write ( X 1 , X 2 ) ∈ L p ×L q instead of X 1 ∈ L p , X 2 ∈ L q . The strategy for solving (2-TCR) is based on identifying a Finite Dominating Set (FDS), that is, a finite set of points ⊂L p × L q containing an optimal solution. From this set, (2-TCR) becomes the problem max (X 1 ,X 2 ) ∈ F (X 1 , X 2 ) . In order to describe the procedure for finding , the concave and convex cases are analyzed separately. 5.1. The concave case This problem can be formulated from (2-TCR) by adding the assumption “L p , L q are antipodal to each other”, and it will be identified as (2-TCR) (1). Each linear arc segment is a rectifiable subedge in which all distance functions d(v i , P ) are linear. On the other hand, we have: 1. For each A i ∈ A , the Euclidean distance || A i −X|| is convex when X varies in any linear arc segment. In effect, this result follows straightforwardly from convexity theory (see Rockafeller, 1970 ), since if f is a convex function in an open set U then the restriction of f to any interval (i.e., straight line segment) inside U is convex. 2. When ( X 1 , X 2 ) ∈ L p ×L q , with L p , L q antipodal to each other, the distance αd ( X 1 , X 2 ) is concave ( Lemma 7 ), where α∈ (0, 1) is the speed factor. Therefore both the function h + ij (X 1 , X 2 ) and h− ij (X 1 , X 2 ) are not convex on L p ×L q . To illustrate some concepts and properties associated with this case, we will use the network with trapezoidal shape shown in Fig. 4 . The lengths of the basis edges of the trapezoid are 7 and 5, respectively, and the nodes { v i , i = 1 , . . . , 4 } are indicated in the figure with their corresponding coordinates. Likewise, each ¯ v i represents the arc bottleneck point opposite to v i , i = 1 , . . . , 4 . This figure also shows the partition of the network originated by the set of linear arc segments L = { L p , p = 1 , . . . , 8 } . In this case, L 2 = [ ¯ v 3 , ¯ v 4 ] and L 6 = [ v 4 , v 3 ] are antipodal to each other. Fig. 5. Surface h + ij (X 1 , X 2 ) for α= 0 . 3 (left), and sets H + ij (η) of such a surface (right). In order to find an FDS for the problem, in the following we introduce the necessary definitions on the sublevel sets, from which the FDS is constructed. 5.1.1. Characterizing the sublevel sets When ( X 1 , X 2 ) ∈ L p ×L q , and { L p , L q } are antipodal to each other, the distance d ( X 1 , X 2 ) is a concave function obtained from the lower envelope of two linear functions: d a ( X 1 , X 2 ) and d b ( X 1 , X 2 ). That is, d(X 1 , X 2 ) = min { d a (X 1 , X 2 ) , d b (X 1 , X 2 ) } , where this expression is obtained from Lemma 7 by replacing P and Q by X 1 and X 2 , respectively. More specifically, if x = l(u p , X 1 ) and y = l(u q , X 2 ) , we have d a (X 1 , X 2 ) = x + d(u p , u q ) + y, and d b (X 1 , X 2 ) = l(u p , w p ) −x + d(w p , w q ) + l(u q , w q ) −y. If there is no confusion we will identify X 1 with x and X 2 with y . Therefore, the travel distance h + ij (X 1 , X 2 ) of travel path ( A i , X 1 , X 2 , A j ) can be expressed as h + ij (X 1 , X 2 ) = || A i −X 1 || + αmin { d a (X 1 , X 2 ) , d b (X 1 , X 2 ) } + || X 2 −A j || and consequently, h + ij (X 1 , X 2 ) = min { g + ,a ij (X 1 , X 2 ) , g + ,b ij (X 1 , X 2 ) } , where g + ,a ij (X 1 , X 2 ) = || A i −X 1 || + αd a (X 1 , X 2 ) + || X 2 −A j || g + ,b ij (X 1 , X 2 ) = || A i −X 1 || + αd b (X 1 , X 2 ) + || X 2 −A j || . Since d(X 2 , X 1 ) = d(X 1 , X 2 ) , in a similar manner we can define the travel distance h − ij (X 1 , X 2 ) of travel path ( A i , X 2 , X 1 , A j ): h − ij (X 1 , X 2 ) = min { g −,a ij (X 1 , X 2 ) , g −,b ij (X 1 , X 2 ) } , with g −,t ij (X 1 , X 2 ) = || A i −X 2 || + αd t (X 1 , X 2 ) + || X 1 −A j || , for t ∈ { a , b }. For example, when X 1 ∈ L 6 , X 2 ∈ L 2 , Fig. 5 (left) shows the function h + ij (X 1 , X 2 ) on the network of Fig. 4 for α= 0 . 3 , A i (2.5, 6), A j (1 , −4) . Note the pagoda roof -shape of the surface. Definition 8 (Sublevel Sets) . Let { L p , L q } be two linear arc segments antipodal to each other such that ( X 1 , X 2 ) ∈ L p ×L q . For η≥0, let us consider: 1. The ( η)-sublevel set H + ij (η) of function h + ij (X 1 , X 2 ) , given by: H + ij (η) = { (X 1 , X 2 ) ∈ L p ×L q : h + ij (X 1 , X 2 ) ≤η} . Analogously, H − ij (η) = { (X 1 , X 2 ) ∈ L p ×L q : h − ij (X 1 , X 2 ) ≤η} . 2. For t ∈ { a , b }, the ( η)-sublevel sets G + ,t ij (η) and G −,t ij (η) , of functions g + ,t ij (X 1 , X 2 ) and g −,t ij (X 1 , X 2 ) , respectively, given by: G + ,t ij (η) = { (X 1 , X 2 ) ∈ L p ×L q : g + ,t ij (X 1 , X 2 ) ≤η} G −,t ij (η) = { (X 1 , X 2 ) ∈ L p ×L q : g −,t ij (X 1 , X 2 ) ≤η} . For several η-values, Fig. 5 (right) displays the corresponding sublevel sets H + ij (η) of the surface represented on the left-hand side of the figure. For t ∈ { a , b }, the function g + ,t ij (X 1 , X 2 ) is the sum of the convex term || A i −X 1 || 2 + || A j −X 2 || 2 and the linear function αd t ( X 1 , X 2 ). Similarly, g −,t ij (X 2 , X 1 ) is also the sum of a convex and a linear term. Therefore, the convexity of the sets G + ,t ij (η) and G −,t ij (η) , for t ∈ { a , b }, is a straightforward consequence (see Boyd & Vanderberghe, 2004 ). From these definitions, and taking into account that if h = min { f, g} , the level set of h is the union of the level sets of f and g , we have: Lemma 9. H + ij (η) = G + ,a ij (η) ∪ G + ,b ij (η) , and H − ij (η) = G −,a ij (η) ∪ G −,b ij (η) Consequently, both H + ij (η) and H − ij (η) are the union of two convex (but possibility not disjoint) sets. The following example shows that G + ,a ij (η) ∩ G + ,b ij (η)  = ∅ , for some η-values, with η< || A i −A j || . In Fig. 4 , we have || A i −A j || =√ 409 2 ≃ 10 . 11 . Fig. 6 (a) displays, for α= 0 . 4 and η= 10 , the boundaries of the sublevel sets G + ,a ij (η) and G + ,b ij (η) . It can be observed that the intersection of both sets is not empty. Proposition 10. For any 0 ≤η< || A i −A j || , H+ ij (η) ∩ H − ij (η) = ∅ , i.e., if there exists a path from A i to A j with length shorter than the Euclidean (planar) travel distance, then the order in which X 1 and X 2 are passed is uniquely determined. ab c Fig. 6. (a): For  d ij = 10 , curves G + ,a ij , G + ,b ij , and set Q + (i, j) = G + ,a ij ∩ G + ,b ij . (b): Set P((i, j) , (k, r)) , for  d kr = 10 . 5 . (c): Vertex (X  1 , X  2 ) in the boundary of a region R . Proof. Let 0 < η<  A i −A j  and assume H + ij (η) ∩ H − ij (η)  = ∅ . Then there exists ( X 1 , X 2 ) such that  A i −X 1  + αd(X 1 , X 2 ) +  A j −X 2  ≤η  A i −X 2  + αd(X 1 , X 2 ) +  A j −X 1  ≤η. Summing up and using that d ( X 1 , X 2 ) ≥0 we obtain that  A i −X 1  +  A j −X 1  +  A i −X 2  +  A j −X 2  ≤2 η. Due to the triangle inequality, we have that  A i −A j  ≤ A i − X k  +  A j −X k  for k = 1 , 2 . This gives us 2  A i −A j  ≤ A i −X 1  +  A j −X 1  +  A i −X 2  +  A j −X 2  ≤2 η, a contradiction to the assumption that η<  A i −A j  .  Let { L p , L q } be antipodal to each other. For a given point ( X 1 , X 2 ) ∈ L p ×L q , the objective value F (X 1 , X 2 ) =  (i,j) ∈ C(X 1 ,X 2 ) t ij quantifies the amount of weights of OD-pairs captured by such a point. Taking into account Definition 1 , let H ij be the set of points which cover the OD-pair ( i , j ), given by H ij = { (X 1 , X 2 ) ∈ L p ×L q : f ij (X 1 , X 2 ) ≤ d ij } . The following result follows directly from the definition Corollary 11. ( X 1 , X 2 ) ∈ H ij if and only if ( i , j ) ∈ C ( X 1 , X 2 ) . In order to obtain H ij from the above defined sublevel sets, we replace the η-values by the specific acceptance level  d ij associated with each OD-pair ( i , j ). Remark 12 (Notation) . Given an acceptance level 0 ≤ d ij < || A i − A j || 2 , for t ∈ { a , b } let us denote G + ,t ij (  d ij ) and G −,t ij (  d ij ) by G + ,t ij and G −,t ij , respectively. This abbreviated notation is also applied to the sets H + ij (  d ij ) and H − ij (  d ij ) , which will be identified by H + ij and H − ij, respectively. Corollary 13. For each OD-pair ( i , j ), H ij = H+ ij ∪ H − ij = G + ,a ij ∪ G + ,b ij ∪ G −,a ij ∪ G −,b ij . Proof. Since f ij (X 1 , X 2 ) = min { h+ ij (X 1 , X 2 ) , h− ij (X 1 , X 2 ) } = f ji (X 1 , X 2 ) , the result follows from Lemma 9 .  5.1.2. Identifying a finite dominating set We now briefly comment on the role of H ij in the construction of a Finite Dominating Set (FDS). Recall that C(X 1 , X 2 ) = { (i, j) , . . . , (k, r) } is the set of OD-pairs covered by ( X 1 , X 2 ). Corollary 11 implies that (X 1 , X 2 ) ∈ H ij ∩ . . . ∩ H kr . For this reason, we next analyze the intersections of these sets, since such intersections will provide the points to be incorporated in the FDS, as we will see in the following. In fact, due to the absence of convexity of both H + ij and H − ij, we will focus the effort on selecting points from the boundaries of all these sets (as well as from their intersections), in order to guarantee that the selected points belong to all sets involved in the intersection. Henceforth we will use the notation G (or H ), to identify the boundary or level curve of a set G (or H ). That is, for t ∈ { a , b }, we have G + ,t ij = { (X 1 , X 2 ) ∈ L p ×L q : g + ,t ij (X 1 , X 2 ) =  d ij } H + ij = { (X 1 , X 2 ) ∈ L p , L q : h+ ij (X 1 , X 2 ) =  d ij } , and analogously for G −,t ij and H − ij . Clearly, for τ∈ { + , −} , H τ ij ⊆ G τ,a ij ∪ G τ,b ij , and H τ ij = G τ,a ij ∪ G τ,b ij if the set G τ,a ij ∩ G τ,b ij contains at most one point. Likewise H ij = { (X 1 , X 2 ) ∈ L p ×L q : f ij (X 1 , X 2 ) =  d ij } . Since from Proposition 10 , H + ij ∩ H − ij = ∅ , we trivially conclude Corollary 14. H ij = H + ij ∪ H − ij . As we have already seen, in order to construct the FDS of problem (2-TCR) (1), we will successively select several feasible points from these level curves and their intersections. Lemma 15. Given two different OD-pairs ( i , j ), ( k , r ), let P((i, j) , (k, r)) ⊂L p ×L q be the set of intersection points defined as follows: P((i, j) , (k, r)) =  ( G τ,t ij ∩ G τ ,t  kr ) , τ, τ ∈ { + , −} , t, t  ∈ { a, b}. Then, H ij ∩ H kr ⊆P((i, j) , (k, r)) . Proof. H ij = H + ij ∪ H − ij ⊆( G + ,a ij ∪ G + ,b ij ) ∪ ( G −,a ij ∪ G −,b ij ) , and a similar inclusion can be obtained for H kr . Therefore we can write H ij ∩ H kr ⊆G + ,a ij ∪ G + ,b ij ∪ G −,a ij ∪ G −,b ij   G + ,a kr ∪ G + ,b kr ∪ G −,a kr ∪ G −,b kr . Clearly, P((i, j) , (k, r)) is the right-hand side of this expression since P((i, j) , (k, r)) is obtained by intersecting each set of the first group with each set of the second group. This concludes the proof.  Definition 16. For each OD-pair ( i , j ), let Q (i, j) = Q + (i, j) ∪ Q −(i, j) be a set of feasible points of H ij = H + ij ∪ H − ij , where for each τ∈ { + , −} : Q τ(i, j) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ G τ,a ij ∩ G τ,b ij ,if this intersection contains at least one feasible point. { X a , X b } , otherwise, where the points X a and X b are arbitrarily selected from G τ,a ij , G τ,b ij , respectively. Clearly Q τ(i, j) ⊂H τ ij , for τ∈ { + , −} . Fig. 6 (a) and (b) shows some of these sets. Fig. 6 is based on the network of Fig. 4 , with α= 0 . 4 . We have considered the points A i (2.5, 6), A j (1 , −4) , A k (−2 , −4 . 5) and A r (3, 5.5). For  d ij = 10 and  d kr = 10 . 5 , Fig. 6 (a) shows the curves G + ,a ij and G + ,b ij , as well as the corresponding set Q (i, j) = G + ,a ij ∩ G + ,b ij containing two intersection points (in this case H − ij = ∅ ). Likewise, Fig. 6 (b) displays the set of intersection points P((i, j) , (k, r)) containing three points. In this figure only a branch of the curve G −,a kr is inside the feasible domain. Theorem 17. For the concave restricted problem (2-TCR) (1), let Q and Pbe the sets defined as follows Q =  (i,j) Q (i, j) , P =  (i,j)  =(k,r) P((i, j) , (k, r)) Then, for any arbitrary point X pq ∈ L p ×L q , the set = Q ∪ P ∪ { X pq } is an FDS for the problem (2-TCR) (1) Proof. Let G =  (i,j) { G τ,t ij , τ∈ { + , −} , t ∈ { a, b}} ⊂L p ×L q be the collection of all level curves of the restricted problem (2-TCR) (1). From both Definition 8 and subsequent results, the collection Ginduces a partition of the feasible domain L p ×L q into a set of regions { R s , s ∈ I } (where I is an index set), such that both F ( X 1 , X 2 ) and C ( X 1 , X 2 ) are constant in the interior points of each region (see Fig. 6 (c)). The possible changes in the objective function may only occur at the points on the boundary of each region. Therefore an FDS for problem (2-TCR) (1) can be constructed by selecting points from the set of boundaries { R s , s ∈ I} . Given a region R ∈ , we analyze the cases R = L p ×L q and R ⊂L p ×L q . 1. If R = L p ×L q , then G = ∅ . Hence, F ( X 1 , X 2 ), C ( X 1 , X 2 ) are constant, for all ( X 1 , X 2 ) ∈ L p ×L q . Equivalently, any point X pq = (X 1 , X 2 ) ∈ L p ×L q is optimal. 2. Otherwise, R ⊂L p ×L q , and its boundary R contains a set of edges: pieces of level curves, and possibly some vertex which is a point shared by (at least) two different level curves ( Fig. 6 (c)). All points of an edge obtained from the level curve G τ,t ij ∈ Gcover the OD-pair ( i , j ). Therefore, given a set of edges incident to a vertex, such a vertex covers all OD-pairs associated with these edges. In other words: if (X  1 , X  2 ) is a vertex, then F (X  1 , X  2 ) ≥F (X 1 , X 2 ) , for any point ( X 1 , X 2 ) of each edge incident to (X  1 , X  2 ) . From this argument, all vertices of the partition are selected to be incorporated to the FDS. Additionally, if there is some R s with none vertex, then R s contains a single level curve, in which case an arbitrary point of such a curve is also added to the FDS. In the following we prove that the FDS thus constructed is the set . In effect, a vertex (X  1 , X  2 ) of R is the intersection point of (at least) two level curves, and these curves can be obtained either from a single OD-pair ( i , j ) or from (at least) two OD-pairs ( i , j ), ( k , r ). (a) In the first case, Lemma 9 and Proposition 10 imply that (X  1 , X  2 ) ∈ G τ,a ij ∩ G τ,b ij . From Definition 16 , this intersection is the set Q τ(i, j) . (b) Let assume two edges associated with the OD-pairs ( i , j ) and ( k , r ) are incident to (X  1 , X  2 ) . This means that (X  1 , X  2 ) is obtained from the intersection G τ,t ij ∩ G τ ,t kr , for some τ, τ ∈ { + , −} and t , t  ∈ { a , b }, which implies that it belongs to the set P((i, j) , (k, r)) . Steps (a) y (b) are repeated with each vertex of the partition . At the end of this process, all vertices of the case (b) are the set P. On the other hand, an arbitrary point is selected from each R s without vertices: these arbitrary points, together with all vertices of the case (a), are the set Q . Finally, the arbitrary point X pq may be selected as one of points previously selected (in fact, X pq is necessary only if G = ∅ ). This concludes the proof.  5.2. The convex case This problem, identified by (2-TCR) (2), is formulated by adding the assumption that { L p , L q } are not antipodal to each other to problem (2-TCR) . In this case, when ( X 1 , X 2 ) ∈ L p ×L q , from Lemma 7 and the subsequent reasoning, the distance d ( X 1 , X 2 ) is convex. More specifically, we have d a ((X 1 , X 2 ) = d b (X 1 , X 2 ) = d(X 1 , X 2 ) . Consequently, all results of the previous section are valid for (2- TCR) (2) taking into account that we now have: H + ij = G + ,a ij = G + ,b ij , and H − ij = G −,a ij = G −,b ij . Therefore, from Proposition 10 and Corollary 13 , both H + ij and H − ij are convex and disjoint sets such that H ij = H+ ij ∪ H − ij. Likewise, for this problem the set Q (i, j) of Definition 16 becomes the set Q (i, j) = { X + , X −} , where X + = (X + 1 , X + 2 ) and X −= (X − 1 , X − 2 ) are points arbitrarily selected from H + ij and H − ij , respectively. And for each two different OD-pairs ( i , j ), ( k , r ), the set P((i, j) , (k, r)) of Lemma 15 is now given by P((i, j) , (k, r)) =  (i,j)  =(k,r) ( H ij ∩ H kr ) = { H + ij ∩ H + kr } ∪ { H + ij ∩ H − kr} ∪{ H − ij ∩ H + kr } ∪ { H − ij ∩ H − kr } . With these sets, Theorem 17 remains valid and establishes that = Q ∪ P ∪ { X pq } is a FDS for this problem. Finally, since C V is a constant set, it follows straightforwardly: Corollary 18. Let us consider that there exists a set of stations located on the nodes of the network. Then, is also a FDS for the problem in which the set C V is excluded: max (X 1 ,X 2 ) ∈ L p ×L q F (X 1 , X 2 ) :=  (i,j) ∈ C(X 1 ,X 2 ) \ C V t ij . 5.3. Example This example, based on the network of Fig. 4 , illustrates the above procedure. The existing demand is located at the points: A 1 (2.5, 6), A 2 (3, 5.5), A 3 (5 . 5 , √ 6 / 10) , A 4 (2 , −4 . 5) , and A 5 (1 , −4) . The partition of the network originated by the set of linear arc segments L = { L p , p = 1 , . . . , 8 } provides 36 different restricted problems on the pairs {{ L p , L q }, p = 1 , . . . , 7 , q = p + 1 , . . . , 8 } ∪ {{ L p , L p } , p = 1 , . . . , 8 } , (the pairs { L p , L q } and { L q , L p } give rise to symmetric restricted problems with the same solution). Among all these pairs, { L 2 , L 6 }, { L 1 , L 5 } and { L 3 , L 7 } are antipodal to each other, and the remaining pairs are not. Fig. 7. Left: Collection Gand partition for the concave restricted problem on { L 2 , L 6 }, and points of the FDS . Right: FDS for the subproblem (1) on { L 2 , V ( L 6 )}. We consider α= 0 . 4 . The matrices T = (t ij ) and  D = (  d ij ) containing the weights and the acceptance levels for all OD-pairs, respectively, are given by T = ⎛ ⎜ ⎜ ⎝ 0 30 15 28 14 16 0 32 45 23 40 25 0 20 20 28 45 26 0 30 14 20 23 30 0 ⎞ ⎟ ⎟ ⎠  D =⎛ ⎜ ⎜ ⎝ 0 0 . 5 6 10 . 2 10 0 . 5 0 5 9 . 2 8 . 5 6 5 0 5 . 5 5 10 . 2 9 . 2 5 . 5 0 1 10 8 . 5 5 1 0 ⎞ ⎟ ⎟ ⎠ With this scenario we first have considered the concave restricted problem: max (X 1 ,X 2 ) ∈ L 2 ×L 6 F (X 1 , X 2 ) :=  (i,j) ∈ C(X 1 ,X 2 ) t ij Note that for ( X 1 , X 2 ) ∈ L 2 ×L 6 , X 1 = (x 1 , 0) ∈ L 2 and X 2 = (x 2 , 2 √ 6 ) ∈ L 6 , therefore each point ( X 1 , X 2 ) ∈ is identified as x = (x 1 , x 2 ) . With this notation, x k = (x k 1 , x k 2 ) denotes the k th local solution (X k 1 , X k 2 ) of this subproblem (if any). Fig. 7 (left) shows the FDS , constructed from all vertices of the partition . The local solution for this subproblem is reached at both x 1 = (4 . 556013 , 2 . 90379) and x 2 = (4 . 776812 , 2 . 950328) , with x 1 ∈ P((2 , 3) , (2 , 4)) and x 2 ∈ P((1 , 5) , (2 , 4)) . For these points, the pairs covered and the objective value are (1, 3), (1, 4), (1, 5), (2, 3), (2, 4) and 286, respectively. The following objective values (in decreasing order) are obtained from the convex restricted problems on { L 3 , L 6 } and { L 1 , L 6 }. Let F ∗ p,q be the optimum objective value of the restricted problem (2-TCR) . Table 1 summarizes the results of the above three subproblems. The local solutions of the remaining restricted problems provide substantially lower objective values, and they have not been included in this table. The solutions obtained from the restricted problem on { L 2 , L 6 } are also global solutions for the 2-transfer problem on the over- Table 1 Best optimum values for the 2-transfer problem. Restricted problem Local solutions C ( X 1 , X 2 )F ∗ p,q { L 2 , L 6 }x 1 = (4 . 556013 , 2 . 90379) (1, 3), (1, 4), (1, 5), (2, 3), (2, 4) 286 x 2 = (4 . 776812 , 2 . 950328) { L 3 , L 6 }x 3 = (5 . 1 , 3 . 075407) (1, 3), (1, 4), (2, 3), (2, 4) 258 { L 1 , L 6 }x 4 = (0 , 2 . 2126927) (1,4), (1,5), (2,4), (2,5) 217 x 5 = (0 , 3 . 1439062) all network. The global optimum is F ∗= F ∗ 2 , 6 = F (X ∗ 1 , X ∗ 2 ) = 286 , for (X ∗ 1 , X ∗ 2 ) ∈ { (X k 1 , X k 2 ) , k = 1 , 2 } . 6. The case of locating a single transfer point The above procedure also solves the case of locating one transfer point. In effect, as we have argued at the beginning of this paper, the formulation of the 1-transfer additional covering problem (1-TAC) is made under the hypothesis that all nodes of V (or a subset of them) are already located transfer points. From this assumption, problem (1-TAC) can also be solved by adapting the procedure described for the 2-transfer restricted problem (2-TCR) to a set of subproblems dealing with the restriction of problem (1- TAC) to each linear arc segment L p ∈ L . The 1-transfer problem (1-TAC) can be reformulated as follows: max L p ∈L max X∈ L p F V (X ) :=  (i,j) ∈ C(X) \ C V t ij =  (i,j) ∈ X 2 ∈ V C(X,X 2 ) \ C V t ij where we have applied that C(X) =  X 2 ∈ V C(X, X 2 ) . The restriction of (1-TAC) to L p ∈ L is: max X∈ L p F V (X ) :=  (i,j) ∈ X 2 ∈ V C(X,X 2 ) \ C V t ij (1-TACR)