Analyzing the theoretical capacity of railway networks with a radial-backbone topology

. Analyzing the theoretical capacity of railway networks with a radial-backbone topology Francisco A. Ortega Riejos Department of Applied Mathematics I, University of Seville, Spain Eva Barrena HEC and Interuniversity Research Center on Network Enterprise, Logistics and Transportation (CIRRELT), Canada J. David Canca Ortiz Department of Industrial Engineering and Management Science, University of Sevilla, Spain Gilbert Laporte HEC and Interuniversity Research Center on Network Enterprise, Logistics and Transportation (CIRRELT), Canada ABSTRACT In this work we propose a mechanism to optimize the capacity of the main corridor within a railway network with a radial-backbone or X-tree structure. The radial-backbone (or X- tree) structure is composed of two types of lines: the primary lines that travel exclusively on the common backbone (main corridor) and radial lines which, starting from the common backbone, branch out to individual locations. We define possible line configurations as binary strings and propose operators on them for their analysis, yielding an effective algorithm for generating an optimal design and train frequencies. We test our algorithm on real data for the high speed line Madrid-Seville. A frequency plan consistent with the optimal capacity is then proposed in order to eliminate the number of transfers between lines as well as to minimize the network fleet size, determining the minimum number of vehicles needed to serve all travel demand at maximum occupancy. . 1. INTRODUCTION Railway capacity refers to the allocation of resources (tracks and vehicles) to achieve a certain quality of service, defining a tradeoff between operators and passengers service level. The set of actions that enable increasing the capacity of railway infrastructures can be classified into two main groups: actions on the infrastructure, which belong to the context of long-term measures and usually require large initial investments, and actions on the operations, which are economically cheaper and applied in the short and medium term horizon. In the latter group, there exist simple strategies to increase the railway lines capacity, such as speed homogenization, traffic management, selection of stops (Lee, 2012, Freyss et al. 2013), acceleration strategies (Canca et al., 2014), and the use of alternative routes. None of these requires financial investments as large as splitting existing tracks. The radial-backbone (or X-tree) topology is one of the most widely used network schemes in conventional railways and tramways in urban transportation networks (Laporte et al., 1994). On a radial-backbone platform, vehicles belonging to two types of lines can travel: those that travel exclusively on the main corridor (primary or backbone lines) and those that, starting from the common backbone, branch out to individual locations (radial lines). The proliferation of the radial lines without adequate planning can inefficiently saturate the capacity of the railway infrastructure. In practical terms, the main lines canalize main services that are complemented by shuttle services provided by the radial lines (Musso & Vuchic, 1988). Thus, the stations located in the central segment of the corridor can be served by radial and backbone lines, while the stations in the branches can only be served by the radial lines. Based on this hierarchical structure, we propose a general mechanism to optimize the capacity of the backbone corridor within an X-tree structure by determining the line design and optimal frequencies in order to serve the whole demand while eliminating transfers between lines. The transport capacity of a rail corridor is a complex, loosely defined concept having multiple meanings. In fact, the International Union of Railways (UIC, 2004) states that the railway capacity is not a concept that can be clearly determined, but that depends on the way in which the railway infrastructure is used. Nevertheless, based on the proposal of Krueger (1999), the railway capacity can be defined as a measure of the ability to move a certain traffic volume along a line over a period of time, with a given set of resources, and a specific service plan. The objective sought when quantifying the capacity of a railway corridor is to achieve an optimal use of the involved resources, scheduling train services according the available capacity. The capacity of a railway line depends primarily on its physical characteristics (number of railways, number of stations, the existence of auxiliary lines and sidings (Kendra et al., 2012; Harrod, 2009), and on the signaling systems (Goverde et al., 2013). See Dicembre & Ricci (2011) for a study on the correlation between capacity, block sections length, types of services and timetables for high density lines. Other important factors are composition, the different running speeds, and the priorities for certain services on the infrastructure use. Abril et al. (2008) mention the existence of four types of railway capacity: . a. Theoretical capacity: Maximum number of trains that could be used by a railway line in ideal conditions during a given time period. b.Practical capacity: Traffic flow that can be offered under normal operating conditions, driving on the railway line with an acceptable level of reliability. This typically corresponds to between 60% and 75% of the theoretical capacity since it depends on the priorities established among different kinds of trains, and on the traffic clustering. c. Used capacity: Effective traffic flow that is canalized through the line (usually less than the one established by the practical capacity). d.Available Capacity: Difference between the practical and the used capacity. It quantifies additional traffic flow that could be introduced in a line. The different types of capacity measures are illustrated in Figure 1. Fig. 1 Types of capacity measures (Krueger, 1999) The factors that determine the capacity of a railway line can be grouped into those derivative of existing infrastructure, those attributable to traffic and those conditioned by the operation of the line. There exist various types of approaches that have led to methods for evaluating the capacity of a railway line. Among the most important techniques are analytical methods, simulation methods and optimization methods. a. Analytical methods: These are usually based on obtaining the theoretical capacity of a line by assuming that its train departures follow a certain probability distribution. Subsequently, the practical capacity is estimated by including regularity margins or by applying the correction percentages imposed by the different types of concurrent services. This general scheme is followed by Petersen & Taylor (1982), Martland (1982), Kraft (1988), Chen & Harker (1990), and Burdett & Kozan (2006). Recently Malavasia et al. (2014) analyzed and compared three synthetic methods for the evaluation of capacity of railway nodes. In general, analytical methods are useful for the calculation of railway capacity at a planning level, as well as for the identification of bottlenecks in the infrastructure. However, different methods may provide very different results when studying the same line since they are very sensitive to the parameters used and, in particular, to the variations in the composition of trains. . The International Union of Railways published a generic method for calculating the capacity of a railway line (UIC, 1983; UIC, 1996), which is based on the determination of the capacity of the line sections and on the identification of bottlenecks. It considers the order of trains and slack times in order to achieve a certain quality of service. This traditional analytical method yields the theoretical capacity for a reference period of T minutes, starting from the time of the average interval of minimum sequence sbetween consecutive trains, the safety time bneeded to avoid incidents, and the overtime protection or separation of trains E. From this expression, the practical capacity is calculated by multiplying the result by a factor typically in the range of 0.6 to 0.75: Ebs T C (1) Another analytical method for calculating the railway capacity is the one proposed by the American Association of Railways (AAR, 2007), which includes a correction factor that depends on the operating conditions. Let abe a constant that takes the value 2 for single line segments, Tbe the period of analysis in minutes, and let fbe a correction factor which takes the value of 0.9 on railway lines with automatic blocking and 0.8 under other operating conditions, and Mb be the maximum net module that represents the sum of the times without train stops at a certain section, plus the time required to perform the in and out operations at the stations: b M fTa C (2) Unlike the previous method, the analysis period Tis not fixed, but also includes the possibility of studying systems of single or double line by varying the parameter a, and in to take into account the type of locking mechanism of the line. In the denominator, Mbcan be interpreted as a parameter equivalent to the denominator s + b + E in Equation (1). b. Optimization methods: These are based on the design of saturated schedules and use mathematical programming models that achieve a high degree of saturation and simultaneously ensure certain level of quality of service (Canca et al., 2014). Different techniques have been used for this purpose: branch-and-bound (Szpigel, 1972; Jovanovic & Harker, 1991), heuristic algorithms (Cai & Goh, 1994; Carey & Lockwood, 1995), tabu search (Higgins et al., 1996), Lagragian relaxation (Caprara et al., 2000), and linear programming (Mussone & Wolfter Calvo, 2013). The optimization method recommended by the International Union of Railways (UIC, 2004) is based on the idea of saturated schedules. Starting from a panel of existing schedules, they propose to compress them up to the maximum, forcing trains to be as close as possible in time. Among the constraints to be considered during this process are the prohibition of travel times modifications and overtakings, and the possibility of forced stops due to the crossings. After completing the process of compacting schedules, the time horizon that remains available enables to quantify the additional services that could be scheduled. c. Simulation methods: These methods attempt to replicate the actual operation of trains within a line or a railway network. They are generally used in combination with the optimization methods in order to check whether the scheduled services resulting from an optimization exercise will involve operational difficulties in practice. In addition to works in the academic field about simulation models using railway capacity, such as those of Welch & Gussow (1986), Jovanovic & Harker (1991) and Kaas (1991), several . commercial software applications used as tools in the railway sector (MultiRail, OpenTrack, SIMONE, CAPRES, DEMIURGE, Recife, MOM, etc.) have been developed. These tools enable operation simulations and the generation of schedules in order to optimize the use of the capacity by means of the parameters relating to railway infrastructure. or the calculation of the railway network capacity. García-Álvarez (2011) identifies several topological designs that are usually used in railway networks, and highlights the radial-backbone topology (or X-tree) as one of the most widely used schemes for conventional railway network design (e.g., AVE networks South-Central and the recent connection of High Speed Railway Barcelona-Paris) and for tram networks in urban transportation (e.g., the metro of Porto or the metro of San Francisco). Figure 2 depicts the high-speed rail network in Spain (in bold) with a clearly defined radial-backbone pattern. Figure 3 shows the Metro map of San Francisco, which also follows a radial-backbone pattern. Fig. 2 High-speed rail network in Spain Source: http://www.adifaltavelocidad.es . Fig. 3 Metro map of San Francisco Source: http://www.sfmta.com On a platform corresponding to the main corridor, vehicles belonging to two types of lines may drive: those that run exclusively on the main corridor (backbone lines) and those that, starting from the common backbone, branch out to individual locations (radial lines). Then, the major congestion problems will occur in sections of the main corridor. The increment of radial services (or lines) sharing sections of the main corridor without an adequate planning process can clog the capacity of the rail infrastructure. This work focuses on railway networks with a radial-backbone topology where the main sections can have variable levels of use. We develop an analytical method that, applied to a railway corridor, determines the scheduling of vehicles required to serve 100% of the travel demand between the stations of the network, using the minimum number of vehicles at full capacity. The resulting line set and frequencies can be viewed as the implementation of the concept of practical capacity for a given origin-destination (OD) demand. Additionally, it takes into account the operator point of view since the number of kilometers of the fleet is minimized, and the users point of view, since it eliminates the need for transfers in order to reach destinations. The remainder of this work is organized as follows. In Section 2, we illustrate the problem using some examples. In Section 3, we propose a formulation associated to the analytical model, which enables us to develop an algorithm for the resolution of this problem. This algorithm is presented in Section 4. We present the results of a computational experiment for the case of the Madrid-Seville high speed railway in Section 5. Finally, Section 6 presents the conclusions of this work. 2. PROBLEM DESCRIPTION AND ILLUSTRATION Consider, as illustrated in Figure 4, a railway corridor where trains drive from left to right, with the possibility of stopping at stations 1 to 4, and whose sections lengths are 1, 2 and 2 . km respectively. Fig. 4 Example of a four-stations corridor In addition, let 60 12050 804020 g be an OD matrix between the four nodes of the corridor in the left to right direction. The existing travel demand will influence the passenger load on each of the corridor segments. The resulting number of demanded trips on each backbone section is depicted in Figure 5. Fig. 5 Origin-destination demand along the corridor The accumulation of this demand segment by segment determines the fleet needed to meet the travel demand (see Figure 6). Fig. 6 Cumulative origin-destination demand for each segment of the corridor Suppose that all trains have the same capacity (10 passengers) and a simple composition. In option 1 (Figure 7), the theoretically served demand is 100%, the fleet size in number of trains required is 29. Regarding the occupation of the vehicle, the horizontal load factor HLF is 73.31 % (ratio between numerator (140 +290 +260) and the denominator )3290( ). The vertical load factor VLF is 100%, corresponding to the section of higher occupancy (ratio 290/290). The load factor LF is 7331.0VLFHLF (Canca et al., 2014). Finally, the percentage of users who do not require transfers is 100%. . Fig. 7 Option 1: 29 long-distance trains In option 2 (Figure 8), the theoretically served demand is also 100%, the fleet size rises to 69 train units, the occupancy of the fleet reaches its peak of 100% (LF = 1). However, the percentage of users who do not require transfers decreases to 35.14%. In this case, 43.24% of the users ((40 +120) / 370) require one transfer, and 21.62% (80/370) require two transfers to reach their destination. Fig. 8 Option 2: 69 (14+29+26) short-distance trains In option 3 (Figure 9) the theoretically served demand is again 100%, the fleet is 29 trains units, and the occupancy of the fleet rises to 100% (LF = 1). The percentage of users who do not require transfers is 100%. Fig. 9 Option 3: 14 long-distance trains, 12 medium-distance trains and three short-distance trains The aim of this work is to develop a general methodology that will lead to intermediate solutions such as the one represented in option 3, which serves 100% of the travel demand and requires the minimum possible number of vehicles, used at full capacity and minimizing the need of transferring. . 3. FORMULATION ASSOCIATED TO THE ANALYTICAL MODEL Let n iiin xixxxxl 1 21 2;,1,0:,,, be the set of transit lines configurations that can be set along a linear corridor connecting nstations. The component i x of the chain n xxxl ,,, 21 takes the value 1 if the transit line is scheduled to stop at the station i, and 0, otherwise. We introduce two operators on each binary string in order to identify the first and last station of its associated transit line: ; . Besides, we define a sum operation on the binary strings: Definition 1 Let n xxxl ,,, 211 and n yyyl ,,, 212 be two binary strings. We define the sum as follows: n zzzll ,,, 2121 , where . otherwise; ][][ ][][ if;,max 21 12 ii ii i yx lLlFi lLlFi yx z Definition 2 Let 1 l and 2 l , we say that both strings are summable if 21 ll . Examples: 1) 0,1,1,1 1 l and 1,1,0,0 2 l are summable. In fact, 1,1,1,1 21 ll . 2) 0,0,1,1 1 l and 1,1,0,0 2 l are summable because 1,1,1,1 21 ll . Note that the resulting line generates a segment with no passenger traveling between the second and 3rd stations. 3) 1,0,0,1 1 l and 0,1,1,0 2 l are summable: 1,1,1,1 21 ll . The resulting line may lead to capacity problems, since it already had passengers before introducing the new stop. 4) 1,0,0,1 1 l and 0,0,1,1 2 l are summable: 1,0,1,1 21 ll . As in the previous case, the resulting line may also lead to capacity problems. 5) 1,0,0,1 1 l and 1,1,0,0 2 l are summable: 1,1,0,1 21 ll . Again, the resulting line may generate capacity problems. 6) 0,1,1,1 1 l and 1,1,1,0 2 l are not summable, since 1,2,2,1 21 ll . Proposition 1 (commutative property) Let 21 ,ll . If 21 ll , then 1221 llll . Proposition 2 (associative property) Let 321 ,, lll . If 21 ll and 32 ll simultaneously occur, then )()( 321321 llllll . . Transportation Research Forum, 29(1), 153 162. Krueger, H. (1999). Parametric Modelling in Rail Capacity Planning. In P. A. Farrington, H. B. Nembhard, D. T. Sturrock, & G. W. Evans (Eds.), Proceedings of the 1999 Winter Simulation Conference (P. A. Farrington, H. B. Nembhard, D. T. Sturrock, and G. W. Evans, eds), 2, 1194 2000. Laporte, G., Mesa, J. A., & Ortega, F. A. (1994). Assessing topological configurations for Rapid Transit Networks. Studies in Locational Analysis, 7, 105 129. Lee, Y.-J. (2012). Mathematical Modeling for Optimizing Skip-Stop Rail Transit Operation Strategy Using Genetic Algorithm. Baltimore, MD: Morgan State University. Department of Transportation and Urban Infrastructure Studies. Mussone, L. & Wolfter Calvo, R. (2013). An analytical approach to calculate the capacity of a railway system. European Journal of Operational Research, 228(1), 11 23. Malavasia, G., Molkováb, T., Riccia, S., & Rotolic, F. (2014). A synthetic approach to the evaluation of the carrying capacity of complex railway nodes. Journal of Rail Transport Planning & Management, 4(1 2), 28 42. Martland, C. D. (1982). PMAKE Analysis: Predicting Rail Yard Time Distributions Using Probabilistic Train Connection Standars. Transportation Science, 16(4), 476 506. Musso, A. And V.R. Vuchic (1988). Characteristics of Metro Networks and Methodology for their Evaluation. Transportation Research Record,1162, 22-33. Petersen, E. R., & Taylor, A. J. (1982). A Structured Model for Rail Line Simulation and Optimization. Transportation Science, 16(2), 192 206. Szpigel, B. (1972). Optimal train scheduling on a single track railway. Operations Research, 72, 343 352. UIC. (1983). Method to be Used for the Determination of the Capacity of Lines. UIC Leaflet 405-1. International Union of Railways. Paris. . UIC. (1996). Links between Railway Infrastructure Capacity and the Quality of Operations. UIC Leafletet 405 OR. International Union of Railways. Paris. UIC. (2004). Capacity. UIC Leaflet 406. International Union of Railways. Paris. Welch, N., & Gussow, J. (1986). Expansion of Canadian National Railways Line Capacity. Interfaces, 16(1), 51 64.