Some mathematical programming-based models for a simplified evaluation of the capacity of railway networks

Title: Some mathematical programming-based models for a simplified evaluation of the capacity of railway networks Author: Fernando E. García Muñoz Advisor: Esteve Codina Sancho Department: Statistics and Operations Research (UPC) University: Universitat Politècnica de Catalunya (UPC) / Universitat de Barcelona (UB) Academic year: 2017/2018 Interuniversity Master in Statistics and Operations Research UPC-UB Universitat Polit`ecnica de Catalunya Facultat de Matem`atiques i Estad´ıstica Master Thesis Some mathematical programming-based models for a simplified evaluation of the capacity of railway networks Fernando Garc´ıa Mu˜noz Advisor: Esteve Codina Statistics and Operations Research Department Doy las gracias a mi madre, padre y hermanos, por estar siempre apoy´andome desde la distancia en cada uno de los proyectos en que me he embarcado. Agradecer tambi´en, a mis amigos, Grace y Alejandro por hacer del m´aster una gran experiencia. Al Dr. Esteve Codina por guiarme y apoyarme durante todo el desarrollo del trabajo. Finalmente, dedico un agradecimiento especial a mi novia Mar, que ha sido mi compa˜nera ideal, en estos meses de trabajo. Abstract Keywords: Railway system, Capacity analysis MSC2000: 200090B10 The estimation of the available capacity in the rail networks is a truly relevant aspect that is part of decision processes both at an operational and strategic level of railway systems. The specific side conditions that are in force at any given moment can have a very strong impact in terms of the level of available capacity in a network. In a tactical decision-making environment, possibly many of these conditions can be well evaluated or known accurately. For example, a table of schedules for passenger services of different types can be known, which are the maintenance / inspection periods of the network and under these circumstances require an estimate of the maximum quantities of different types of circulations for freight trains. On the contrary, at different stages of the strategic process, such as the formation of new lines or the construction of new infrastructure, there may be a high level of uncertainty in relation to these additional factors, and even then an acceptable estimate of the capacity to accommodate services that the network can have, either for certain origin / destination relationships separately or working together in a certain scenario. In this master’s thesis, two similar models that have recently appeared in the literature aimed at establishing sets of constraints that incorporate basic variables of flow or number of circulations on elements of a railway network are analyzed and extended to the case of networks with a general configuration. The potential of these models consists of their ability to give estimates of maximum flows in the network taking into account only: a) their mutual interactions at specific points of the network, such as junctions or small stations, acting as the only ”deterrent factors” that can be the agent that limits such flows, b) basic principles of blockade of railway sections for safety reasons. Also, these proposed models provide capacity estimates following different methodologies that allow finding either a rank of the maximum capacity or a pointwise estimate value; a remarkable characteristic is that the congestion level that may be reached in the network is included as part of the modelling process. Both approaches are not based on a scheduling methodology and it does not consider delays due to stochasticity or coming from queueing theory to compute the occupation percentage, but the time that a train could remain stopped at a node due to blocking. The usefulness of the models that are the object of this master’s thesis lies in their apparent simplicity and in their possibility of being included in more complex mathematical programming models oriented mainly to planning, without substantially increasing their complexity. The approaches are tested in two networks of different size to study the influence of the operational conditions, dwell times, headway time and infrastructure over a railway system. Notation NNode set CPath set φSet of origins and/or destinations RSet of origin/destination pairs, where R={(p, q) : p, q ∈φ} ASet of Arcs, where A={(i, j) : i, j ∈N} KSet of train types GSet of passing loops FSet of passing loop arcs, F={(m, n) : m, n ∈G} DSet of arcs within passing loop, D={(i, j) : i, j ∈F} Ωr[i, j] Set of path r∈Ccrossing arc (i, j)∈A ξp,q[r] Path rthat goes from the origin pto destination q Si,j[r] Set of arcs (i, j)∈Athat use the path r∈C αk iTime in the node i for the train type k θk i,j Time to cross the arc (i, j) with the train type k ρk p,q Time to cross the path (p, q) with the train type k ϑk i,j Sum of dwell time at station iplus the time to cross the arc (i, j) for a train of type k, such that (i, j)∈Sr γk i,j,r Enforced headway time for a train of type k, on arc (i, j) belonging to the path r λk rReduction factor in path rfor train of type k βk i,j Headway time on arc (i, j) between traffic moving in opposite directions when there is no crossing loop at station jfor train of type k. Pj i,j Probability that the node j∈Nis occupied πj i,j Occupancy probability for the remaining arcs (i0, j) for a node j∈N µj i,j Weighted probability that node j∈Nis not occupied, on arch (i, j) σrProbability that the path ris not occupied ηk p,q Total proportion of trains of type kon path (p, q) and (q, p) νk p,q Proportion of trains of type kon path (p, q) TTime period length xk rNumber of trains of type kcirculating on path r yk i,j Number of trains of type kcirculating on arc (i, j) bxk rNumber of trains of type kcirculating on path rnot delayed byk i,j Number of trains of type kcirculating on arc (i, j) delayed Contents Chapter 1. Introduction 1 1. Study context 1 2. Report structure 4 Chapter 2. Concepts of a railway network 5 1. Infrastructure 5 2. Time parameters 7 3. Rolling stock 7 4. Simplifications 8 Chapter 3. Background Formulations 9 1. Techniques for absolute capacity determination in railways 9 2. An analytical approach to calculate the capacity of a railway system 13 Chapter 4. Two new approaches 17 1. A fixed-point heuristic method for solving non-linear approach 1 17 2. A fixed-point heuristic method for solving non-linear approach 2 23 3. Extension of the models 27 4. Automatic generation of parameters and sets 29 Chapter 5. Computational results 31 1. Medium sized railway network 31 2. Double track network 32 3. Single track network 35 4. Large-scale network 37 Chapter 6. Conclusions 41 References 45 Appendix A. Formulations 47 Appendix B. Tables for double and single track network 55 Appendix C. Catalunya Rodalies Network 67 i Chapter 1 Introduction 1. Study context Within the management of railway systems, one of the elements to take into account to provide an efficient train traffic, is the dimension of the network capacity. If this is a known factor, the amount of trains circulating can be handled and it is possible to know the available capacity, i.e. to know the numbers of additional trains that may be put into operative . At the same time, it allows the management operator to know if the line capacities are inefficient, because if there are more trains than the system allows, probably the network is under congestion or bottlenecks occur in some stations or node on the network, reducing the service level. On the other hand, having a correct estimation of the capacity, helps to know which are the volumes that can be moved along the network, and if at any time the demand is increased, know if it is necessary to expand the network to maintain the services in the estimated times. This last situation (expanding the network) is a really important issue to solve for the investors, because a good estimation of additional required capacity -Available capacitycould save a high investment. However, achieving a current approach of the capacity is a complex task for many elements that must be incorporated in the estimation model. Thus, as the railway knowing the capacity of a railway system produces a great impact on the service level, International Union of Railway (UIC from its French name, Union Internationale des Chemins de fer) has proposed a method (UIC Leaflet 405 OR, 1996) based on timetable to deal with this issue. Furthermore, other interested researchers have developed alternative methods that consider factors that are not incorporated in the methodology provided by UIC. The influential parameters to estimate the railway capacity can be categorized depending on the literature. [7] indicates the balance between average speed, heterogeneity, stability and number of trains. On the other hand, [3] proposes to grouping the parameters under infrastructure, time and rolling stock. However, the real issue has been to find a common definition of what can be understood by the capacity of a railway network ∗The capacity of a railway line is the ability to operate trains with an acceptable punctuality [8] 1 8 2. CONCEPTS OF A RAILWAY NETWORK increase its complexity but, rather increases the amount of variables, and this can be an important issue in the solving time of the problem and could determine the solution method. Heterogeneity in train types, usually different train types share all or part of a given railway network. For example, trains to travel short distances, stopping in each station and hence it will not need a high speed but probably will need a great capacity to transport all passengers. But if it is an express service, it will be a train operating at a higher speed. On the other hand, if the service is international, the trains must have a major capacity and in some case a high speed. In the case of freight trains there will also be a variety of train types depending on the service; rolling stock characteristics such as acceleration and deceleration are also important. Hence, the capacity of the network will depend on the proportion of each kind of train being used to support the corresponding demand. 4. Simplifications The formulations presented in this master thesis include the elements which represent the main parameters that restrict the capacity in a railway system. However, some simplifications have been considered to carry out the models. ∗The scheduling methodology has not been considered a base to develop the formulations. ∗Double and single tracks have been taken into account separately, i.e. the network possesses only, double tracks or single tracks, but an explicit formulation with both cases at the same time has not been included . ∗Headway time concept will depend on the infrastructure parameters. For instance, in single-track case, travel time between two crossing loops is considered, and for double track, the travel time between two node or stations independently if they possess a crossing loop. ∗Mix of trains is considered as a fixed parameter given, and their difference lies in the speed of trains and not in the type of service. i.e., regional, international, urban or express service is not taken into account and neither is the concept of satisfying a minimum of passengers or freight demand included. Therefore, there is no difference between the type of service. ∗The concept of priority is not included for the case when conflicts in some nodes appear. ∗The data structure proposed allows the application in a design of large scale network, due to that it includes all the possible paths between origin / destination pairs. ∗The dwell time is fixed and does not consider stochastic conflicts. ∗Maneuver times have been reduced to the average travel speed on sections, and the deceleration and acceleration at the entrance or exit of a station has been considered in the dwell time. Chapter 3 Background Formulations In this chapter, the two models used as a basis for proposing the new approaches of the next chapter are explained. The first one will be ”Techniques for absolute capacity determination in railways” by [1], and the second one, ”An analytical approach to calculate the capacity of a railway system” by [2]. Moreover, for each one of these formulations, their components, simplifications and assumptions are highlighted and commented. However, it is necessary to mention that the nomenclature and notation of this reference articles have been modified in order to facilitate the comparison between them. 1. Techniques for absolute capacity determination in railways This section presents a model which has as objective function, the maximization of the amount of trains on a railway system. To do this, the authors in [1] extend the bottleneck approach incorporating additional operational factors that the original (bottleneck approach) does not include such as the dwell times, the lengths of trains and stopping protocols. Also, the bottleneck analysis is usually used for a single train type, and as it was mentioned in the previous chapter, is a strong simplification that this approach considers in its formulation through the concept of percentage train mix, which it is computed from an actual or observed train mix. Consequently, two distribution concepts are introduced: ∗Proportional distribution (ηk p,q) is the distribution of the types of trains, with regard to the total, through a corridor considering both direction. ∗Directional distribution, (νk p,q) is the distribution of the types of trains, with regard to the total, through a corridor considering only one direction. Thus, it is possible to incorporate the composition of train types in the model through the followings equations: 9 10 3. BACKGROUND FORMULATIONS xk r+xk r0=ηk p,qX k0∈K (xk0 r+xk0 r0)∀k∈K,∀(p, q)∈R,∀r∈ξp,q (1) xk r=νk p,q[xk r+xk r0]∀k∈K,∀(p, q)∈R,∀r∈ξp,q (2) Just to avoid confusion, it is explained that r0refers to the opposite path to r, i.e. if path r∈ξp,q, then r0is denoted as path r0∈ξq,p such that it contains the same sections as r, but in reversed order. Signals and reference locations are considered in the model to not overestimate the capacity of the network in the cases when bi-directional flows on a single track exist. To avoid this situation the enforced headway is used by the authors as proportional to the number of pairs of alternating trains. This will be dictated by a train schedule, and hence the absolute capacity will vary depending on the level of fleeting. Thus, an upper bound of the capacity will be the best sequence of trains, i.e. all trains in one direction, and the other fleet of trains in the opposite direction. With this schedule it is possible to decrease the enforced headway time on the system. On the other hand, when the traffic has the worst combinations, i.e. one train up, and the next down, and so on. The enforced headway time will be higher thus producing a lower bound capacity. Therefore, the equations to bound the problem in the corridors are: X k∈K [ρk i,jxk r+ρk j,ixk r0] + βk m,nz≤T∀r∈C(3) X k∈K [ρk i,jxk r+ρk j,ixk r0] + min(βk m,n, βk n,m)≤T∀r∈C(4) It is necessary to highlight that both equations must be evaluated in the model in a separate way, i.e. solve the problem including first constraints (3) in order to obtain a lower bound, and then, separately solve the problem including only constraints (4) in order to obtain a upper bound. In this way, a range of values for the railway capacity will be obtained, and the actual level of capacity will then depend on the efficiency of the timetable that the operator will adopt in order to satisfy parameter demand However, equations (3) and (4) are useful only when the problem is an evaluated problem at a corridor level. In the case when the situation requires a more exhaustive study of the situation in sections, the estimation of the headway time must be modified as the sum of two weighted average traveling times. In [1], the traveling times in particular were based upon the time it takes each train to reach the nearest crossing loop. Furthermore, the variable related with the number of trains traveling in the corridors, must be changed for a new variable associated with the number of trains traveling in the section. Thus, the new constraints to consider in the model are: 1. TECHNIQUES FOR ABSOLUTE CAPACITY DETERMINATION IN RAILWAYS 11 X k∈K [θk i,jyk i,j +θk j,iyk j,i] + βk i,j(Yi,j , Yj,i)≤T∀r∈C,∀(i, j)∈A(5) βk i,j(Yi,j , Yj,i) = γk r,i,jxk r Yi,j +γk r0,j,ixk r0 Yj,i ∀(i, j)∈A,∀k∈K(6) yk i,j =X r∈Ωi,j xk r∀(i, j)∈A(7) Yi,j =X k∈K yk i,j ∀(i, j)∈A(8) In equation (5) it is possible to see that the authors include βk i,j, the enforced headway time for a train of type k on corridor (p, q) on section (i, j). And also xk r/Yi,j which is the proportion of the current configuration of train types. Moreover, with equations (5) and (6) the problem becomes non-linear. Dwell times are added as reduction factors over the total number of trains on the network. The article shows three different approaches to determine it, and additionally, propose two ways of how can be used in the resolution methods. 1.1. The first approach for the reduction factor. Is computed as the proportion of time that the train is delayed due to its dwell time in the station. The following set of equations allows us to see clearly the way in which the authors deal with this subject. ρk r=X (i,j)∈Sr θk i,j ∀r∈C,∀k∈K(9) ϑk r=X (i,j)∈Sr (θk i,j +αk j)∀r∈C,∀k∈K(10) λk r=ρk r ϑk r ∀r∈C,∀k∈K(11) λr=X k∈K ηk p,q[µk rλk r+µk r0λk r0]∀(p, q)∈R,∀r∈ξp,q,∀r0∈ξq,p (12) In first instance, they compute the total travelling time on corridors, then the dwell on each station on the corridor is added to obtain the reduction factor for each train in a corridor, dividing the travelling time in the path (p, q) over the total time, including the dwell time. Once that is achieved, this factor must be adjusted in both directions of travel, through the directional distribution. And finally, we add up these factors for each type of train multiplied by its proportional distribution. Once the reduction factor for each corridor has been obtained, this can be added directly from the objective function, after the initial problem (i.e. only considering the mixed train and signals constrains) has been resolved. Or as a second option, it can be resolved as one problem including the set of equations into the initial problem. 12 3. BACKGROUND FORMULATIONS Absolute Capacity =X r∈C λrX k∈K xk r (13) 1.2. The second approach for the reduction factor. Uses the same solving methodology, however, the set of equations is different. In this case, the sectional running time is multiplied by its respective direction proportion sum in both directions, to obtain the sectional running time on the corridor for each type of train. Likewise, the dwell times are obtained, then each factor is multiplied by its proportional distribution summing for all types of trains, getting the weighted average transit time and the weighted average total dwell time. And finally, the reduction factor will be the quotient between the last parameters obtained. αk r=µp,q X (i,j)∈Sr αk j+µq,p X (j,i)∈Sr0 αk i∀(p, q)∈R,∀r∈ξp,q,∀r0∈ξq,p (14) ρk r=µp,qρk r+µq,pρk r0∀(p, q)∈R,∀r∈ξp,q,∀r0∈ξq,p (15) bρk r=X k∈K ηk p,qρk r∀r∈ξp,q (16) bαk r=X k∈K ηk p,qαk r∀r∈ξp,q (17) λr=bρk r bρk r+bαk r ∀r∈ξp,q (18) 1.3. The third approach for the reduction factor. Is quite different because until now, prior estimation has been at the corridor level, however when it is at the section level, the estimation of the reduction factor must be modified, and it will have the same structure as (6). λk i,j =λk r,i,jxk r Yi,j +λk r0,j,ixk r0 Yj,i ∀(i, j)∈A,∀k∈K(19) It is necessary to distinguish that this reduction factor is for a section for all types of trains, and the prior approach is the reduction factor for corridors. Hence, to introduce this factor λk i,j on the formulation, the proportional distribution and directional distribution must be adapted for a section level as follows: ηk i,j =yk i,j +yk j,i Yi,j +Yj,i ∀(i, j)∈A,∀k∈K(20) µk i,j =yk i,j Yi,j ∀(i, j)∈A,∀k∈K(21) Thus, the new reduction factor is added multiplying this new equation and then incorporated in the general formulation. 2. AN ANALYTICAL APPROACH TO CALCULATE THE CAPACITY OF A RAILWAY SYSTEM13 The model presented by [1] is in general a good approach because it considers three relevant factors like composition of train flows, signals and dwell times. Nevertheless, some elements are simplified, for example, a steady state is assumed (i.e. the time it takes for trains to reach a specific position prior to the time period). Neither does it take into account the scheduling, but only introduces it implicitly through the equations (4) and (5), assuming a given configuration of trains. Delays caused by multiple trains interactions are also not handled. 2. An analytical approach to calculate the capacity of a railway system This paper in [2] proposes new concepts and a different way to estimate the absolute capacity in a complex node. Here, the objective function presented seeks the maximization of the amount of trains on the network, using a relatively simple model that allows very short computing times and is based on the work done by [1] and [14] that is the paper previously presented. However, the main difference with the other approach is that, here the model is on the complex node and this forces a new way to tackle the problem. Thus, the authors split a complex node in its three main infrastructure elements; simple nodes, lines and station, where usually in a real case a big station is a complex node. Hence, in these particular cases, this kind of approach is very useful, although, some different types of times must be incorporated to achieve an actual approach. In this way, the time as accelerated and decelerated is considered. Thereby, and using the constraints of time intervals present in [2], it is that the three equations associated for each element is introduced into the model. X r∈Ωi,j X k∈K (xk rα1 j,k +bxk rbα1 j,k)≤T∀j∈G(22) X r∈Ωi,l X k∈K (xk rα2 l,k +bxk rbα2 l,k)≤T∀l∈G(23) X r∈CX k∈K (xk r+bxk r)≤Cl∀(p, q)∈R(24) Eq. (22) is associated to the station. Eq. (23), to the time involved in a simple node, and Eq. (24) with a little different structure, related with the line capacity. As it is possible to observe, a new variable is introduced in theses equations, to show the amount of trains delayed. Thus, this model considers two types of variables; one type associated to the number of trains which circulate on the network without interruptions, called regular trains, and a second type variables that represent the amount of trains that have been delayed due to conflicts on a simple node, named as irregular trains. However, to make the difference between these two types of trains, the fraction of time Pj rthat path r∈Ωi,j is occupied, or equivalently, the probability that a train is in a conflict with flows in path r, can be expressed by the following equation: 14 3. BACKGROUND FORMULATIONS Pj r=1 TX k∈K (xk rα2 j,k +bxk rbα2 j,k)∀j∈G,∀r∈Ωi,j (25) Here is represented the probability of conflict in a specific node j, where both variables are considered with their corresponding dwell times on the node. In fact, for the regular trains, the dwell time, will be defined by the schedule. However, the time for the irregular train includes the maneuver time, accelerated, decelerated time, and in some cases, as with a single track, the time waiting for enabled track, which are estimated separately. To introduce the constraint associated to the irregular trains, the authors consider the following approach. xj r= (xk r+bxj r) Pj rX m∈Ωi,j Pj m 1−X m∈Ωi,j Pj m∀j∈G,∀r∈Ωi,j, m 6=r(26) As per a type of train and for each path belonging to specific simple node the Irregular trains will be a percentage of the total amount of them. This percentage is the result of the product between the probability obtained in the Eq. (26) for a node, and the sum of probability to the rest of path minus the given node, and moreover dividing by how much of the available fraction of time that all trains belonging to the path under consideration use. Let us note that when the node is extremely congested (i.e. the sum for each path that converges in the node is equal to one) the probability of interference for a given path is equal to the sum of percentage of the period Tused by all other paths. However, the model will likely produce null values using the previous constraints, and to avoid this result, a maximum and minimum number of trains must be imposed for each type of them. X k∈K (xk r+bxk r)≥LBr∀r∈C(27) X k∈K (xk r+bxk r)≤UBr∀r∈C(28) Furthermore, Eq. (26) makes the problem nonlinear, and the method that the authors in [2] propose to solve the model as a linear problem is the following: step 1 fix a value for the matrix P step 2 relax constraints (25) step 3 solve the linear programming problem step 4 insert the values x and bxin Eq. (25) step 5 if maxr,kεr,k ≤%stop step 6 else calculate the new values of P and go to step 2 2. AN ANALYTICAL APPROACH TO CALCULATE THE CAPACITY OF A RAILWAY SYSTEM15 Models proposed by [2] may have problems when applied on a large network with many stations, nodes, signals and single or double tracks. In other words, and based on the article presented above, the variables considered are only at corridor level and do not include the situation of what happens in the sections with the signals. Moreover, the objective of the model is not replacing the simulation or the scheduling approach which instead can take into account time evolution and crossed statistical dependence of the arrival characteristic of each type of train, neither does it include the proportional distribution of trains on the network. While it is true that, the diversity of train types (i.e. different speed and length) is added in the approach, the proportion of how this diversity is distributed on the network is not represented in any equation. Chapter 4 Two new approaches This chapter presents two new extended approaches of the models presented previously, where each one of them includes, in its formulation, the parameters related with configuration of train flows, signals, dwell time, headway time, traffic at section level and the corresponding variations for networks with double and single track. Both models will be explained separately with their respective linear and non-linear problem. The original formulation includes non-linear constraints, and to solve an alternative way through a heuristic method (fixed-point method), the linearization of the problem will be developed. Therefore, each approach contains: a non-linear problem with a set of general constraints and a variation for double and single track, together with a linear problem that includes the same contents. In Appendix A, the models proposed are stated for each one of the seven cases set out in this chapter. In addition, at the end of the chapter, two different extensions are presented that can be applied to the models proposed. Moreover, a methodology to automatically generate the sets of data through the shortest path algorithm is presented in the final subsection. 1. A fixed-point heuristic method for solving nonlinear approach 1 Before explaining the model based on [2], it is necessary to describe some sets and subsets that will be used in almost every constraint, and whose understanding is important to observe the difference between a single and double track network system. For this purpose, let us call the set Ga subset of N, where Gcorresponds to the nodes with crossing loop. Let Fbe all sub-paths bounded by two nodes (m, n) : m, n ∈G. Let Dset be the arcs (i, j) that compose the sub path (m, n)∈F. Hence, in a double track the sets used are Nand A, and for a single track the sets are G,Fand D. Therefore, the objective function that maximizes the total number of trains traversing the railway system is as follows: max xX r∈CX k∈K xk r (29) 17 24 4. TWO NEW APPROACHES to the Eq. (1) and (2). Furthermore, considering that this model is an extension of [1], it will also provide a range of solutions regarding the total number of trains allowed on the network, being the maximum of trains as consequence of the optimal programming of the rolling stock, and the minimum of the worst combination of trains. The fact that the approach 2 has less constraints than model 1, it will influence in the results when these approaches will be compared, i.e. in the outcomes, the maximum number of trains provided by the formulation 2, will be higher than the first model, because the second model is less restrictive. The set of variables is also smaller than in previous approach because, in this case the number of trains delayed is not considered as a variable of the model. Hence, two sets of important variables associated to the number of trains of a given type k traveling through a particular path are used with one at corridor level (xk r), and the same variable but at section level (yk i,j). The objective function (29) continues to be the same for this approach, however, some constraints present small variations: Eq. (50) has a similar structure to (35), and its meaning is strictly the same, i.e. the total trains of type k, traveling on a section (i, j) must be obtained considering the flows of train of type kand all path rthat use section (i, j). (51) is a new family of constraints and defines the variables Yi,j, total number of trains traveling in the section (i, j), considering all types of trains. Eq. (53) is equal to Eq. (36) with the only difference that in (53) the variable takes the total of trains and does not make any difference between delayed and non-delayed trains. The same case happens between (52) and (37), only that these equations are for single tracks, and (53) is for double tracks. The constraints that must be included in the model in order to estimate the lower bound of the total capacity of the railway system are (54) and (55) depending on whether the network consists of single or double tracks respectively. Both equations include the dwell times and the headway time in their formulation. However, despite that the left parts of the constraints are equal, the right side is different, because the headway time concept used is not the same. Let us recall that, for a single track the time that must be taken into account will be the traveling time between two stations with crossing loop, and in the double track, this time will only be the traveling time between two stations, no matter if it has crossing loop or not. Furthermore, to be solved, both equations need a prior computation of the maximum headway time over a node, or the minimum number of trains traveling in a section in opposite direction (fleet). Thus, through (54) the non-linearity arises. 2. A FIXED-POINT HEURISTIC METHOD FOR SOLVING NON-LINEAR APPROACH 2 25 yk i,j =X r∈Ω(i,j) xk r∀k∈K,∀(i, j)∈A (50) Yi,j =X k∈A yk i,j ∀(i, j)∈A (51) X k∈KX (i,j)∈Dm,n ((θk i,j +αk j)yk i,j + (θk j,i +αk i)yk j,i)≤T∀(m, n)∈F (52) X k∈K (θk i,j +αk j)yk i,j ≤T∀(i, j)∈A (53) X k∈Kαk jyk i,j +max (j,n)∈Fβk j,nmin(Yi,j , Yj,i)≤T∀j∈G,∀(m, j)∈F,∀(i, j)∈Dm,j (54) X k∈Kαk jyk i,j +max (j,n)∈Aθk j,nyk i,j≤T∀j∈N,∀(i, j)∈A, n 6=i (55) X k∈K (αk jyk i,j)≤T∀k∈K,∀(m, j)∈F,∀(i, j)∈Dm,j (56) X k∈K (αk jyk i,j)≤T∀(i, j)∈A (57) Inequalities (56) and (57) are associated with the upper bound supported by the network for a single and double track, being the latter, the reason why the only difference between them is the set where the inequalities are applied. It is possible to observe that these constraints only include dwell times, since in order to obtain the maximum number of trains on the railway system, the optional sequencing of them, must be every one in one direction, and then all in the opposite direction. In this way, trains will not be delayed at nodes, and no enforced headway will take place at node. (See in Appendix A Single-track non-linear problem 2 and Double-track non-linear problem 2 ) 2.1. A previous reformulation. To linearize the non-linear problem, for the single track case, some continuous and binary variables must be incorporated along with their respective constraints. Therefore, the inequality (55) that obtains a lower bound for a double track system, will be replaced by (46). And the Eq. (54) associated for a single track network, will be changed by the following constraint: 26 4. TWO NEW APPROACHES X k∈Kαk jyk i,j +b βk i,j Qi,j≤T∀k∈K,∀(m, j)∈F,∀(i, j)∈Dm,j (58) Eq. (58) has equal structure to (47), however, in this equation, b βk i,j (headway time applied for a single track) is multiplied by a new continuous positive variable Qi,j. The variable is related with the minimum sequence of trains allowed in a section (i, j), and (58) becomes a linear constraint. On the other hand, the use of this new variable, requires new constraints that allow the relation with the other variables of the problem. Eq. (59) and (60) are the upper bound for Qi,j . Hence, the maximum value that Qi,j may take will be the maximum number of trains traveling in the section (i, j), this is Yi,j or Yj,i. (61) forces both binary variables to sum up to one, where d1i,j is associated when Yi,j is the minimum and d2i,j when Yj,i is the minimum. Qi,j ≤Yi,j ∀k∈K,∀(i, j)∈A(59) Qi,j ≤Yj,i ∀k∈K,∀(i, j)∈A(60) d1i,j +d2i,j = 1 ∀k∈K,∀(i, j)∈A(61) Qi,j ≥Yi,j −M( 1 −d1i,j)∀k∈K,∀(i, j)∈A(62) Qi,j ≥Yj,i −M( 1 −d2i,j )∀k∈K,∀(i, j)∈A(63) Finally, Eq. (62) indicates that if Yi,j is the minimum between (Yi,j, Yj,i), then Qi,j ≥Yi,j and Yi,j ≥Qi,j, hence Qi,j takes the value of Yi,j. And for (63) applied for the same situation (Yi,j minimum), Qi,j ≥Yj,i −M, where Mis a big number, and as Qi,j must be positive, (63) is a superfluous constraint. And the same reasoning can be applied when Yj,i is the minimum value. (The summary formulation can be seen in Appendix A in Single-track linear problem 2 and Doubletrack linear problem 2 ) 2.2. The fixed-point heuristic method. The non-linearity emerged by the approach 2, has already been eliminated in the previous section when the variable Qi,j was introduced. However, if in future extensions, the way to estimate the headway time is different to the one proposed in this master thesis, and the equation to estimate it is as suggested by [1], i.e. using the Eq. (6), the fix-point method will also be a good methodology to tackle the non-linearity raised by this constraint (6). Therefore, for the single track and with a estimation of βk i,j under the Eq. (6), the steps for the algorithms will be exactly the same ones that were used in the first approach, the only difference lying in the estimation of the initial point. Thus, to find the first solution, the linear problem that must be solved considers the Eq. (1), (2), (50) and (51) plus the follow constraint X r∈Ωi,j X k∈K θk i,jxk r≤T∀(i, j)∈A(64) 3. EXTENSION OF THE MODELS 27 Thus, the linear problem (i.e. step (a) of the algorithm) used to find the initial solution represents the simplest formulation to estimate the railway capacity, since that considers only heterogeneous composition of train flows. Finally, the iterative process, described with detail in the solving methodology for the linear approach 1, can be summarized as follows: (1) Initial: (a) Solve [Abs Network Capacity] linear problem using Eq. (1), (2), (50), (51) and (64) (b) Compute the values for βk i,j ∀(i, j)∈A (c) u= 1, X(0) =xk(0) r. (2) While (ϕ≥ε) do: (a) Solve [Abs Network Capacity] for the second linear approach (b) b X(u)=xk(u) r (c) Compute X(u)=X(u−1) +ξ(u)(b X(u)−X(u−1)) (d) ϕ=kX(u)−X(u−1)k kX(u)k (e) Update X(u−1) =xk(u) r, u =u+ 1. (f) Compute the new values for βk i,j ∀(i, j)∈A (g) End While 3. Extension of the models 3.1. Extension A: Minimum traffic. Both approaches previously commented have an objective function (29) that maximizes the total number of trains on the railway system. However, for the formulations presented until now, the algorithm will tend to discard all long-distance paths and will select mostly, the shortest path for each origin / destination pair. Therefore, using a formulation without a minimum number of trains for each line could generate a distortion of the estimate a capacity obtained by the algorithms when applied to realistic networks on which a given number of lines is already operating in order to satisfy some specific demand. To avoid this issue, and with the aim of comparing the approaches in a real situation, the following constraint must be added for each one. Nevertheless, it is necessary to stress that the Eq (65) is an oversimplification for the minimum demand satisfaction requirement on the network. X k∈K xk r≥LBr∀r∈C(65) The parameter LBrrepresents the minimum amount of trains that the network requires, for each path. A finer extension would be including additional constraints that take into account the demand requirements for each type of train and for each type of service. 28 4. TWO NEW APPROACHES 3.2. Extension B: An alternative formulation for approach 2. Let us recall that the main difference between both models presented is that the second approach does not distinguish the delayed trains and the outcome is a range of maximum capacity. i.e. a lower and upper bound. However, the incorporation of some continue and binary variables related with the travel time, and with their respective constraints, allow finding a value between this optimal rank, for the case of double and single track. Additional variables Two sets of continuous variables must be introduced. The first one, τk rwhich is the departure time between two consecutive trains of type k, following the path r. And the second tk rwhich is the traveling time on path r, by train of type k. Furthermore, a binary variable δk rmust be included that indicates whether the train k, crosses the path r. Additional parameters A new parameter θk ris required, that represents the travel time in the first section belonging to the path r, for each train of type k. And another parameter hk r, that will represent the arriving time between two consecutive trains of type k, following the path r. When Double-track case is considered, the following equations must be added, to replace the Eq. (55) and (57). τ1 r+δ1 rρ1 r+h1 rx1 r<=t1 r (66) τk r+δk rρk r+hk rxk r<=tk r (67) τk r≥τk−1 r+hk−1 rxk−1 r+θk rδk r (68) τk r≤T(69) δk r≤xk r≤Mrδk r, δk r∈ {0,1}(70) The approach two must be modified, including the set of equations (66) (70) and remove (55) and (57) associated with lower and upper bound respectively. Thus, the solution obtained using this new formulation will be a value between the rank of optimal capacity given by the original model 2. Specifically, (66) represents the travel time for the first train on the network, where is added the starting time τk r, plus the travel time in crossing the path r ρk rmultiplied by the binary variable δk r if the train effectively is using path r, and the headway time hk r(which is the the arriving time for two consecutive trains), which must be less than the time variable tk r. Likewise, the Eq (67) represents the time for every other train that is crossing the path rbelonging to the system. On the other hand, (68) indicates that the departure time for a train of type kthat is going to start, must be greater than the sum of the starting time and headway time for the previous train, plus the travel time of the first section θk rof the path for the train that is going to start the travel. 4. AUTOMATIC GENERATION OF PARAMETERS AND SETS 29 (69) and (70) represent in first instance, that the variable tk rmust be less or equal to the period of time T, and secondly, the relation between the binary variable with the variable xk r. For the Single-track case must be taken into account the Eq.(66), (67), (68), (70) and some additional constraints are included: τ1 r0≥tk r (71) τ1 r0+δ1 r0ρ1 r0+h1 r0x1 r0<=t1 r0 (72) τk r0+δk r0ρk r0+hk r0xk r0<=tk r0 (73) τk r0≥τk−1 r0+hk−1 r0xk−1 r0+θk r0δk r0 (74) τk r0≤T(75) δk r0≤xk r0≤Mr0δk r0, δk r0∈ {0,1}(76) The set of equations from (72) to (77) are exactly equal to previous sets of equations, but for a train that follows the path r0, where if ris the path which unites the pair origin / destination (p, q), then r0unites the pair (q, p). Let us bear in mind that, travel in both directions must be considered on a single track. Thus, the Eq (71) ensures that the trains that start the travel from qto p, must do it after the train that follows the path rhas already finished. Finally, the additional parameters have the following compute equations: hk r= max (i,j)∈Sr {θk i,j} ∀r∈C(77) θk r=θk i,j ∀(p, q)∈R,∀k∈K,∀r∈ξp,q,∀(i, j)∈Sr:i=p(78) 4. Automatic generation of parameters and sets Part of the sets used to resolve the formulations set out in this master thesis require a special attention, because some of them are not easy to create and could lead to consistency errors if a generation algorithm is not used. Therefore, to deal with this issue, some sets will be generated automatically based on other sets that define the network. Thus Table 1. shows which sets will be generated through the algorithm To create the sets belonging to the column at the right side, it will be necessary solve a shortest path problem, to find all the possible paths that join an origin / destination pair. This process must be developed through a generation algorithm because each one of these sets is composed by several elements, and if one of them is not found, at the moment of solving the problem, the result will be unfeasible or not bounded . 30 4. TWO NEW APPROACHES By hand By Algorithm Nξ R S AΩ G D F C Table 1. sets For instance, to Ω set, that are all path rthat cross a section (i, j), would be a great work to establish all paths that cross it and furthermore it would not be easy to consider a path in a big network. Thus, to avoid this issue, first it is necessary, through the shortest algorithm without sub-circuits, to find all possible path rfor each origin / destination pairs, and then find the paths that cross a section (i, j) for each one of them belonging to A Therefore, there are two problems that must be solved: the first one, is a simple optimization problem with just a balanced constraint, and the second one, to create the amount of possible paths, it should include constraints that avoid sub-circuits. min Link X (i,j)∈A Costi,jLinki,j (79) X (i,j)∈A Linki,j −X (j,i)∈A Linkj,i =     1if i =p 0if (i, j)6= (p, q) −1if j =q (80) X (i,j)∈A Linki,jLink0 i,j ≤X (i,j)∈A |Link0 i,j| − 1(81) X (i,j)∈A Costi,jLinki,j ≥Costi,j Link0 i,j + min (i,j)inACosti,j (82) In the problem above, Linki,j is the binary variable which represents a section (i, j), the parameter Costi,j is the cost of each section and their values are generated randomly. Link0 i,j is a vector of ones and consequently another parameter that is necessary in constraint to avoid sub-circuits, and (p, q) represent the origin / destination points. Finally, all the sets are generated using the complete algorithm and only the set Duses the Eq. (79) and (80) Chapter 5 Computational results 1. Medium sized railway network To apply the approaches presented, this thesis considered the Line 1, 2, 3 and 7 of Rodalies Network of Catalunya, shown in Fig. 1, with 124,4 km of tracks. The railway system includes elements of the three parameter categories that influence over the capacity. Specifically, it is composed by 8 points of origin / destination, 29 stations of which 16 can be considered without crossing loop, and three nodes. Furthermore, it has 6 types of trains, among them, 450, 447, Civia, 470, 449 and 448 to offer regional service and in Barcelona down town with a maximum speed of 120, 140 and 160 Km/h depending on the series. Line 1 that is composed of 47.7 km of tracks, has been taken from Molins de Rei (B) to Matar´o (E). For Line 2 has been considered only from Vilanova i la Geltr´u (A) to Estaci´o de Fran¸ca (C) with 48 Km. Line 3 has been taken into account from L’Hospitalet (16) to Granollers (F) with 36.5 km of tracks, and finally to Line 7, from Sant Andreu (24) to Cerdanyola Universitat (D) with 13,1 km. (Configuration of the network in Tables 15-16) The network as it is considered, i.e. with stations without crossing loops, allows replacing the signals by these stations due to that the train must be stopped for a given time and does not allow the train flows in the opposite direction because it does not have an additional track. Hence, in a hypothetical situation, all the 16 simple stations can be considered as signals. For the case study, only two out of six types of trains have been taken into account since the only relevant parameter is speed. Hence, the approaches will be tested for trains with average speed of 100 and 80 km/h for a period of 18 hours and including the dwell times given by standard scheduling. Furthermore, as the formulations have been designed to be applied in large-scale networks, all possible paths that join origin/destination pairs will be considered. The models have been evaluated assuming two possible scenarios. In the first one, the network is composed only by double track segments, and in the second, the railway system has only single tracks in all segments. A mixed scenario has not 31 32 5. COMPUTATIONAL RESULTS Fig. 1. Traveling time vs. headway time been considered because the objective is to observe the percentage that influences the double and single-track factor in a network. Finally, to facilitate the understanding of the results, all the tables discussed below are attached in Appendix B. 2. Double track network 2.1. General results. Table 1 indicates that traffic exists in 20 out of 48 possible paths, without considering a minimum of trains in each one of them and a given rolling stock and dwell time. Specifically, each column of the table presents the traffic distribution for each possible path obtained through the different formulations. In Table 1 it is possible to observe that the differences between the results are related to linear and non-linear problems. For the first approach, they are very similar in terms of the total flows, but different with their traffic distribution. Thus, the linear approach 1 estimates the capacity of the network in 1.969,85 trains while the non-linear model 1 indicates 1.983,99 trains, giving a 0,72% of difference. On the other hand, the formulation 2 provides an optimal rank between 1.314,08 and 2.181,53 trains on the network for 18 hours. Thereby, the result of the first approach is within of the optimal rank provided by the model 2, and being precise a 9,05% below of the upper bound (2.181,53 trains) Furthermore, the paths which have the highest train flows are those with the smallest length of track, this is the case of paths (B, 16) and (D, 24) that have 10 km and 13,1 km respectively, being the number of trains that cross these paths 372,78 and 338,79 trains in 18 hours (a train every 3 minutes). On the contrary, the longest track (A, C) has the lowest train flows with a total of 27,12 trains (one train every 40 minutes). 2. DOUBLE TRACK NETWORK 33 Fig. 2. Convergence of the iterative process Table 2 shows the percentage of trains not delayed and delayed for each path. In general, all the paths that cross node 12, where 4 sections converge, has a high percentage of delayed, highlighting the paths (E, 24) and (24, E) that have the 100% of their trains with delay. 2.2. Rolling stock. The results related with Table 1 are under a hypothetical distribution of the mixture of trains associated to the parameters ηk p,q yνk p,q. However, in the case where these constraints are not taken into account, the capacity of the network would be increased by 35,6% (2.672,7 trains) and the lines used are reduced to only 10, marked by the shortest path of the network, see Table 5. Moreover, within the 10 paths selected by the models, (B, 16) and (D, 24) continue being the paths with highest train flows with 554 and 480 trains in 18 hours respectively, that correspond to a train every two minutes. However, in these cases, the amount of trains produces an increase in the percentage of trains delayed for these lines particularly. Specifically, for the line (B, 16) the percentage of trains delayed increase from 19% to 59% and the line (D, 24) from 31% to 54%, with regard to the situation that considers the rolling stock parameters. 2.3. Minimum number of trains. As the algorithm does not give paths with more than three nodes, because the formulations tend to select the shortest path, the Table 6 shows the results of a hypothetical case when the models are forced to consider a minimum train flows for each path. Thus, in the case when the minimum number of trains on each path is greater than one, as constraint, the capacity is reduced by 7,86% from 1.969,85 trains to 1.808 regarding the Table 1, and the percentage of trains delayed increases from 40,2% (Table 2) to 45% (Table 6). However two aspects must be stressed: Chapter 6 Conclusions In this master thesis, two approaches (1 and 2) have been presented based on the works done by [1] and [2] to the case of networks with a general configuration for the estimation of the maximum capacity of a railway network. These two models are based on establishing sets of restrictions that incorporate flow variables or the number of circulations in elements of a railway network during a time period of operations. The potential of these models lies in their ability to provide estimates of maximum flows taking into account only: a) their mutual interactions at specific points in the network, such as crossings or small stations, acting as causal agents that limit such flows, b) the possibilities of blocking sections or sections for security reasons. On the one hand, through model 1 it is possible to have a point estimate of the maximum capacity and also, under these conditions of maximum flows, an estimate of the fraction of the flows that are affected by blockages (delay by blockage). On the other hand, through model 2 it is possible to obtain, from two families of different restrictions, a range of values within which the maximum capacity of the system should be. The lower bound of this interval is marked by conditions established by an unfavorable scheduling, while the upper bound is determined by favorable scheduling. Both model 1 and 2 incorporate non-linear constraints and to solve the extension made in this master’s thesis of these models, a heuristic method based on fixedpoint iterations has been implemented in which, in each iteration, various non-linear terms are frozen, to obtain a linear version of the problem. The models have been described using a graph notation, to improve their understanding with respect to the proposed extensions. The computational tests have been carrying out using AMPL and CPLEX or MINOS as solvers. In general words, approach 1 provides more information than the approach 2, allowing a better understanding of the network studied. For instance, it is possible to know the occupation percentage of each path, section, node and the amount of trains with delay that follow a path or just in a particular section. Moreover, it can be adapted easily for cases with double / single-track and give an optimal solution unlike the approach one that provides a region of solution bounded by efficient and inefficient scheduling. Nonetheless, this last parameter (timetable) is the biggest contrast between both models, because the second model does not incorporate it 41 42 6. CONCLUSIONS in an explicit way, but it leaves open the possibility to include it by means of a different estimation of the headway time. The formulations with their respective extensions have been applied on a medium size network corresponding to the line 1,2,3 and 7 of Rodalies Network of Catalunya. Also model 1, for double track, taken into account in the extension A, has been tested on the complete railway system of Rodalies. Given the results shown in chapter 5, applied on the case studies commented, it is possible to observe how relevant the parameters explained in the introduction are (i.e. dwell time, headway time, rolling stock and infrastructure). Each one of them has been modified, keeping the other constant, to observe the impact in percentage on the performance of the test networks. Thus, double / single-track has been considered to represent the case associated with infrastructure parameters (where in the single-track case, the station without crossing loop can play the role as signal or simple station), mix of trains to evaluate the rolling stock, dwell time, to study the time parameter and the headway time to dimension the influence of an efficient scheduling, delivering for each situation, the following summary of results: ∗The models tend to prioritize the shortest paths and their traffic, providing high train flows on these paths and low delay percentages. ∗A network containing long paths and with high amount of nodes, implies a growth over the percentage of delayed trains. ∗For double track systems, the rolling stock parameters have an impact over 30% on the capacity of the network. ∗A decrease of dwell times can affect up to 40% the amount of delayed trains and the capacity of the network. On the other hand, an increase of dwell times, can affect up to 20% the capacity and the percentage of delays. ∗An efficient scheduling can decrease the travel times over 30%. ∗A double track system has at least 3 times more capacity than a single track system. ∗In general, the impact of the time parameters (dwell time and headway time) is higher on a network with single track than a system with double track. ∗The rolling stock parameter has more impact on the percentage of trains delayed than on capacity of the network in case that a single track is considered. Future extensions can be developed from the approaches set out in this work including the concepts of passenger demand and type of service (i.e. express, international, regional, urban). For instance, the models proposed use the distribution of train types as a fixed parameter which is given. However, that parameter can be estimated in function of the proportion of the type of service required to supply the demand for the different stations on the railway system. The equations associated with the fleet heterogeneity will continue being the same, the only change would be that now the parameters will depend on deterministic / stochastic variables related to the passenger demand. Likewise, the extension applied for the large-scale case, used only a simple constraint to force the model to have a minimum traffic in each line, nevertheless, it could also be written under demand variable, keeping the difference between both constraints, due to that one reflects how the type of service is 6. CONCLUSIONS 43 distributed across the network and the other is associated with a minimum service offered. References [1] R. Burdett, E. Kozan, Techniques for absolute capacity determination in railway, Transportation Research Part B; Methodological 40(8) (2006) 616-632 [2] L. Mussone, R. Wolfler, An analytical approach to calculate the capacity of a railway system, European Journal of Operational Research 228 (2013) 11-23 [3] M. April, F. Barber, L. Ingolotti, M.A. Salido, P. Tormos, A. Lova, An assessment of railway capacity, Transportation Research Part E 44 (2008) 774-806 [4] E. Codina, F. Rosell, A heuristic method for a congested capacitated transit assignment model with strategies Statistics and Operations Research Department, Universitat Politcnica de Catalunya [5] E. Oliveira, B.M. Smith, A job-shop scheduling model for the single-track railway scheduling problem, School of Computing, University of Leeds [6] A. Landex, 2008. Methods to estimate railway capacity and passenger delays, Ph.D. Thesis, Technical University of Denmark [7] UIC, 2004. Capacity (UIC code 406), Ph.D. International Union of Railway (UIC), Paris, France [8] S. Skartsterhagen, Capacity of railway lines, Institute for Energy Technology, Norway, in Norwegian (1993) [9] W. Rothengatter, Bottlenecks in European transport infrastructure, Proceedings of the 24th PTRC European Transport Forum, PTRC, England. (1996) [10] H. Krueger, Parametric modeling in rail capacity planning, Proceedings of the 31st Conference on Winter simulation, eds. P.A. Farrington, H.B. Nembhard, D.T. Sturrock. G.W. Evans, ACM Press New York, NY, USA, Phoenix, Arizona, United States, pp. 1194 [11] D. Wood, S. Robertson, Planning tomorrow’s railway-role of technology in infrastructure and timetable options evaluation, Proceedings of the 8th International Conference on Computers in Railways, eds. J. Allan, R.J. Hill, C.A. Brebbia, G. Sciutto, S. Sone, WITpress, Great Britain, pp. 721 (2002) [12] E.R. Kraft, Jam capacity of single track rail lines, Proceedings of the Transportation Research Forum 23 (1) (1982) 461 - 471 [13] Kittelson and Associates, Inc., Transit Capacity and Quality of Service Manual, second ed., Transportation Research Board,Washington, DC. (2003) [14] A.F. De Kort, B. Heidergott, H. Ayhan, A probabilistic (max, +) approach for determining railway infrastructure capacity, European Journal of Operational Research 148 (2003) 644-661 [15] M. Carey, A. Kwiecinski, Stochastic approximation to the effects of headways on knock-on- delays of trains, Transportation Research Part B 28 (4) (1994) 251 - 267 45 Appendix A Formulations 47 48 A. FORMULATIONS Single-track non-linear problem 1 Pj i,j =1 TX k∈K (αj,k yk i,j +byk i,j max (j,n)∈Fβk j,n)∀j∈G,∀(m, j)∈F,∀(i, j)∈Dm,j, n 6=i X (m,j)∈FX (i,j)∈Dm,j Pj i,j ≤1∀j∈G X k∈KX (i,j)∈Dm,n ((θk i,j +αk j) (yk i,j +byk i,j)+(θk j,i +αk i) (yk j,i +byk j,i)) ≤T∀(m, n)∈F byk i,j = (yk i,j +byk i,j)Pj i,j πj i,j (1 −πj i,j)∀k∈K,∀j∈G,∀(i, j)∈A yk i,j +byk i,j =X r∈Ω(i,j) xk r∀k∈K,∀(i, j)∈A bxk r=σrxk r∀r∈C,∀k∈K byk i,j ≤X r∈Ω(i,j) (1 −σr)xk r∀(i, j)∈A,∀k∈K πj i,j =X (i0,j)∈A Pj (i0,j)−Pj i,j ∀j∈G,∀(i, j)∈A σr=Y j∈N,(i,j)∈Sr µj i,j ∀j∈G,∀(i, j)∈A µj i,j =1−Pj i,j πj i,j (1 −πj i,j)∀j∈G,∀(i, j)∈A βk m,n =X (i,j)∈Dm,n θk i,j ∀k∈K,∀(m, n)∈F xk r+xk r0=ηk p,qX k0∈K (xk0 r+xk0 r0)∀k∈K,∀(p, q)∈R,∀r∈ξp,q xk r=νk p,q[xk r+xk r0]∀k∈K,∀(p, q)∈R,∀r∈ξp,q xk r,bxk r, yk i,j,byk i,j ≥0 1≥Pj i,j ≥0 1≥πj i,j ≥0 A. FORMULATIONS 49 Double-track non-linear problem 1 Pj i,j =1 TX k∈K (αj,k yk i,j +byk i,j max (j,n)∈Aθk j,n)∀j∈N,∀(i, j)∈A, n 6=i X (i,j)∈A Pj i,j ≤1∀j∈N X k∈K (θk i,j +αk j) (yk i,j +byk i,j)≤T∀(i, j)∈A byk i,j = (yk i,j +byk i,j)Pj i,j πj i,j (1 −πj i,j)∀k∈K,∀j∈N,∀(i, j)∈A yk i,j +byk i,j =X r∈Ω(i,j) xk r∀k∈K,∀(i, j)∈A bxk r=σrxk r∀r∈C,∀k∈K byk i,j ≤X r∈Ω(i,j) (1 −σr)xk r∀(i, j)∈A,∀k∈K πj i,j =X (i0,j)∈A Pj (i0,j)−Pj i,j ∀j∈N,∀(i, j)∈A σr=Y j∈N,(i,j)∈Sr µj i,j ∀j∈N,∀(i, j)∈A µj i,j =1−Pj i,j πj i,j (1 −πj i,j)∀j∈N,∀(i, j)∈A xk r+xk r0=ηk p,qX k0∈K (xk0 r+xk0 r0)∀k∈K,∀(p, q)∈R,∀r∈ξp,q xk r=νk p,q[xk r+xk r0]∀k∈K,∀(p, q)∈R,∀r∈ξp,q xk r,bxk r, yk i,j,byk i,j ≥0 1≥Pj i,j ≥0 1≥πj i,j ≥0 56 B. TABLES FOR DOUBLE AND SINGLE TRACK NETWORK Linear Problem Corridors Path Total Trains Trains without Delay % Delayed % without Delay (A, C) 2 64 3 95% 5% (A, 16) 6 98 74 24% 76% (B, 16) 12 373 303 19% 81% (C, A) 14 27 1 96% 4% (16, A) 19 160 137 14% 86% (16, B) 25 193 164 15% 85% (C, E) 27 40 5 88% 13% (E, 16) 32 56 32 43% 57% (E, 24) 33 31 0 100% 0% (24, D) 36 213 147 31% 69% (E, C) 38 164 47 71% 29% (16, E) 43 111 31 72% 28% (24, E) 44 100 0 100% 0% (D, 24) 47 339 234 31% 69% Total 1969 1178 40,2% 59,8% Table 2. Delayed trains considering double track Non-Linear Problem Corridors App 2 UB App 1 LB App 1 (16, B) 12,55 62,9 62,9 (16, E) 52,82 52,82 52,82 (24, A) 38,34 38,34 38,34 (24, D) 28,36 19,75 23,11 (A, 24) 33,68 33,68 33,68 (B, 16) 24,23 121,4 121,4 (B, C) 99,12 0 0 (C, B) 48,31 0 0 (C, D) 10,2 17,28 14,52 (C, F ) 106,48 106,48 106,48 (D, 24) 45,12 31,41 36,76 (D, C) 22,06 37,36 31,39 (E, 16) 26,63 26,63 26,63 (F, C) 54,13 54,13 54,13 Total 602,03 602,18 602,16 Table 3. Results considering single track case B. TABLES FOR DOUBLE AND SINGLE TRACK NETWORK 57 Non-Linear Problem Corridors Path Total Trains Trains without Delay % Delayed % without Delay (A, 24) 7 33,68 0,9 97% 3% (B, C) 8 99,12 38,51 61% 39% (B, 16) 12 24,23 23,71 2% 98% (24, A) 20 38,34 13,03 66% 34% (C, B) 21 48,31 15,78 67% 33% (16, B) 25 12,55 12,53 0% 100% (C, F ) 28 106,48 77,62 27% 73% (C, D) 29 10,2 7,47 27% 73% (E, 16) 32 26,63 10,31 61% 39% (24, D) 36 28,36 27,22 4% 96% (F, C) 39 54,13 40,27 26% 74% (D, C) 40 22,06 16,46 25% 75% (16, E) 43 52,82 20,94 6% 4% (D, 24) 47 45,12 41,36 8% 92% Total 602,03 346,11 42,5% 57,5% Table 4. Delayed trains for single track case Linear Problem Corridors Path Total Trains without Delay % Delayed % without Delay (A, 16) 6 149 87 42% 58% (A, 24) 7 76 7 91% 9% (B, 16) 12 336 74 78% 22% (16, A) 19 208 145 30% 70% (16, B) 25 554 228 59% 41% (24, D) 36 480 266 45% 55% (E, C) 38 263 85 68% 32% (24, E) 44 263 85 68% 32% (D, 24) 47 118 56 53% 47% (F, 24) 48 225 115 49% 51% Total 282 2672 1148 58% 42% Table 5. Delayed trains without considering train mixes 58 B. TABLES FOR DOUBLE AND SINGLE TRACK NETWORK Linear Problem Corridors Path Total Trains without Delay % Delayed % without Delay (A, B) 1 2 1 50% 50% (A, C) 2 5 1 80% 20% (A, E) 3 5 1 80% 20% (A, F) 4 4 1 75% 25% (A, D) 5 12 2 83% 17% (A, 16) 6 102 53 48% 52% (A, 24) 7 2 1 50% 50% (B, C) 8 5 1 80% 20% (B, E) 9 5 1 80% 20% (B, F ) 10 6 1 83% 17% (B, D) 11 3 0 100% 0% (B, 16) 12 346 234 32% 68% (B, 24) 13 4 1 75% 25% (C, A) 14 2 0 100% 0% (B, A) 15 3 1 67% 33% (E, A) 16 5 1 89% 20% (F, A) 17 3 0 100% 0% (D, A) 18 6 1 83% 17% (16, A) 19 166 128 23% 77% (24, A) 20 2 0 100% 0% (C, B) 21 3 0 100% 0% (E, B) 22 3 0 100% 0% (F, B) 23 6 0 100% 0% (D, B) 24 2 0 100% 0% (16, B) 25 179 151 16% 84% (24, B) 26 2 0 100% 0% (C, E) 27 16 1 94% 6% (C, F ) 28 4 0 100% 0% (C, D) 29 3 0 100% 0% (E, D) 30 14 2 86% 14% (E, F) 31 4 1 75% 25% (E, 16) 32 90 15 83% 17% (E, 24) 33 11 3 73% 27% (16, F) 34 4 1 75% 25% (16, D) 35 4 1 75% 25% Table 6. Delayed trains considering a minimum train flows B. TABLES FOR DOUBLE AND SINGLE TRACK NETWORK 59 Linear Problem Corridors Path Total Trains without Delay % Delayed % without Delay (24, D) 36 178 122 31% 69% (24, F) 37 3 2 33% 67% (E, C) 38 66 20 70% 30% (F, C) 39 2 0 100% 0% (D, C) 40 6 1 83% 17% (D, E) 41 12 1 92% 8% (F, E) 42 3 0 100% 0% (16, E) 43 178 51 71% 29% (24, E) 44 36 6 83% 17% (F, 16) 45 5 0 100% 0% (D, 16) 46 4 0 100% 0% (D, 24) 47 284 188 34% 66% (F, 24) 48 5 4 20% 80% Total 1808 994 45% 55% Table 7. Delayed trains Non-linear Problem Corridors Path Total Trains without Delay % Delayed % without Delay (C, A) 14 44,32 36,47 18% 82% (16, A) 19 35,37 31,27 12% 88% (C, B) 21 205,7 169,27 18% 82% (C, E) 27 2,93 2,82 4% 96% (C, D) 29 1,51 1,45 4% 96% (16, F) 34 46,84 37,19 21% 79% (24, D) 36 116,16 116,16 0% 100% (24, F) 37 127,34 127,34 0% 100% (16, E) 43 63,18 50,17 21% 79% (24, E) 44 18,25 18,06 1% 99% Total 661,67 590,27 10,79% 89,21% Table 8. Delayed trains for single track case without considering mixture of trains parameters Non-linear Problem Dwell times Capacity % Train Delayed % capacity % delayed −80% 838,26 1% 39% 99% −50% 727,27 28% 21% 34% −25% 657,9 34% 9% 19% 0 602,03 43% 0% 0% 25% 553,03 46% −8% −9% 50% 517,53 47% −14% −10% 80% 478,45 56% −21% −32% Table 9. Effect of the variation of dwell times for single track case 60 B. TABLES FOR DOUBLE AND SINGLE TRACK NETWORK Linear Problem Path Extension B Approach 1 LB Approach 2 UB Approach 2 (16, A) 5,45 8,7 4,45 7,43 (16, B) 10,73 10,73 8,02 10,73 (16, D) 0 0 0 0,88 (16, E) 10,02 6,18 4,65 12,31 (24, A) 2,5 0 0 0 (24, D) 7,15 11,83 9,67 6,85 (24, E) 0 5,57 0 0 (24, F) 0 0 0,1 0,1 (A, 16) 3,36 5,36 2,74 4,58 (A, 24) 2,19 0 0 0 (A, C) 5,9 4 2,24 7,09 (B, 16) 20,71 20,71 15,49 20,71 (C, A) 2,48 1,68 0,94 2,98 (C, E) 0 2,23 1,38 1,89 (C, F ) 8,96 0 0 13,28 (D, 16) 0 0 0 0,9 (D, 24) 11,37 18,82 15,39 10,89 (E, 16) 5,05 3,12 2,35 6,2 (E, 24) 0 1,73 0 0 (E, C) 0 9,08 5,62 7,71 (E, F) 3,81 0 0 0 (F, 24) 0 0 0,17 0,17 (F, C) 4,56 0 0 6,75 (F, E) 2,64 0 0 0 Total 106,88 109,74 73,21 121,45 Table 10. Double track results using Extension B for T = 60 Linear Problem Path Extension B Approach 1 LB Approach 2 UB Approach 2 (16, B) 3,49 3,49 3,49 3,49 (16, E) 0 2,93 2,93 2,93 (24, A) 0 2,13 2,13 2,13 (24, D) 0 1,1 1,28 1,1 (A, 24) 0 1,87 1,87 1,87 (B, 16) 6,74 6,74 6,74 6,74 (C, D) 4,6 0,96 0,81 0,96 (C, F ) 0 5,92 5,92 5,92 (D, 24) 0 1,74 2,04 1,74 (D, C) 9,94 2,08 1,74 2,08 (E, 16) 0 1,48 1,48 1,48 (F, C) 0 3,01 3,01 3,01 Total 24,77 33,45 33,44 33,45 Table 11. Single track results using Extension B for T = 60 B. TABLES FOR DOUBLE AND SINGLE TRACK NETWORK 61 Linear Problem Path Hdway time Dwell time Travel time Min time Max time (%)Hdway Time effect (A, B) 30,85 10,7 25,3 36 66,85 46% (A, C) 29,35 10 24 34 63,35 46% (A, E) 46,95 13,4 37,45 50,85 97,8 48% (A, F) 46,4 16,9 36,85 53,75 100,15 46% (A, D) 39,05 16,3 31,75 48,05 87,1 45% (A, 16) 24,7 8,5 20,3 28,8 53,5 46% (A, 24) 30,55 11,5 25,2 36,7 67,25 45% (B, C) 12,7 7,7 10,4 18,1 30,8 41% (B, E) 30,3 11,1 23,85 34,95 65,25 46% (B, F ) 29,75 14,6 23,25 37,85 67,6 44% (B, D) 22,4 14 18,15 32,15 54,55 41% (B, 16) 5,6 3,7 5 8,7 14,3 39% (B, 24) 13,9 9,2 11,6 20,8 34,7 40% (C, A) 31,8 10 24 34 65,8 48% (B, A) 32,5 10,7 25,3 36 68,5 47% (E, A) 47,55 13,4 37,45 50,85 98,4 48% (F, A) 45,75 16,9 36,85 53,75 99,5 46% (D, A) 40,85 16,3 31,75 48,05 88,9 46% (16, A) 26,9 7 20,3 27,3 54,2 50% (24, A) 31,8 10 25,2 35,2 67 47% (C, B) 13,5 7,7 10,4 18,1 31,6 43% (E, B) 29,25 11,1 23,85 34,95 64,2 46% (F, B) 27,45 14,6 23,25 37,85 65,3 42% (D, B) 22,55 14 18,15 32,15 54,7 41% (16, B) 6,15 2,2 5 7,2 13,35 46% (24, B) 13,5 7,7 11,6 19,3 32,8 41% (C, E) 21 4,4 15,65 20,05 41,05 51% (C, F ) 20,45 7,9 15,05 22,95 43,4 47% (C, D) 13,1 7,3 9,95 17,25 30,35 43% (E, D) 28,85 10,7 23,4 34,1 62,95 46% (E, F) 36,2 11,3 28,5 39,8 76 48% (E, 16) 23,1 8,9 18,85 27,75 50,85 45% (E, 24) 20,35 5,9 16,85 22,75 43,1 47% (16, F) 24,15 10,9 18,25 29,15 53,3 45% (16, D) 16,8 10,3 13,15 23,45 40,25 42% (24, D) 8,5 4,8 6,55 11,35 19,85 43% (24, F) 15,85 5,4 11,65 17,05 32,9 48% (E, C) 19,15 4,4 15,65 20,05 39,2 49% (F, C) 17,35 7,9 15,05 22,95 40,3 43% (D, C) 12,45 7,3 9,95 17,25 29,7 42% (D, E) 30,05 10,7 23,4 34,1 64,15 47% (F, E) 34,95 11,3 28,5 39,8 74,75 47% (16, E) 24,7 7,4 18,85 26,25 50,95 48% (24, E) 21 4,4 16,85 21,25 42,25 50% (F, 16) 21,3 12,4 18,25 30,65 51,95 41% (D, 16) 16,4 11,8 13,15 24,95 41,35 40% (D, 24) 9,05 6,3 6,55 12,85 21,9 41% (F, 24) 13,95 6,9 11,65 18,55 32,5 43% Table 12. Headway time effects for double track test network 62 B. TABLES FOR DOUBLE AND SINGLE TRACK NETWORK Linear Problem Path Hdway time Dwell time Travel time Min time Max time Hdway Time effect (A, B) 41,45 5,1 25,3 30,4 71,85 58% (A, C) 42 6 24 30 72 58% (A, E) 58,95 7 37,45 44,45 103,4 57% (A, F) 63,8 11,1 36,85 47,95 111,75 57% (A, D) 57,5 11,1 31,75 42,85 100,35 57% (A, 16) 34,85 4,5 20,3 24,8 59,65 58% (A, 24) 46,4 7,5 25,2 32,7 79,1 59% (B, C) 25,25 6,1 10,4 16,5 41,75 60% (B, E) 42,2 7,1 23,85 30,95 73,15 58% (B, F ) 47,05 11,2 23,25 34,45 81,5 58% (B, D) 40,75 11,2 18,15 29,35 70,1 58% (B, 16) 8,8 2,1 5 7,1 15,9 55% (B, 24) 29,65 7,6 11,6 19,2 48,85 61% (C, A) 42,05 6 24 30 72,05 58% (B, A) 41,2 5,1 25,3 30,4 71,6 58% (E, A) 60,2 7 37,45 44,45 104,65 58% (F, A) 65,05 11,1 36,85 47,95 113 58% (D, A) 58,3 11,1 31,75 42,85 101,15 58% (16, A) 32,4 3 20,3 23,3 55,7 58% (24, A) 43,25 6 25,2 31,2 74,45 58% (C, B) 25,55 6,1 10,4 16,5 42,05 61% (E, B) 43,7 7,1 23,85 30,95 74,65 59% (F, B) 48,55 11,2 23,25 34,45 83 58% (D, B) 41,8 11,2 18,15 29,35 71,15 59% (16, B) 6,6 0,6 5 5,6 12,2 54% (24, B) 26,75 6,1 11,6 17,7 44,45 60% (C, E) 21,6 2 15,65 17,65 39,25 55% (C, F ) 26,45 6,1 15,05 21,15 47,6 56% (C, D) 20,15 6,1 9,95 16,05 36,2 56% (E, D) 38,3 7,1 23,4 30,5 68,8 56% (E, F) 44,6 7,1 28,5 35,6 80,2 56% (E, 16) 37,1 6,5 18,85 25,35 62,45 59% (E, 24) 27,2 3,5 16,85 20,35 47,55 57% (16, F) 38,25 9,1 18,25 27,35 65,6 58% (16, D) 31,95 9,1 13,15 22,25 54,2 59% (24, D) 11,1 3,6 6,55 10,15 21,25 52% (24, F) 17,4 3,6 11,65 15,25 32,65 53% (E, C) 22,8 2 15,65 17,65 40,45 56% (F, C) 27,65 6,1 15,05 21,15 48,8 57% (D, C) 20,9 6,1 9,95 16,05 36,95 57% (D, E) 37,85 7,1 23,4 30,5 68,35 55% (F, E) 44,6 7,1 28,5 35,6 80,2 56% (16, E) 33,4 5 18,85 23,85 57,25 58% (24, E) 22,8 2 16,85 18,85 41,65 55% (F, 16) 41,95 10,6 18,25 28,85 70,8 59% (D, 16) 35,2 10,6 13,15 23,75 58,95 60% (D, 24) 15,05 5,1 6,55 11,65 26,7 56% (F, 24) 21,8 5,1 11,65 16,75 38,55 57% Table 13. Headway time effects for single track test network B. TABLES FOR DOUBLE AND SINGLE TRACK NETWORK 63 Linear Problem Path Double track Single track % Increase (A, B) 30,85 41,45 34% (A, C) 29,35 42 43% (A, E) 46,95 58,95 26% (A, F) 46,4 63,8 38% (A, D) 39,05 57,5 47% (A, 16) 24,7 34,85 41% (A, 24) 30,55 46,4 52% (B, C) 12,7 25,25 99% (B, E) 30,3 42,2 39% (B, F ) 29,75 47,05 58% (B, D) 22,4 40,75 82% (B, 16) 5,6 8,8 57% (B, 24) 13,9 29,65 113% (C, A) 31,8 42,05 32% (B, A) 32,5 41,2 27% (E, A) 47,55 60,2 27% (F, A) 45,75 65,05 42% (D, A) 40,85 58,3 43% (16, A) 26,9 32,4 20% (24, A) 31,8 43,25 36% (C, B) 13,5 25,55 89% (E, B) 29,25 43,7 49% (F, B) 27,45 48,55 77% (D, B) 22,55 41,8 85% (16, B) 6,15 6,6 7% (24, B) 13,5 26,75 98% (C, E) 21 21,6 3% (C, F ) 20,45 26,45 29% (C, D) 13,1 20,15 54% (E, D) 28,85 38,3 33% (E, F) 36,2 44,6 23% (E, 16) 23,1 37,1 61% (E, 24) 20,35 27,2 34% (16, F) 24,15 38,25 58% (16, D) 16,8 31,95 90% (24, D) 8,5 11,1 31% (24, F) 15,85 17,4 10% (E, C) 19,15 22,8 19% (F, C) 17,35 27,65 59% (D, C) 12,45 20,9 68% (D, E) 30,05 37,85 26% (F, E) 34,95 44,6 28% (16, E) 24,7 33,4 35% (24, E) 21 22,8 9% (F, 16) 21,3 41,95 97% (D, 16) 16,4 35,2 115% (D, 24) 9,05 15,05 66% (F, 24) 13,95 21,8 56% Table 14. Comparative Headway time between Table 13 and Table 14 64 B. TABLES FOR DOUBLE AND SINGLE TRACK NETWORK Network configuration Name Large Medium Name Large Medium Calafell 1−Breda 40 − Segur de Calafell 2−Gualba 41 − Cunit 3−Sant Celoni 42 − Cubelles 4A Palautordera 43 − V ilanova 5 1 Llinar del Vall`es 44 − Sitges 6 2 Cardedeu 45 − Garraf 7 3 Les Franqueses Granollers 46 − Platja de Castelldefels 8 4 Montmel´o 47 − Castelldefels 9 5 Mollet Sant Fost 48 − Gav`a 10 6 La Llagosta 49 − V iladecans 11 7 Montcada i Reixac 50 − Bellvitge 12 8 Sant Andreu Comtal 51 − Sants 13 10 Cornell`a 52 15 Passeig de Gr`acia 14 11 Sant Joan 53 14 El clot 15 −Sant Feliu 54 13 Pl. Catalunya 16 −El Papiol 55 − Arc de Triomf 17 −Castellbisbal 56 − Sant Adri`a 18 19 Gelida 58 − Badalona 19 20 Sant Sadurn´ı 59 − Montgat 20 −Lavern 60 − Montgat Nord 21 −La Granada 61 − El Masnou 22 21 V ilafranca 62 − Ocata 23 −Els Monjos 63 − Premi`a de Mar 24 22 L’Arbo¸c 64 − V ilassar de Mar 25 −El V endrell 65 − Cabrera de Mar 26 23 Rub´ı 66 − Matar´o 27 E Sant Cugat 67 D Sant Andreu de Llavaneres 28 −Cerdanyola del Vall`es 68 34 Caldes 29 −Santa Mar´ıa 69 33 Arenys de Mar 30 −Manresa 70 32 Canet de Mar 31 −Montcada Bifurcaci´o 71 26 Sant Pol del Mar 32 −Torre del Bar´o 72 25 Calella 33 −Montcada Ripollet 73 28 Pineda de Mar 34 −Santa Perp`etua 74 29 Santa Susanna 35 −Mollet Santa Rosa 75 30 Malgrat de Mar 36 −Parets del Vall`es 76 31 Blanes 37 −Granollers 77 F Tordera 38 −Les F ranqueses 78 − Hostatric 39 −La Garriga 79 − Table 15. Node numbers in the test network B. TABLES FOR DOUBLE AND SINGLE TRACK NETWORK 65 Network configuration Name Large Medium Figar´o 80 − Sant Mart´ı de Centelles 81 − Centelles 82 − Baleny`a 83 − Tona Seva 84 − Sabadell sud 85 − Sabadell centre 86 − Sabadell nord 87 − Terrassa Est. 88 − Terrassa 89 − Sant Miquel 90 − V iladecavalls 91 − V acarisses −Torr 92 − V acarisses 93 − Montserrat 94 − Sant Vicen¸c 95 − St. Vicen¸c de Calders A− Aeroport B − Estaci´o de Fran¸ca C− L0Hospitalet D 16 Sant Andreu E 24 Granollers Centre F − Ma¸canet-Massanes G− V IC H − Cerdanyola Universitat I − Manresa J − Martorell K − Molins de Rei L B El Prat N1 9 Node N2− Node N3 12 Node N4− Node N5− Node N6− Node N7 27 Node N8− Node N9− Table 16. Node numbers in the test network 72 C. CATALUNYA RODALIES NETWORK Arc Traffic Arc Traffic Arc Traffic Arc Traffic Arc Traffic (N2,13) 391 (38, G) 153 (8,7) 75 (29,28) 25 (86,85) 15 (N7, I) 390 (37,38) 153 (9,8) 75 (28,27) 25 (87,86) 15 (E, 72) 383 (36,37) 153 (N1, B) 68 (27,26) 25 (88,87) 15 (72,71) 383 (35,36) 153 (46, F) 68 (26,25) 25 (89,88) 15 (71, N6) 383 (34,35) 153 (45,46) 68 (25,24) 25 (90,89) 15 (N6,70) 371 (33,34) 153 (44,45) 68 (24,23) 25 (91,90) 15 (70,69) 371 (32,33) 153 (43,44) 68 (23,22) 25 (92,91) 15 (69,68) 371 (31,32) 153 (42,43) 68 (22,21) 25 (93,92) 15 (68, N7) 371 (30,31) 153 (41,42) 68 (21,20) 25 (94,93) 15 (N3,15) 318 (29,30) 153 (40,41) 68 (20,19) 25 (95,94) 15 (N9,48) 254 (28,29) 153 (39,40) 68 (19,18) 25 (J, 95) 15 (48,47) 254 (27,28) 153 (G, 39) 68 (18,15) 25 (65, A) 15 (47, F) 254 (26,27) 153 (9,10) 57 (15, N3) 25 (64,65) 15 (I, N7) 238 (25,26) 153 (10,11) 57 (D, 52) 20 (63,64) 15 (N4, N3) 218 (24,25) 153 (11, N1) 57 (52,53) 20 (62,63) 15 (13, N2) 215 (23,24) 153 (N2, D) 52 (53,54) 20 (61,62) 15 (N1,12) 210 (22,23) 153 (N3,17) 52 (54, L) 20 (60,61) 15 (12, N2) 210 (21,22) 153 (17,16) 52 (52, D) 20 (59,60) 15 (13,14) 210 (20,21) 153 (16,13) 52 (53,52) 20 (58,59) 15 (14, N4) 210 (19,20) 153 (56, K) 50 (54,53) 20 (55, N8) 15 (72, E) 183 (18,19) 153 (N8,56) 50 (L, 54) 20 (N6, N5) 12 (71,72) 183 (15,18) 153 (A, 1) 38 (N4,15) 19 (N5,73) 12 (N6,71) 183 (48, N9) 123 (1,2) 38 (58, K) 16 (73,74) 12 (D, N2) 181 (47,48) 123 (2,3) 38 (N7,85) 16 (74,75) 12 (17, N3) 181 (F, 47) 123 (3,4) 38 (85,86) 16 (75,76) 12 (16,17) 181 (15, N4) 100 (4,5) 38 (86,87) 16 (76,77) 12 (13,16) 181 (K, 56) 98 (5,6) 38 (87,88) 16 (77,78) 12 (15,51) 172 (56, N8) 98 (6,7) 38 (88,89) 16 (78,79) 12 (51,50) 172 (10,9) 95 (7,8) 38 (89,90) 16 (79,80) 12 (50,49) 172 (11,10) 95 (8,9) 38 (90,91) 16 (80,81) 12 (49, N9) 172 (N1,11) 95 (N3, C) 38 (91,92) 16 (81,82) 12 (70, N6) 171 (N3, N4) 91 (66, N8) 35 (92,93) 16 (82,83) 12 (69,70) 171 (51,15) 88 (67,66) 35 (93,94) 16 (83,84) 12 (68,69) 171 (50,51) 88 (I, 67) 35 (94,95) 16 (84, H) 12 (N7,68) 171 (49,50) 88 (N9, N5) 35 (95, J) 16 (N5, N6) 12 (12, N1) 163 (N9,49) 88 (N5, N7) 35 (A, 65) 16 (73, N5) 12 (N2,12) 163 (N8,66) 82 (N4, E) 28 (65,64) 16 (74,73) 12 (14,13) 163 (66,67) 82 (E, N4) 27 (64,63) 16 (75,74) 12 (N4,14) 163 (67, I) 82 (G, 38) 25 (63,62) 16 (76,75) 12 (F, 46) 153 (N5, N9) 82 (38,37) 25 (62,61) 16 (77,76) 12 (46,45) 153 (N7, N5) 82 (37,36) 25 (61,60) 16 (78,77) 12 (45,44) 153 (C, N3) 75 (36,35) 25 (60,59) 16 (79,78) 12 (44,43) 153 (1, A) 75 (35,34) 25 (59,58) 16 (80,79) 12 (43,42) 153 (2,1) 75 (34,33) 25 (N8,55) 16 (81,80) 12 (42,41) 153 (3,2) 75 (33,32) 25 (55, L) 16 (82,81) 12 (41,40) 153 (4,3) 75 (32,31) 25 (L, 55) 15 (83,82) 12 (40,39) 153 (5,4) 75 (31,30) 25 (K, 58) 15 (84,83) 12 (39, G) 153 (6,5) 75 (30,29) 25 (85, N7) 15 (H, 84) 12 (B, N1) 153 (7,6) 75 −0−0−0 Table 7. Maximum possible traffic by section C. CATALUNYA RODALIES NETWORK 73 Fig. 2. Segments with higher possible traffic of Catalunya Rodalies Network