Analysis of the Parameters of Transfers in Rapid Transit Network Design

Analysis of the Parameters of Transfers in Rapid Transit Network Design Ricardo Garc´ıa1, Armando Garz´on-Astolfi2, Angel Mar´ın3, Juan A. Mesa4, and Francisco A. Ortega5 1Departamento de Matem´atica. Universidad de Castilla La Mancha. Ciudad Real, Spain [email protected] 2Departamento de Matem´atica Aplicada I. Universidad de Sevilla. Sevilla, Spain agastol[email protected]s 3Departamento de Matem´atica Aplicada y Estad´ıstica. Universidad Polit´ecnica de Madrid. Madrid, Spain [email protected] 4Departamento de Matem´atica Aplicada II. Universidad de Sevilla. Sevilla, Spain [email protected] 5Departamento de Matem´atica Aplicada I. Universidad de Sevilla. Sevilla, Spain [email protected] Abstract. The rapid transit network design problem consists of the location of train alignments and stations in an urban traffic context. The originality of our study is to incorporate into the location model the decisions about the transportation mode and the route, to be chosen for urban trips. This paper proposes a new design model which includes transfers between train lines. The objective of the model is to maximize the number of expected users in the transit network taking limited budgets into consideration, in addition to location and allocation constraints. Furthermore, the transfer costs are considered in the generalized public costs when the users change lines. Waiting time to take the metro and walking time to transfer is included in the formulation of the costs. The analysis of transfer parameters is carried out using a test network. Some computational experience is included in the paper. 1 Introduction Increasing mobility caused by the growth of cities is the reason why new lines of rail transit have been constructed. A crucial part of the network design process consists of the location of stations and alignments between them. In the paper [1] an approach to the network design problem, based on the previous selection of the key nodes (those providing a high number of trips) was described. Therefore, the transit network is defined on the edges which connect the key node set. The transit system involves the node and edge locations at upper level and considers the user traffic behavior at lower level. At upper level the main factor ATMOS 2005 5th Workshop on Algorithmic Methods and Models for Optimization of Railways http://drops.dagstuhl.de/opus/volltexte/2006/658 to consider is maximum coverage of the demand using public mode, taking constraints of our model and the budget constraints into account. Traffic demand leads to alternative configurations of networks, comparing private trip cost with public trip cost, the latter depending on previous location decisions. Customers choose the most convenient routes and modes in order to carry out their trips. A decisive factor for attracting passengers to the public mode is to offer direct trips without transfers. Transferring is annoying and it is undesirable for customers. In our approach, transfers are explicitly considered in accordance with the central role played by user mentality. The previous references to the rapid transit network design (RTND), [2],[3], [4], [5], [6], [7] consider travel cost as the time spent in travelling without taking into account any transfer cost. The layout of the paper is as follows. In Section 2 the RTND is formulated including transfers between lines. In Section 3 the transfer costs are consistently introduced into the previous model. In Section 4 a transfer parametric analysis is implemented. The paper finalizes with conclusions and further research. 2 Rapid Transit Network Design Model with transfers We assume that a set N={i:i= 1,...,I}of potential locations for the stations is given. Let Ebe the set of feasible edges linking the potential stations. Thus, we have an undirected graph G= (N, E) from which the transit network is going to be designed. For each node i∈N, let N(i) denote the set of nodes adjacent to it. A matrix of distances D= (dij ) between pairs of points of Nis also known. The travel patterns are given by the origin-destination matrix G= (gp), where gpis the demand of the pair p= (q, r)∈Pand Pis the set of pairs of demand. The cost structure is as follows. Let cij and cidenote the cost of constructing a section of an alignment on edge ij and that of constructing a station at node i, respectively. According to the available budget the length of the public lines will be bounded; for this purpose, there are bounds lengthl min,lengthl max,l= 1,...,L, on the length of line land bounds T lengthmin and T lengthmax on the total length of the lines of the network. In regard to the demand, let ucP UB pbe the user’s generalized cost of travelling within the constructed transit network and let ucP RIV pbe the user’s generalized cost using the private mode. Observe that this cost does not depend on the final topology of the transit network. The problem we are dealing with consists of choosing a number of lines L={l:l= 1,...,L}covering as much as possible travel demand between the points of N, subject to the line length constraints and other constraints. The decision variables are defined as follows: •The station selection variables: yl i= 1, if station iof line lis constructed; and yl i= 0 otherwise. •The edge selection variables: xl ij = 1,if edge ij of the line lis constructed; and xl ij = 0 otherwise. 2 •The following variables are defined for indicating whether or not the demand would use the transit network in case edge ij is selected. Specifically, up ij = 1,if the demand of pair pwould use edge ij in the public network, up ij = 0 otherwise. •Mode choice variables: zp= 1 if the generalized cost for the demand of pair pwithin the public network Ais less than that of the private mode; zp= 0 otherwise. •Flow routing variables: wpl ij = 1 if the demand ptraverses the edge ij using line l, 0 otherwise. •Transfer variables: vpl i= 1 if demand ptransfers to line lin station i. The RTND model with transfers is stated in the following terms: •Objective function: Trip coverage max Pp∈Pgpzp •Length constraints Pij∈Edij xl ij ∈[lengthl min,lengthl max], l ∈ L (1) Pl∈L Pij∈Edij xl ij ∈[Tlengthmin,Tlengthmax] (2) •Alignment location constraints Pj∈N(ol)xl olj= 1, l ∈ L (3) Pi∈N(dl)xl idl= 1, l ∈ L (4) yl ol=yl dl= 1, l ∈ L (5) Pj∈N(i)xl ij = 2yl i, i ∈N\ {ol, dl}, l ∈ L (6) xl ij =xl ji ij ∈E, l ∈ L (7) •Routing demand constraints Pj∈N(q)up qj = 1, p = (q, r)∈P(8) Pi∈N(q)up iq = 0, p = (q, r)∈P(9) Pi∈N(r)up ir = 1, p = (q, r)∈P(10) Pj∈N(r)up rj = 0, p = (q, r)∈P(11) Pi∈N(j)up ij −Pk∈N(j)up jk = 0, j ∈N\ {q, r}, p = (q, r)∈P(12) •Location-Allocation constraints up ij +zp−1≤PL l=1 xl ij , , ij ∈, p = (q, r)∈P(13) •Splitting demand constraints ucP UB p−ucP RIV p−M(1 −zp)≤0p= (q, r)∈P(14) where ucP RI pis a data and ucP UB pwill be defined in the next subsection. M is an enough big number. 3 •Transfer constraints wpl ij ≤xl ij , ij ∈E, p = (q, r)∈P, l = 1,...,L (15) up ij +zp−1≤PL l=1 wpl ij , p = (q, r)∈P, ij ∈E(16) up ij −zp+ 1 ≥PL l=1 wpl ij , p = (q, r)∈P, ij ∈E(17) Pij∈E,l∈L wpl ij ≤M zp, p = (q, r)∈P(18) Pj∈N(i)wpl ij −Pj∈N(i)wpl ji ≥2vpl i−1, i ∈N\ {r}, p= (q, r)∈P, l ∈ L (19) Pj∈N(i)wpl ij −Pj∈N(i)wpl ji ≤2vpl i, i ∈N\ {r}, p= (q, r)∈P, l ∈ L (20) xl ij , yl i, up ij, zp, wpl ij , vpl i∈ {0,1}. Constraints (1) and (2) impose lower and upper bounds on the individual and total line lengths. Constraints (3) and (4) guarantee that each line starts and ends at its specified origin and destination. Constraints (5) ensure that all the origins and destinations belong to A.Constraints (6) impose that each line must be a path between the corresponding origin and destination. Constraints (7), (8) and (9) guarantee demand conservation. Constraints (10) and (11) were introduced to ensure that identity zp= 1 implies that the demand of the pair pgoes through the public network and zp= 0 if it uses the private network. Constraints (12) guarantee that the demand is routed on an edge only if this edge belongs to the public system. Constraints (13) ensure that the demand is routed on an edge if it has been previously constructed. Constraints (14) force the demand to be assigned to public mode if public cost is less than private cost. Note that this formulation does not include the common sub-tour elimination constraints. Therefore, when a solution contains a cycle, additional constraints can be imposed in order to avoid the presence of cycles in the solution network. Note that well developed networks (e.g. Paris, London, Moscow, Tokyo and Madrid) often contain circular lines. It has also been proved by Laporte, Mesa and Ortega (1997, [?]) that the inclusion of a circle line increases the effectiveness of the network and thus the inclusion of cycles can be interesting. Transfer constraints (15) permit the flow to use edge ij of line lonly if edge ij have already been established for public mode. Constraints (16) guarantee that if the flow of edge ij is carried through any line, the public mode and its flow at edge ij must already be chosen. Constraints (17) establish that any flow for the pair pcan use any edge of the public network. Constraints (18) impose that if a transfer is made at node ithen the flow leaving from this node is bigger than the flow coming in. Constraints (19) and (20) impose that if the flow leaving out is less than the flow coming in at a node i, then a transfer is made at this node. 4 3 Transit costs in transfers Time spent in transference between lines is characterized by certain cost parameters. We have studied different values of the parameters which define transfer cost in order to conclude how they influence the RTND solution. The paper is focused on the study of the increase in the cost using the public mode, assuming that users may transfer from one line to another. The transfer process has been modeled at RTND through constraints (15) to (20), but now we will give details about how the public mode cost is influenced by transfers. The public cost for each demand ucP UB pis the sum of two terms: one term relative to travel time spent moving in the transit vehicle on the rapid transit network and another term related to the transfer time spent in transferring from one line to another. The first term has been considered in all the references, and it is computed by the traveling time, which is calculated by the sum of the travel distance divided by the average velocity of the lines ˆ λ. Hence, non-transfer public costs (NTPUB) are defined as follows: ucNT P UB p=1 ˆ λPij∈Edijup ij, p = (q, r)∈P(16) In the concept of vehicle velocity, we include vehicle moving time and the time spent at the station required to permit boarding and alighting of the passengers. These values are average values for standard lines. The line velocity may be considered by taking an average value of 20 kilometers per hour. In that case, the average velocity, ˆ λ, is 1/3 kilometers per minute. As was pointed out below, the demand is very sensible to transfer time. Thus, the transfer cost of each demand and station is considered as the sum of two terms: 1) one value fixed for each station i,uci, that represents the average walking time between line platforms and 2) another value on the waiting time for taking the next train of a different line. In our approach we assume ucias a parameter which depends on the travel time spent for any demand that transfers at station ifrom the previous board platform line up to the board platform of the next line. This value is given in minutes and it can model the cumulative sum of walking times between platforms and the annoyance associated to the transfers, which depends on the station characteristics. This value would be in average about 3 to 5 minutes. The transfer waiting cost depends on the frequency of the line of the train to take in order to continue the trip towards the destination. The line frequency is considered fixed and represents a parameter of the model. Considering that the planning period is of 1 hour, and that the time cost will be given in minutes, the wait time is assumed equal to one divided by twice the frequency of the line, 2 ∗fl. So if the average frequency is of 6 vehicle per hour then the average waiting time is of 5 minutes. For a line with double frequency, 12 vehicles per hour, the waiting time will be of 2.5 minutes. With these considerations, the public cost expression with transfer of a pair pis: 5 •UserPublic cost ucP UB p=1 ˆ λPij∈Edij up ij +Pi∈N\{r},l∈Liuci+1 2flvpl i p= (q, r)∈P(17) where Liis the set of lines that use the node i. In this context, for a distance of 3 kilometers and for an average velocity of 20 km/h, the travel time is 9 minutes. If the fixed transfer time is of 3 minutes more, and the wait time of 5 minutes, the total travel time is of 17 minutes. 4 Transfer parametric analysis The previous model has been tested on the 6-node network shown in Figure 1, where each node ihas an associated cost (variable ciin the model) and each edge has been weighted by means of a pair (cij , dij) its components respectively representing the cost of constructing edge ij and the generalized public cost of using edge ij to connect both nodes. 1 2 3 4 5 6 ( 2 ) ( 3 ) (2.2) ( 3 ) (2.5 ) ( 1.3 ) (3, 1.1) (2.4, 0.7) (1.9, 0.5) (2.8,0.8) (1.7, 0.5) (2.1,0.6) (2.6,1.1) (1.7, 0.5) (2.7,0.7) Fig. 1. Network considered. The origin-destination demands gp, p = (q, r)∈Pand the private cost ucP RIV pfor each demand pair p∈Pare given in the following matrices: G =         −9 26 19 13 12 11 −14 26 7 18 30 19 −30 24 8 21 9 11 −22 16 14 14 8 9 −20 26 1 22 24 13 −         ; 6 ucPRIV =         −1.6 0.8 2 2.6 2.5 2−0.9 1.2 1.5 2.5 1.5 1.4−1.3 0.9 2 1.921.9−1.8 2 3 1.5 2 2 −1.5 2.1 2.7 2.2 1 1.5−         Bounds on maximum and minimum lengths of the total public network have been established at 4 and 2, respectively. The solutions presented in the following scenarios have been obtained by using CPLEX 8.0 on a Pentium IV laptop computer at 2.56 Mghz, provided by 1 Gbyte of RAM. Although different parametric analyses can be carried out for the model, we have emphasized the sensitivity of the solutions with respect to the dispersion of values associated to transfer costs. Applying a calibration process to the public costs of the edges, the centralized value ucP UB ij = 0.685 was obtained. Taking this result into account, the value 0.75 was considered a central value. Different decrements and increments of size 0.25 have been used to grade the dispersion with respect to the average 0.75. Therefore, a variation of modulus 0.25 will be identified as low dispersion and if the difference with respect to the central value is 0.50, then we will say that the dispersion is high. 4.1 The effect of varying the transfer cost between lines on the configuration of the optimum network An average speed of 20 km/h has been assumed for transit on all lines. The cost for transferring was established at 3 min. Private cost was six times higher than public cost; this proportion stimulates a desirable competition between transportation modes. The congestion level has been assumed equal to 1.5 remaining outside of this first parametric analysis. The following tables show optimum configurations of the rapid transit networks for the constraints indicated; namely, the number of lines that will compose the final network and the range for the maximum length of each line. Each table deals with a different scenario: Table 1 : All transfer costs coincide in a central value (0.75). Table 2 : Low dispersion for the distribution of transfer costs in a 2-line network (0.5 and 1). Table 3 : Low dispersion for the distribution of transfer costs in a 3-line network (0.5, 0.75 and 1). Table 4 : High dispersion for the distribution of transfer costs in a 2-line network (0.25 and 1.25). Table 5 : High dispersion for the distribution of transfer costs in a 3-line network (0.25, 0.75 and 1.25). The analysis of the results lead us to the following conclusions: 7 Line Length Optimum Obj. Line Exec. Num. Range Lines Func. Lengths Time(s) 2[0.5,2.5] [0.5,2.5] n1-n2-n3-n4 n3-n5-n6-n4 444 2.2 1.757.7 3 [0.5,1.5] [0.5,1.5] [0.5,1.5] n3-n5-n6 n1-n3-n2 n3-n4 404 1 1.3 1.1 1666.72 Table 1. All transfer coefficients are equal to 0.75 Line Length Optimum Obj. Line Exec. Num. Range Lines Func. Lengths Time(s) 2[0.5,2.5] [0.5,2.5] n2-n1-n3-n5-n4 n5-n6-n4 456 2.5 1.295.23 2[0.5,3] [0.5,2.5] n1-n3-n5-n4-n6 n2-n3 470 2.7 0.650.5 2[0.5,3.5] [0.5,2.5] n2-n1-n3-n5-n4-n6 n2-n3 470 3.2 0.661.2 Table 2. Low dispersion of transfer coefficients (2 lines) 1. A wide range for the line lengths produces better values of the objective function. 2. When the dispersion of transfer cost increases (i.e., waiting time is very heterogeneous for all lines), the flow shift is higher. Subsequently, the best results for a 2-line network are obtained when the dispersion is low and, on the other hand, the objective function reaches higher values for the 3-line network when the dispersion is high. This fact does not alter although the range of the line lengths varies. 3. The required execution time descends when the dispersion of transfer costs and the range for line lengths increase, which behaves even better on the 3-line network, as the tables show. 4.2 The effect of varying the train frequency of the lines on the network configuration The following tables show optimum configurations of the rapid transit networks for the train frequency indicated. Table 6 : Low frequency of the train flow on the 2-line network. Table 7 : High frequency of the train flow on the 2-line network. 8 Line Length Optimum Obj. Line Exec. Num. Range Lines Func. Lengths Time(s) 3 [0.5,1.5] [0.5,1.5] [0.5,1.5] n1-n3-n2 n3-n5-n4 n3-n5-n6 425 1.3 1.3 1 1252.69 3 [0.5,2] [0.5,2] [0.5,1.5] n1-n3-n5-n4 n2-n3 n5-n6-n4 470 2 1.2 0.6 248.61 3 [0.5,2.5] [0.5,2.5] [0.5,1.5] n1-n3-n5-n4 n5-n6-n4 n2-n3 470 2 1.2 0.6 248.61 3 [0.5,3] [0.5,2.5] [0.5,1.5] n1-n3-n5-n4-n6 n2-n3 n1-n2 470 2.7 0.6 0.5 173.64 Table 3. Low dispersion of transfer coefficients (3 lines) Line Length Optimum Obj. Line Exec. Num. Range Lines Func. Lengths Time(s) 2[0.5,2.5] [0.5,2.5] n1-n3-n5-n6-n4 n2-n3 447 2.4 0.664.63 2[0.5,3] [0.5,2.5] n2-n1-n3-n5-n6-n4 n2-n4 456 2.9 1.146.81 2[0.5,3.5] [0.5,2.5] n1-n3-n5-n4-n6 n2-n3 456 2.7 0.638.81 Table 4. High dispersion of transfer coefficients (2 lines) 4.3 The effect of varying the train frequency on the remainder parameter set Table 8 contains the results obtained for a 3-line network whose congestion level is 5, range for line lengths is [0,2.5] and total network length is less than 5. Moreover, the maximum value for the objective function is 496 (the total demand) and λ= 0.33. The main aim of this subsection consists of showing how the solution varies when the line frequency increases. For this purpose, the first column of Table 8 collects an increasing sequence of values for the frequency while the remainder columns show the associated values in relation to the objective function, the total length and the execution time. As can be noted, when frequency increases, the waiting time for riderships decreases and, subsequently, the use of public network increases (as shows the sequence of values corresponding to the objective function). In relation to the total length of the lines, Table 8 shows, from a frequency greater than 6, how the system does not require a minimization of the location 9