Rapid transit network design and line planning

Programa de Doctorado “Matem´aticas” PhD Dissertation RAPID TRANSIT NETWORK DESIGN AND LINE PLANNING Author Alicia De Los Santos Pineda Supervisor Prof. Dr. Juan Antonio Mesa L´opez-Colmenar Co-supervisor Dr. Gilbert Laporte September 7, 2014 UNIVERSIDAD DE SEVILLA Departamento de Matem´ atica Aplicada II Dise˜no de Redes de Transporte R´apido y Planificaci´on de L´ıneas Rapid Transit Network Design and Line Planning Alicia De Los Santos Pineda Tesis doctoral A mi hija. A Antonio. A mis padres. Agradecimientos Durante los a˜nos en los que he realizado mi tesis son muchas las personas que me han prestado su ayuda y apoyo de forma desinteresada, a quienes quiero expresar mi gratitud. En primer lugar quiero agradecer el apoyo, dedicaci´on y ayuda que me han brindado mis directores de tesis Juan Antonio Mesa y Gilbert Laporte. Me gustar´ıa agradecer a Juan Antonio el haberme trasmitido su pasi´on por la investigaci´on, por sus sugerencias e ideas que tanto me han servido, por las interminables correcciones, por la confianza depositada en m´ı, y por su respaldo y amistad. No s´olo me ha ense˜nado a nivel profesional sino tambi´en a nivel personal, me ha mostrado que siempre hay un camino correcto para hacer las cosas, a afrontar los problemas con honestidad y a creer en m´ı misma. I am grateful to Gilbert for his enthusiasm and optimism, for his suggestions and ideas, for his time and dedication. I also wanted to thank his hospitality and support during my stay at the CIRRELT and HEC, providing all the facilities and resources required to develop my work. During that time I always felt at home and I have fond memories. Me gustar´ıa extender mi agradecimiento a los miembros del grupo de investigaci´on LOGRO y a los del proyecto de Excelencia TEP-5022 por el apoyo mostrado, muy especialmente a David Canca, por su disponibilidad, colaboraci´on y ayuda que tan desinteresadamente me ha brindado en los ´ultimos a˜nos, y, por supuesto, por su amistad. Tambi´en me gustar´ıa agradecer de manera especial a Federico Perea por todo lo que he aprendido trabajando con ´el, por su acogida y recibimiento en su departamento, por su amistad. Gracias al Departamento de Estad´ıstica e Investigaci´on Operativa Aplicadas y Calidad, de la Universitat Polit`ecnica de Val`encia por su acogida y los medios recibidos. I also want to thank Anita Sch¨oebel and Jonas Harbering for the welcome, for effective collaboration, support and resources received during my stay at the Institute for Numerical and Applied Mathematics at the University of G¨ottingen. A los miembros del Departamento de Matem´atica Aplicada II, de los que me gustar´ıa destacar aquellos con los que he tenido un especial trato. A Ana Beatriz S´anchez, por su amistad y apoyo con la que he compartido despacho en estos ´ultimos meses; ha sido un placer tenerte como compa˜nera. Es sorprendente que haya personas que, sin apenas conocerte, te est´en dando la mano y prestando su ayuda, como Nieves Jim´enez, quien desde el primer d´ıa se ofreci´o tan desinteresadamente a ayudarme con mis clases. A los miembros del grupo “caf´e”, con los que he tenido agradables desayunos. A MaCarmen S´anchez, por tener siempre hueco para atenderme y por su trato tan cordial. A todos los doctorandos/as y nuevos doctores; In´es Gallego, Soledad Fern´andez, Jos´e Manuel v Agradecimientos Gallardo y El´ısabeth Garc´ıa. No puedo olvidar a mis compa˜neras o, mejor dicho, amigas; El´ısabet Vela, M´onica Molina y Eva Barrena. Ha sido un placer tener como compa˜nera de despacho a una gran amiga como Eli, siempre atenta y sincera. Gracias por estar en todo momento. A M´onica por su apoyo y sobretodo por su amistad, no puedo olvidar lo buena amiga que ha sido en los momentos tan dif´ıciles que he pasado. A Eva, con la que he compartido despacho e incontables horas de trabajo. Gracias por escucharme, por tu humor, por tu generosidad y sobretodo, por esas risas que hemos echado. A Fernando Fern´andez por sus consejos, que tanto me han ayudado y por su opini´on siempre tan acertada. Gracias por describir con tanto entusiasmo ese viaje que tengo pendiente. A mis amigas Guadalupe, Amanda, Yoli y Madel Mar, que siempre han estado a mi lado a pesar de la distancia. Para terminar, el agradecimiento m´as profundo y sentido va para mi familia. A mi hija Laura, por todo el tiempo que me he perdido de ella, por soportar tantas horas sin la compa˜n´ıa de su madre, por tener que entender el tenerme al lado sin poder jugar o hacer planes juntas. Para la persona que me ha ense˜nado a ser quien soy, quien, a pesar de no poder estar f´ısicamente en estos ´ultimos a˜nos, siempre lo he sentido cerca, recordando las veces que me dec´ıa “t´u puedes, ya ver´as c´omo lo consigues, creo en t´ı”. A mi madre por todo el sacrificio y apoyo incondicional que me ha brindado; sin t´ı esto no hubiera sido posible, gracias por hacer que sea lo que hoy en d´ıa soy. A Antonio, por su paciencia, por tenderme su mano cada vez que he ca´ıdo, por sacrificarse tanto por m´ı, sobretodo, por darme ´animos usando ejemplos de f´utbol. Quisiera expresar tambi´en mi agradecimiento a mis hermanos y hermanas por todo lo mucho que me han apoyado y animado. Extiendo mi agradecimiento a mis suegros, siempre disponibles y atentos; sin vuestra ayuda no podr´ıa haber seguido adelante. vi Contents 3. Simultaneous frequency and capacity problem 79 3.1. Introduction................................... 79 3.2. Theproblem................................... 82 3.2.1. Data and notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.3. Uncapacitated problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 3.3.1. A mathematical programming program . . . . . . . . . . . . . . . . 84 3.3.2. Efficient approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.4. Capacitated problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.4.1. Two algorithms for our problem . . . . . . . . . . . . . . . . . . . . 101 3.5. Computational experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 104 3.5.1. Parameter setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.5.2. Computational comments . . . . . . . . . . . . . . . . . . . . . . . 109 3.6. Conclusions ...................................111 C. Computational results 113 C.0.1. Computational experiments for the uncapacitated problem . . . . . 113 C.0.2. Computational experiments for the capacitated problem . . . . . . 125 4. An adaptive neighborhood search heuristic for metro network design 135 4.1. Introduction...................................135 4.1.1. Literature review on algorithms for RTND . . . . . . . . . . . . . . 136 4.2. The mathematical programming program . . . . . . . . . . . . . . . . . . . 149 4.2.1. Data and notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 4.2.2. Variable .................................149 4.2.3. Constraints ...............................151 4.2.4. Efficient approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 4.3. The heuristic. Adaptive large neighborhood search heuristic . . . . . . . . 156 4.3.1. Initial solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 4.3.2. Operators ................................160 4.4. Computational results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 4.4.1. Instance generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 4.4.2. Parameters setting . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 4.4.3. Experiments on a small network . . . . . . . . . . . . . . . . . . . . 167 4.4.4. Experiments on a medium network . . . . . . . . . . . . . . . . . . 172 4.5. Conclusions ...................................174 ix Contents 5. Robust network design 179 5.1. Introduction...................................179 5.2. A mathematical programming model . . . . . . . . . . . . . . . . . . . . . 180 5.2.1. Data and notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 5.2.2. Variables.................................181 5.2.3. Objective function . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 5.2.4. Constraints ...............................182 5.2.5. Problem reformulation . . . . . . . . . . . . . . . . . . . . . . . . . 183 5.3. Robustness in rapid transit network design . . . . . . . . . . . . . . . . . . 184 5.3.1. Possible uncertainty sets . . . . . . . . . . . . . . . . . . . . . . . . 185 5.4. Robustness regarding uncertainty set U1...................186 5.5. Robustness regarding uncertainty set UΓ 1...................188 5.6. Lightrobustness.................................192 5.6.1. On the uncertainty U1.........................193 5.6.2. On the uncertainty UΓ 1,2.........................194 5.7. Conclusions and further work . . . . . . . . . . . . . . . . . . . . . . . . . 195 Conclusions 197 List of Figures 199 List of Tables 201 List of Algorithms 203 Bibliography 205 Index 215 Curriculum Vitae 217 x Chapter 1 Rapid transit networks: robustness and related measure assessment 1.1. Introduction In this chapter we will concentrate on describing and analyzing the different measures found in the literature in the transportation networks context. These measures can be oriented regarding to connectivity and robustness. The well-known Graph theory provides a natural way to represent networks as has been shown in the past. Graph theory was first developed to solve a transportation problem: Euler (1741) famously analyzed the Seven Bridges of K¨onigsberg and showed it was not possible to design a path crossing each bridge exactly once. The application of graph theory to road transportation systems emerged in the late 1950´s. It was mainly treated from the economics point of view. Garrison and Marble (1962, 1964) pioneered in the field by introducing three graph theory measures directly linked to network design (circuits α, degree of connectivity γand complexity β). At the same time, Kansky (1963) defined new indicators related to complexity and network specificities. The application of graph theory to urban transit systems emerged in the early 1980´s. More recently, Gattuso and Miriello (2005) have applied Garrison and Marble´s and Kansky´s indicators and others to 13 metro networks. The concept of robustness has been studied in both computer science and in engineering. According to the Glossary of the Institute of Electrical and Electronics Engineers 1 Chapter 1. Rapid transit networks: robustness and related measure assessment (IEEE) Geraci (1991), robustness can be defined as “the degree to which a system or component can function correctly in the presence of invalid inputs or stressful environmental conditions.” Gribble (2001) defined system robustness as “the ability of a system to continue to operate correctly across a wide range of operational conditions, and to fail gracefully outside of that range.” Ali et al. (2003) have considered an resource allocation mapping to be robust if it “guarantees the maintenance of certain desired system characteristics despite fluctuations in the behavior of its component parts or its environment”. In transportation systems, Immers et al. (2004) define the robustness as “the degree to which a system is capable of functioning according to its design specifications in the case of a serious disruptions”. According to Holmgren (2007): “Robustness signifies that the system will retain its system structure (function) intact (remain unchanged or nearly unchanged) when exposed to perturbations.” In Nagurney and Qiang (2009) transportation network robustness has also been quantified in presence of degradable links. In rapid transit system planning, robustness can be defined with respect to fluctuations in the input parameters, (i.e., the parameters are estimations), with respect to disturbances or disruptions (fails in links, drops in electrical power, trains breaking down, etc.), or with respect to integration with other subsequent planning phases. The topological configuration of associated to a transportation network may dramatically affect the system robustness. In this chapter we will concentrated on the robustness of a RTS and we will consider the concept of robustness proposed by Immers et al. (2004). So, the robustness will be treated respect to disturbances or disruptions in the rapid transit system. According to different aspects, we can define several measures. These measures can be used as objective functions in rapid transit network design and line planning problem. Moreover, robustness measures can be applied to determine where the network is more vulnerable and to compare different types networks. 1.1.1. Representation of transportation networks As mentioned, Graph Theory provides a natural way to represent networks. A graph G(N, E) is an abstract object defined by means of two sets: a set Nrepresenting a finite set of elements called nodes, and a set Eformed by pairs of elements in N. Let nand mbe the number of elements of Nand E, respectively. Depending on the kind of relationship defined in E, a graph is classified as undirected or directed graph. In an undirected graph G(N, E), each element of Ecalled edge, represents a connection between two different 2 1.1. Introduction nodes i, j of N. An edge is usually denoted by {i, j},eij or e. In a directed graph G(N, A) the order in each element of Ais an important aspect. An element (i, j) of A called arc, has an origin i∈Nand a destination j∈N. If an edge occurs several times in E, the copies of such edge are called parallel edges and the corresponding graph is known as multigraph. For determined situations, it is useful to associate numerical values (weights) to edges or nodes of an undirected or directed graph. The weighted graphs are usually called networks. The weights defined on edges (resp. arcs) can be expressed as a function ω:E→IR (resp. ω:A→IR ) which assigns a weight ω(e) (resp a weight ω(a)) to each edge e∈E(resp. arc a∈A). Depending on the context, these weights can describe different aspects such as cost, travel time, distance, capacity, strength of interaction, etc. From a network perspective, three different embedded and overlapping layers can be distinguished: •A first layer; the infrastructure network, in which only nodes (stations) and edges (links between adjacent stations) are considered. •A second layer; the line network, which represents the line set of a RTS. Each line is characterized by its itinerary and frequency. Note that this layer is defined on the first layer where trains run. In order to help passengers, this layer is usually shown at platforms by means of maps. •A third layer; the passenger system, in which the mobility patterns of users are taken into account. At this case, passengers travel according to the itinerary of lines given in the second layer. Two possible abstraction levels can be considered at the first layer: topological and metric. In Figure 1.1 we depict the different layers associated to metro of Seville. The structure of this chapter is as follows. In Section 1.2 we describe measures related to the infrastructure network of rapid transit systems. The Section 1.3 is devoted to define and analyze measures on weighted networks. We have presented measures defined on the above mentioned third layer in Section 1.4. In Section 1.5 we formally describe representations of a collective transportation network as well as connectivity and transferability measures. We will end with some conclusions. 3 Chapter 1. Rapid transit networks: robustness and related measure assessment (a) Metro network of Seville. (b) Topological level abstraction (first layer). (c) Metric level abstraction (first layer). (d) Line network (second layer). (e) Passenger routes (third layer). Figure 1.1.: Different layers associated to the metro network of Seville. 4 1.2. Measures in the infrastructure network 1.2. Measures in the infrastructure network Let G= (N, E) be a network representing the infrastructure network of a rapid transit system, where Nis the station set and Ethe set of links connecting adjacent stations. Let nand mbe the number of stations and edge in G, respectively. Over this level, we consider the topological distance dij between two nodes iand j, i.e., the number of edges that the shortest path between iand jcontains. Following sections are devoted to describe the different measures that can be found in the literature related to robustness measures of transportation networks in the topological context. 1.2.1. Mean connectivity The mean connectivity measure defined by Tainitier (1975), measures the probability of disconnecting a network after eliminating a set of edges. This measure can be useful in determining whether the connectivity of the network can be improved by adding some edges. Let ε(G) be the set formed by the m! possible orderings of the edge set and ǫbe an element of ε(G) representing a possible ordering of the edge set. Starting with a network G= (N, ∅), we will add edges in the order ǫuntil Gbecomes a connected network. Let ξ(ǫ) be the position of the edge in ǫthat makes connected the network. The mean connectivity of Gis defined as follows: M(G) = m−1 m!X ǫ∈ε(G) ξ(ǫ).(1.1) Tainitier proved that this measure satisfies several properties: 1. M(G′)≤ M(G), for G′= (N, E′) with E′⊂E. 2. λ(G)−1≤ M(G)≤m−n+ 1, where λ(G) is the edge-connectivity of G, i.e., is the smallest number of edges whose removal from Gresults in a non-connected network. For the sake of clarification, we show the following example. Example 1.2.1 The following Figure 1.2 represents a network with mean connectivity equal to 4. It can be note that ε(G)is formed by 120 elements as follows: •ǫ1= [(1,2),(2,3),(1,4),(2,4),(4,5)]. Note that ε(ǫ1) = 5, since we need to add all edges to G(N, ∅)to transform Gin a connected network. 5 Chapter 1. Rapid transit networks: robustness and related measure assessment Figure 1.2.: Computation of the mean connectivity for a sample network. •ǫ2= [(1,2),(2,3),(1,4),(4,5),(2,4)]. In this case, ε(ǫ2) = 4, since if we introduce the edges (1,2),(2,3),(1,4),(4,5) the network is connected. •ǫ3= [(1,2),(2,3),(2,4),(1,4),(4,5)],ε(ǫ3) = 5. As in ǫ1, we need to add all edges to transform Gin a connected network. •ǫ3= [(1,2),(2,3),(4,5),(2,4),(1,4)],ε(ǫ4) = 4. In this case the network is connected with 4edges. •. . . •ǫ120 = [(1,2),(2,3),(1,4),(2,4),(4,5)],ε(ǫ120) = 5. We need to insert all edges in G. 1.2.2. Pair disconnection measure An important measure proposed by Ng and Efstathiou (2006) to evaluate how the nodes of a network are connected is the network disconnectedness. This measure can be applied for both connected and non-connected networks. Concretely, if Gis a non-connected network, the network disconnectedness is the ratio between the number of pairs of unreachable nodes and the maximum number of possible pairs of nodes (n(n−1)/2). In contrast, if Gis connected, is interesting to study this ratio when a node or an edge is eliminated of G. The network disconnectedness is defined as pd(i) = pnd(i)/[n(n−1)/2], pd(e) = pnd(e)/[n(n−1)/2],(1.2) where pnd(i) denotes the number of unreachable node pairs when the node iis eliminated and pnd(e) is the number of unreachable node pairs when the edge eis interrupted. 6 1.2. Measures in the infrastructure network From this measure, it can be defined the worst (wc) and average (aver) case for pair disconnection measure. pdwc N(G) = max i∈Npd(i), pdwc E(G) = max e∈Epd(e) pdaver N(G) = 1 nX i∈N pd(i), pdaver E(G) = 1 mX e∈E pd(e) (1.3) We observe that this measure satisfies several desirable properties: it lies within a predefined range and satisfies a monotonicity property. Proposition 1.1 Let G= (N, E)be a connected network representing a rapid transit system. The pair disconnection measure holds the following properties. 1. 0≤pdwc N(G)≤(n−2)/n and 0≤pdwc E(G)≤1. The nearer to 0, better communicated the nodes are. 2. It is monotone non-decreasing in the sense that, if G′is a network obtained when adding a new edge to Gconnecting two nodes, we have that pdwc N(G′)≤pdwc N(G)and pdwc E(G′)≤pdwc E(G). Proof 1.2 1. Note that the denominator of pnd(i)and pnd(e)do not depended on i. Thus, max i∈Npd(i)=max i∈Npnd(i)/[n(n−1)/2]. The worst case respect to pnd(i)is obtained for a star network which has all nodes connected to a central node. If the central node iis eliminated, there not exists edge in G−i, i.e., G−i= (N\ {i},∅)in whose case pnd(i) = (n−1)(n−2)/2. Analogously, the worst case to pdE(G)is obtained in a graph with two nodes and one edge: N={i, j}, E ={e}, e ={i, j}, in whose case, pdwc E(G) = 1. The minimum value (best case) is reached in a completely connected network Kn with nnodes and all possible edges, in whose case, pdwc E(Kn) = 0 and pdwc N(G) = 0. 2. Adding a new edge in Gprovides a new couple of connected nodes, which implies that pd(i)and pd(e)are non-decreasing. 1.2.3. Toughness The toughness of a network was introduced by Chv´atal (2006). It measures the number of connected components in which the network can be decomposed by the failure of a 7 Chapter 1. Rapid transit networks: robustness and related measure assessment certain number of nodes. The toughness is the minimum ratio between the cardinality of a subset Sof Nand the number of connected components resulting after eliminating the set of nodes S: T(G) = min S⊂N,K(G−S)>1|S| K(G−S)(1.4) where K(G−S) is the number of connected components that Gis split into when removing S. The minimum value is 1/(n−1) obtained in a start network, i.e., a network in which all nodes are connected to a central and there not exists more connection between them. The maximum value can be ∞, for the case of a completely connected network. Now, we compute the toughness in network shown in Figure 1.3. Example 1.2.2 For the network of 1.3 the toughness is T(G) = min{1/2,1,1}= 1/2. In this network, the family of subset Sof Nis the follow: {{1},{2},{3},{4}, {1,2},{1,3},{1,4},{2,3},{2,4},{3,4}, {1,2,3},{1,2,4},{1,3,4},{2,3,4}}. For S1={3}, S2={1,3}and S3={2,3},K(G−Si) = 2. In other case, K(G−S) = 1. Figure 1.3.: Computation of the toughness for a sample network. 1.2.4. Diameter The diameter D(G) of a network is the longest shortest path between any pair of nodes of G. Dekker and Colbert (2004) and Ng and Efstathiou (2006) consider that this measure is interesting from robustness point of view when Gis a connected network. 8 1.3. Measures in the metric network •V(G′)≥V(G) if Gis obtained from G′by adding edges. •V(G) is computable in polynomial time respect to the number of nodes of G. In Criado et al. (2005) two vulnerability functions are defined as follows V1(G) = exp{M+−M− n+n−m−2 + 2 n}(1.13) and V2(G) = exp{σ n+n−m−2 + 2 n},(1.14) where M+= max{gr(i); i∈V}and M−= min{gr(i); i∈V}are the maximum and minimum degree of nodes, respectively, and, σ= ( 1 nPn i=1(gr(i)−2m/n)2)1/2is the standard deviation of the degree distribution. 1.3. Measures in the metric network In this section, we consider a metric l(e) in the infrastructure network G(N, E) associated to each edge e, representing; length, running time or generalized cost for traversing it. So, the distance between a pair of nodes is the sum, l(e), of edges that the shortest path between such nodes contains. 1.3.1. Diameter The diameter of a network e D(G) is the longest shortest path between any pair of nodes of G, that is, e D(G) = max i,j∈Ndij.(1.15) We observe two basic properties for comparing networks: it belongs to a predefined range, and it is monotone decreasing. Proposition 1.3 Let Gbe a infrastructure network with a metric. We have that: 1. maxe∈E(Kn)l(e)≤e D(G)≤d1n, where d1ndenotes the distance between first-node 1, and last-node n, in a chain graph formed by n-nodes. 2. It is monotone decreasing in the sense that, if G′is network obtained when adding a new edge to Gconnecting two nodes, we have that e D(G′)≤e D(G). 15 Chapter 1. Rapid transit networks: robustness and related measure assessment Proof 1.4 1. It is easy to note that the minimum value of e D(G)is reached for a completely connected network Kn. At this case, e D(N, Kn) = maxe∈E(Kn)l(e). Similarly, the maximum value is obtained for a chain graph with n-nodes. So, the maximum distance is reached for the shortest path between first and last node. 2. Adding a new edge in Gprovides a new couple of connected nodes, which does not increase e D(G). It is interesting to analyze networks when edges or nodes fail. It can be observed that if G−eis a connected network, its corresponding diameter increase is a non-negative number, i.e., ∆Ee D(G) = e D(G−e)−e D(G)≥0. In contrast, if G−eis a non-connected network, the diameter of G−eis infinity. Last case, we propose two alternative ways to obtain information on the connectivity of networks, as follows: 1. To analyze the connected components as in (1.5). 2. To introduce a penalty k∈N. If an edge or node failure is expected to be long enough, it is frequent that the transit company offers an alternative transportation mode, usually a bus, between the affected stations (see Figure 1.6). So, if G−eis a non-connected network, we modify the distance associated to e,l(e) by l(e) times k. This aspect can be extended to interruptions in nodes considering a penalty on all edges incident to such node. In order to illustrate this situation we consider what happened in the Barcelona metro in August 2008 (Figure 1.6). Due to the construction of the high-speed train tunnel Figure 1.6.: The affected line of Barcelona metro network. across Barcelona, the service in stations Diagonal and Verdaguer was interrupted during 16 1.3. Measures in the metric network a determined number of days. So, the blue line was fragmented into two parts and the stretch Hospital Clinic-Sagrada Familia was disabled. The operator provides two choices to the affected passengers: 1. an alternative route: transferring from the blue1 line L5 to the red line L1 at station Pla¸ca de Sants and transferring back to L5 at station Sagrera (or the other way around), 2. a bus between stations Hospital Clinic and Sagrada Familia (labelled as B Especial in the figure). 1.3.2. Average shortest distance The average shortest distance between any pair of nodes has been suggested for measuring robustness (see Ng and Efstathiou (2006)). This measure is defined as ASd(G) = 1 n(n−1)X i∈NX j∈N dij.(1.16) Similar to the characteristic path length, this measure may be ∞if the network is nonconnected. 1.3.3. Global and local Efficiency indicators Latora and Marchiori (2001, 2008) have defined the global and local efficiency for weighted networks. However, in this case, the efficiency belongs to a predefined range [0,∞). In order to compare different networks, this measure must be normalized. Let Kn be the completely connected graph . So, the global efficiency for a weighted network Gis defined as e Eglob(G) = Eglob(G) Eglob(Kn),(1.17) where Eglob(G) represents the global efficiency defined in Section (1.2), according to the length of each edge. Note that 0 ≤e Eglob(G)≤1, and that it measures how efficiently can passengers move in a global scale. Now, we will introduce the local efficiency indicator on this layer. For the purpose, let Gi= (Ni, Ei) be the neighbor subgraph of Gwith ki-nodes formed by all first neighbors 17 Chapter 1. Rapid transit networks: robustness and related measure assessment of node i. The local efficiency is defined as: e Eloc(G) = 1 nX i∈N Eglob(Gi) Eglob(Gideal i),(1.18) where Eglob(Gideal i) is the global efficiency of the ideal network Giideal which has kinodes and all possible edges. The local properties of Gcan be characterized by evaluating for each node i, the efficiency of its neighbor subgraph Gi= (Ni, Ei). 1.4. Measures for networks with demand patterns in operation In this section we will summarize the paper Evaluating passenger robustness in a rail transit network. Transportation Research Part C: Emerging Technologies, 20(1):34–46, 2012 by A. De Los Santos, G. Laporte, J.A. Mesa and F. Perea. First, we will describe the corresponding measures for networks with demand patterns. 1.4.1. Measures for networks with demand patterns In this section we propose a measure for the robustness of a network by calculating the overall travel time in the entire system when some link fails. Let t(e) denote the time required to traverse edge e. For the sake of simplicity it is assumed that only one type of train runs on the network. Let H= (hij) be the origin-destination matrix (denoted by OD) in the interval time that we are studying, where hij denotes the number of passengers going from ito j. It must be noted that our model assumes that this matrix is not affected by failures, that is, all passengers will keep travelling to their normal destination regardless of disruptions in the normal functioning of the network. Otherwise, the number of passengers missed could be a primary index or passenger loss of robustness. We will suppose that passengers choose their fastest alternative and that for each pair i, j there is only one shortest path on the network joining iand j(note that this is what happens in practice when dealing with real data). Therefore the flow of each edge is fe=X i,j∈N f(i,j) e,(1.19) 18 1.4. Measures for networks with demand patterns in operation where f(i,j) e=hij if the shortest path from ito jcontains edge eand zero otherwise. The maximum direct effect of an edge failure (without considering secondary delays) in the network service is observed on the edge having the maximum flow. Measures of robustness are the maximum and the average number of passengers affected by the disruption of the service in an edge: fEmax = max e∈Efe, fE=1 mX e∈E fe. If the disruption happens in station i, the number of passengers affected fiis the sum of those arriving to and departing from the station. Other cases (e.g. only passengers departing from the station) could also be considered. Since the interruption time affecting the passengers can be diverse, an indicator in terms of time loss for using alternative routes or even a different mode of transportation is a measure of the overall inconvenience to the passengers. The total travel time of the network G(N, E) is T(N, E) = X e∈E fet(e).(1.20) If there is a disruption in edge e, then the flow through edge ecan be larger because of the addition of passengers for which second shortest time route contains e. This flow will be denoted by fe(e). Then the total travel time is: TT(e) = Pe6=et(e)fe(e) and the difference: TTL(e) = TT(e)−TT, is the total time loss. Measures of robustness in terms of ridership time are TTL= max e∈ETTL(e), TTL =1 mX e∈E TTL(e). In a similar way the robustness of the network for disruptions in nodes can be measured. A related measure has recently been suggested for highway planning in Scott et al. (2006). In De-Los-Santos et al. (2012) we have performed a more complex analysis and we have considered secondary delays and different types of interruptions in the system. In order to evaluate the robustness of the network, we have computed its total travel time when one link fails, taking into account the possible changes in passenger routes and the delays induced by such changes. In order to measure robustness, measures relative to the overall time of a network when links fail are introduced for two different cases: without-bridging interruptions and with-bridging interruptions. In the first case, passengers either have to wait for the failure to be repaired or find an alternative route in the network, whereas in the second case, a bus service is provided between the affected stations and only the edge 19 Chapter 1. Rapid transit networks: robustness and related measure assessment failing link is disrupted. When an edge fails, other edges of the network may also be affected by having their flow increased or decreased. If ¯efails, let fe(¯e) be the new flow through edge e, and let fALT ¯ebe the number of passengers who decide to take the alternative mode provided by the operator to traverse edge ¯e, when this alternative mode is actually provided. Let ˜ t(¯e) be the sum of the travel time through edge ¯eplus the waiting time until the disruption is repaired. The effect of a without-bridging interruption of edge ¯eon network G(N, E) is defined as the ratio between the total travel time of the ideal completely network and the total travel time of network G(N, E) in case edge ¯esuffers a disruption without bridging : R((N, E),¯e) = T(Kn) DT ((N, E),¯e),(1.21) where DT ((N, E),¯e) = f¯e(¯e)˜ t(¯e) + X e6=¯e fe(¯e)t¯e(e), t¯e(e) is the time needed to traverse edge ewhen edge ¯eis interrupted. In the implementation of this index three models have been considered to calculate te(e). For more details we refers the reader to De-Los-Santos et al. (2012). Let t′(¯e) be the time needed to traverse edge ¯eby the alternative mode. The effect of a with-bridging interruption of edge ¯eon network G(N, E) is defined as the ratio between the total travel time of the ideal completely network and the total travel time of network G(N, E) if edge ¯esuffers a disruption with bridging (see De-Los-Santos et al. (2012) ): BR((N, E),¯e) = T(Kn) BDT((N, E),¯e),(1.22) where BDT((N, E),¯e) = fALT ¯et′(¯e) + X e6=¯e fe(¯e)t(e). The next proposition shows that both measures Rand BR satisfy three desirable properties. The first one is the scale-invariance, which ensures that the value of the index is not affected by the scale on which the number of passengers or the time are measured. The second one states that if the network becomes more dense the measure increase. The third property ensures that both measures are positive and cannot exceed 1. Proposition 1.5 Let G(N, E)be a network and let ¯e∈E. Then, the following properties 20 1.4. Measures for networks with demand patterns in operation hold. 1) Scale-Invariance: Both R((N, E),¯e)and BR((N, E),¯e)are invariant with respect to scale changes in the OD matrix and in travel times. 2) Monotonicity: Let E+=E∪ {e+}. Then BR((N, E+),¯e)≥BR((N, E),¯e)and R((N, E+),¯e)≥R((N, E),¯e). 3) Membership in (0,1]: 0< R((N, E),¯e)≤1and 0< BR((N, E),¯e)≤1. The detailed proofs are in De-Los-Santos et al. (2012). The measures: definition and properties Measures Rand BR, see (1.21) and (1.22), enable us to measure the effect of a disruption on a particular edge. In order to give a passenger robustness measure for a network, the following measures are introduced: •Measures of passenger robustness against without-bridging disruptions: δR(N, E) = T(Kn) max¯e∈EDT((N, E),¯e), µR(N, E) = T(Kn) P¯e∈EDT((N, E),¯e)/|E|. (1.23) In (1.23), δR(N, E) is the ratio between the total travel time of the ideal completely network and the travel time of the constructed network when the edge whose failure most increases this total travel time fails, whereas µR(N, E) includes in the denominator the average total travel time in case of failures. Note also that max¯e∈EDT((N, E),¯e) yields the edge that most affects the functioning of network (N, E), called critical edge, in the event of a without-bridging disruption. •Measures of passenger robustness against with-bridging disruptions: δBR(N, E) = T(Kn) max¯e∈EBDT((N, E),¯e), µBR(N, E) = T(Kn) P¯e∈EBDT((N, E),¯e)/|E|. (1.24) 21 Chapter 1. Rapid transit networks: robustness and related measure assessment The interpretations of δBR and µBR are similar to those of δR and µR. Again, max¯e∈EBDT((N, E),¯e) yields the critical edge of network (N, E) in the event of a with-bridging disruption. From now on, both δR and δBR may be called maximum measures, whereas µR and µBR are mean measures. Following the traditional terminology in the robustness literature (R´eka and Barab´asi (2002) ) the mean or µmeasures refer to robustness against random failures and the maximum or δmeasures to robustness against intentional attacks. Random failures and intentional attacks have been dealt with in Laporte et al. (2010) the latter being treated as a non-cooperative game theory application. The following theorem is a direct consequence of proposition 1.5 and of the definition of our passenger robustness measures in (1.23) and (1.24). It states that these are scaleinvariant, monotone and their values lie in (0,1]. Theorem 1.1 δR, µR, δBR and µBR satisfy the following properties: 1) scale-invariance, 2) monotonicity, and 3) membership in (0,1]. These properties allow us to use our measures to compare the passenger robustness of different networks. Definition 1.6 Let (N, E)and (N′, E′)be two transportation networks. Network (N, E) is more robust than network (N′, E′)against a without-bridging (respectively with-bridging) interruption if δR(N, E)≥δR(N′, E′)(respectively δBR(N, E)≥δBR(N′, E′)). Alternatively the mean measures can be also used to compare networks. 1.4.2. Measures in operations In De-Los-Santos et al. (2012), the previous model is extended introducing lines in the infrastructure network, assuming their origins, itineraries, stops, destinations and frequencies are fixed in periodic timetables. The network representing the lines is non-connected, but adding pedestrian edges corresponding to transfers in the stations makes it connected. A route going from an origin station to a destination station in the network can use edges of several lines as well as the edges of the transfers. The overall travel time is defined when a without-bridging (with-bridging) failure occurs on edge ¯e∈Eas the sum of DT((N, E),¯e) (BDT((N, E),¯e)), plus the new transfer times at stations, which results in Transfer Disruption Time and Transfer Bridging Disruption Time, respectively: 22 1.5. Transferability measures TrDT((∪Ni, E′),¯e) = DT((N, E),¯e) +X i∈VX j,k:i(lj),i(lk)∈Ni t(ei(lj, lk))(¯e)fei(lj,lk)(¯e), TrBDT ((∪Ni, E′),¯e) = BDT((N, E),¯e) +X i∈NX j,k:i(lj),i(lk)∈Ni t(ei(lj, lk))(¯e)fei(lj,lk)(¯e). (1.25) where t(ei(lj, lk)) is the sum of the time needed to change platforms at (possibly) different levels (from the stop of line ljto the stop of line lk), plus the average waiting time for line lkand fei(lj,lk)(¯e) is the flow through edge ei(lj, lk) (which represents the platform changes), if ¯e∈Efails. The detailed description appears in De-Los-Santos et al. (2012). From these overall travel times in case of disruptions, the measures of the passenger robustness of a network considering transfer times is defined, considering two types of interruptions. •Measures of passenger robustness against without-bridging interruptions: δTrR(∪Ni, E′) = T(Kn) max¯e∈ETrDT((∪Ni, E′),¯e), µTrR(∪Ni, E′) = T(Kn) P¯e∈ETrDT((∪Ni, E′),¯e)/|E|. (1.26) •Measures of passenger robustness against with-bridging disruptions: δTrBR(∪Ni, E′) = T(Kn) max¯e∈ETrBDT ((∪Ni, E′),¯e), µTrBR(∪Ni, E′) = T(Kn) P¯e∈ETrBDT((∪Ni, E′),¯e)/|E|. (1.27) 1.5. Transferability measures First, we will summarize the paper Analyzing connectivity in collective transportation line networks by means of hypergraphs. The European Physical Journal Special Topics, 215(1):93–108, 2013. by E. Barrena, A. De Los Santos, J.A. Mesa, F. Perea. as follows. In Barrena et al. (2013) we have analyzed the performance of a Collective Transportation Line Network (CTLN) with respect to the number of transfers. For this purpose, we 23 Chapter 1. Rapid transit networks: robustness and related measure assessment have represented the line network associated to a CTLN by means of hypergraphs and their associated graphs. Hypergraphs are the natural extension of graphs allowing edges (called hyperegdes) with more than two elements. This fact enables to describe a CTLN in a simplified way, representing each line as one hyperedge. Associated to a hypergraph, there exists two well-known graph: the primal and the linear graph. In this work, we consider three different ways to describe a CTLN: using the hypergraph, the linear graph and the linear multigraph (for more details, see Barrena et al. (2013)). On each structure, we have introduced topological connectivity indicators, which give a measure of how easy or hard it is to transfer from one line to another. Concretely, we have concentrated on the characteristic path length, the clustering coefficient, the local efficiency and the global efficiency. In order to define the clustering coefficient and the local and global efficiency on the hypergraph, we have used the primal graph associated to a hypergraph. In the next section the graphs and and the hypergraph associated to one CTLNs are introduced. 1.5.1. Representations of CTLNs by means of graph and hypergraphs Now, we present the formal description of all structures previously mentioned. We assume the existence of a set of stations, N={1,...,n}and a set of lines L= {ℓ1,...,ℓ|L|}in the CTLN. Each line ℓ∈ L is characterized by its set of nodes and itinerary. In this way, a CTLN G, can be defined as G= (N, L). Associate to this CTLN, we can define the following structures. •Transit hypergraph We call transit hypergraph to the hypergraph associated to G, which is defined as H= (N(H), E(H)), where N(H) = {1,...,n}is the node set of Gand the hyperedge set E(H) = {ℓ1,...,ℓ|L|}, contains subsets of N(H), each of them representing the set of stations that itinerary of each line contains. •The linear graph and linear multigraph The linear graph L(H) = (N(L(H)), E(L(H))) associated to hypergraph His a graph in which each hyperedge in His a node in L(H) and, the edge set E(L(H)) is the set of transfer edges connecting lines with intersections between them. This graph is assumed to be simple and, therefore, two nodes may be connected at most by an edge. 24 1.5. Transferability measures 1)/2edges. CP O(Lp(H)) is the fraction of these edges that actually exist and CP O(L(H)) is the average of CP O(Lp(H)), calculated over all nodes: CP O(L(H)) = 1 Pp∈N(L(H)) gpX p∈N(L(H)) CP O(Lp(H)), where CP O(Lp(H)) = number of edges in Lp(H) kp(kp−1)/2gp, where gpthe total number of passengers traversing line Lp. Note that CP O(L(H)) ∈[0,1]. We consider that if |Lp(H)|= 1, then CP O(Lp(H)) = 0. The clustering coefficient on the linear multigraph, in which the number of intersection nodes, that is, the number of possibilities to transfer between lines is taken into account, is defined as follows. Definition 1.19 Let LM p(H)be the neighbor multigraph associated to p∈N(LM(H)) and Umax a threshold that represents the maximum number of transfer nodes that can exist between two lines. If node phas kpneighbors, then LM p(H)will have at most Umax(kp(kp−1))/2multiedges. CM P O(LM p(H)) is the fraction of these edges that actually exist and the passenger-oriented clustering coefficient CM P O(LM(H)) on the linear multigraph LM(H)is the average of CM P O(LM p(H)), calculated over all nodes: CM P O(LM(H)) = 1 Pp∈N(LM(H)) gpX p∈N(LM(H)) CM P O(LM p(H)), where CM P O(LM p(H)) = number of edges in LM p(H) Umaxkp(kp−1)/2gp. Note that CM P O(LM(H)) ∈[0,1]. Passenger-oriented local and global efficiency Now, we will introduce the demand pattern on the global and local efficiency. These measures will give information on how efficiently passengers can move between stations. All measures here defined, satisfy three interesting properties: invariance to scale changes, staying within a predefined range of variation and monotonicity. We will define the global and local efficiency on L(H), but these concepts are also applicable on LM(H). 31 Chapter 1. Rapid transit networks: robustness and related measure assessment Definition 1.20 We define the passenger oriented global efficiency indicator of the linear graph L(H)as the average of the inverse of the passenger-oriented distances in L(H), that is, EP O glob(L(H)) = X p6=q ¯gpq gLdL(H) pq , where ¯gpq/gLis the proportion of passengers transferring from line ℓpto line ℓqover all passengers who transfer. Definition 1.21 We define the passenger-oriented local efficiency indicator of the linear graph L(H)as the average passenger oriented global efficiency of the subgraph Lp(H) = (Np, Ep), formed by all first neighbors of ℓpin L(H), where Np=N(Lp(H)) and Ep= E(Lp(H)). Mathematically, EP O loc (L(H)) = 1 Pp∈NgpX p∈N EP O glob(Lp(H))gp, where gpis the number of passengers traveling within line ℓp. 1.5.6. Passenger-oriented measures in H In this section we will introduce the characteristic path length, the clustering coefficient, the local efficiency and the global efficiency that evaluate the transferability of a CTLN considering passenger demand. Over this level we will have into account the passengers traveling between stations and not between lines. Characteristic path passenger-oriented length The characteristic path length on the hypergraph gives information on the average number of transfers of all passengers in a CTLN. Definition 1.22 We define the characteristic path passenger-oriented length of the transit hypergraph H, with |N(H)|>1, as the average passenger-oriented distance in H, i.e., LP O(H) = X i6=j dH ij gij g. It can be seen that two different line configuration associated to a same CTLN, will have different LP O(H). Note that now the importance of an edge is also given by the number of passengers crossing such edge. This measure is also an interesting objective in the design 32 1.5. Transferability measures of lines of a CTLN. So, if we consider the problem of designing a line network minimizing the characteristic path length, its solutions will tend to have better connections between lines with more passengers traveling between them. As in LP O(H), the characteristic path passenger-oriented length on His a natural extension of L(H) defined in Barrena et al. (2013) and it satisfies analogous properties. Clustering passenger-oriented coefficient As in Barrena et al. (2013), we will refer to the primal graph of a hypergraph to define the clustering coefficient on hypergraphs and all calculations will be based on the terminology of hypergraphs. Definition 1.23 Let GHbe primal graph associated to Hand and GHibe the subgraph formed by all first neighbors of i. The passenger-oriented clustering coefficient of GHis defined as follows: CP O(GH) = 1 Pi∈N(GH)˜giX i∈N(GH) CP O(GHi), where CP O(GHi) = number of edges in GHi ki(ki−1)/2˜gi, kibeing the number of nodes of GHiand ˜githe number of passengers traversing station i. Note that CP O(GH)∈[0,1]. The passenger-oriented clustering coefficient on the primal graph GHis a natural extension of C(GH) defined in Barrena et al. (2013). Passenger-oriented local and global efficiency The passenger-oriented local and global efficiency on the hypergraph Hmeasure how the passenger are communicated between the first neighbors of a station when it is eliminated. Definition 1.24 Let GHbe primal graph associated to Hand and GHibe the subgraph formed by all first neighbors of i. We define the passenger-oriented global efficiency indicator of GHas the average of the inverse of the passenger-oriented distances in H, that is, EP O glob(GH) = X i6=j gij gdH ij , 33 Chapter 1. Rapid transit networks: robustness and related measure assessment where gij/gis the proportion of passengers travelling from line ito line jover all passengers who travel. Definition 1.25 Let GHbe primal graph associated to Hand GHibe the subgraph formed by all first neighbors of i. We define the passenger-oriented local efficiency indicator of H as the average passenger-oriented global efficiency of the subgraph GHi, as EP O loc (GH) = 1 Pi∈N(H)˜giX i∈N(H) EP O glob(H) ˜gi, ˜githe number of passengers traversing station i. 1.6. Conclusions In this chapter we have reviewed the existing literature on the rapid transit network design measures. We have represented a transportation network by means of Graph and Hypergraph theory. We have described measures found on transportation network in the topological context, measures in operations and with demand patterns as well as transferability measures. On these measures, we have analyzed properties and we have included some extensions. 34 Chapter 2 Modelling the rapid transit network design problem 2.1. Introduction In recent years, much effort has been devoted to the construction, improvement or extension of rapid transit networks. This phenomenon is motivated by the increase in travel demand, traffic congestion, the growing length of trips and by the necessity of reducing energy consumption and pollution (Gendreau et al. (1995)). It is important to pay special attention to the investment needed in the building process of new networks or new lines due to their very high cost and because these infrastructures cannot easily be modified within a short time horizon. Due to its complexity, the railway planning process has traditionally been decomposed into a succession of stages, namely, network design, line design, timetabling, rolling stock, and personnel planning (Guihaire and Hao (2008)). In this chapter we will focus on rapid transit network design, line planning and rolling stock. The main novelty of this chapter is the consideration of a general model that contains as particular cases, all models treated in the literature related with this problem. Another important aspect is the integration of the strategic and tactical phases into an optimization model that determines the location of stations and their connections, a set of lines, each one formed by two different terminal stations and a sequence of intermediate stations (an itinerary), the frequency of each line and the capacity of vehicles. Moreover, several aspects related 35 Chapter 2. Modelling the rapid transit network design problem to rolling stock and personnel planning as well as a long term public economic support for a network profitable operation are also considered as key factors in the network design problem. From now on, we will call to the network that is being designed the rapid transit system (RTS). In order to model the problem realistically, it is appropriate to assume that there exists a different mode of transportation competing with the RTS (e.g. private car, bus, bicycle) which we will call the alternative mode (ALT). Note that, although we have only considered one mode of transport, this aspect can be easily extended to the case of several competing transportation modes. We assume the trains used to operate a determined line are identical, that is, all trains employed for a line carry the same number of vehicles. Without loss of generality, we suppose a train is formed by a locomotive and several passenger carriages. The number of trains needed for each line is determined by their frequency and cycle time (for more details, see Section 2.3.3). The main input data that we are considering are the underlying network, that is, the potential location for the stations and their connections, the distance matrix between pairs of stations of the underlying network, the travel patterns and the building, capacity and operational related costs. The remainder of this chapter is structured as follows. In order to properly describe the main characteristics of the models in the literature, we need some notation valid for all models (see Appendix A). In Section 5.2.2 we introduce the variables needed in order to formulate the problem and discuss the different considered objectives. Section 2.3 presents a general model for the rapid transit network design problem. In Section 2.4 we review the literature related to rapid transit network design. Finally, this chapter ends with a summary table containing the main characteristics of each paper analyzed earlier, and with some conclusions. 2.2. Objectives In this section we discuss different objective functions that can be found in the literature related to the rapid transit network design problem and line planning problem. The general objective in any transport system is to improve the population mobility by providing shorter travel times (Gendreau et al. (1995)). However, different perspectives are taken into account in the transportation network design and line planning. Vuchic (2005), Ceder (2007), Van Nes (2002) and Van Nes and Bovy (2000) state that the objectives for the transportation network design and line planning can be classified into three categories depending on the point of view that is considered. From the passenger’s perspective the 36 2.2. Objectives main characteristics that any transportation network must have in order to be attractive are the service offered, spending as little time as possible to reach the destination, direct connections, and the price of the service. Moreover, the operator wants to minimize costs and maximize revenues and, at the same time, provide a good service level to attract passengers. The community is the third point of view. It wants to find a service of quality for the traveler in order to improve the population’s mobility. Moreover, an equilibrium between the preferences of the passengers and those of the operators is implicity contemplated. Therefore, the objectives for the transport network design are classified into three perspectives: community, passengers and operator, which we describe below. The following criteria can be classified into the preferences of the community: •Area coverage The area coverage (Vuchic (2005)) is defined by computing population of the served area as a percentage of the total urban area population. In Guihaire and Hao (2008), the area coverage is defined as the percentage of the estimated demand that can be served by the rapid transit. •Trip coverage The number of passengers using the transportation system being build is a common objective in the network design and line planning. This number is usually estimated according to OD matrices and travel patterns. •Social welfare The concept of social welfare is defined as the sum of consumer surplus and producer surplus (see Van Nes (2002)) . In Jansson (1996) consumer surplus are the benefits of all travellers who use the public transport since that the travel time is lower than their maximum acceptable travel time. The producer surplus is equivalent to profit. Note that the component expressing the preferences of the passengers is the consumer surplus and the preferences of the operator is the producer surplus. The consumer surplus incorporates the sensitivity of the demand to changes in the given network. So, the level of demand will depend on the quality of the services offered: travel times, comfort, transfers, etc. •Service quality/passenger attraction A common characteristic between service requirements of passengers and operator is to provide a service of high quality in order to attract as many passengers as 37 Chapter 2. Modelling the rapid transit network design problem possible, representing enough mobility capacity and reducing the traffic congestion (see Gendreau et al. (1995)). •System cost The total cost of the system is defined by means of the investments, building and operating costs (Gendreau et al. (1995), Van Nes (2002), Gallo et al. (2011)). In order to guarantee a good service quality, passengers prefer the following characteristics: •Short travel time The travel time can be broken down into the access time from the origin to the station and into the station, waiting time to take first train in the origin station, riding time, transfer time between platforms and the time to get the destination since alighting the train. This factor is very important to attract passengers since time has a direct influence on modal split. •Low number of transfers/direct trips The number of transfers is also a criterion for the passengers. Users do not like transfers in order to get to the destination station. In general, a passenger uses rapid transit system if no more than two transfers are required (see Guan et al. (2006)). Travelers prefer direct connections in order to complete their trip. •Good service frequency High frequency is a very important aspect for passengers; a slow service frequency implies long waiting times (see Gendreau et al. (1995)). •Reasonable fares Travel costs represent a composite measure of different factors such as travel time, monetary cost and comfort. Transit passengers accept fares depending on the offered service. From the operator’s point of view the system designed must operate efficiently, both at the economical and technical levels. Thereby, the operator considers several factors, some of which are contrary to the preferences of the passengers. The following characteristics can be stated as the operator’s point of view: 38 2.3. A mathematical programming model •Investment costs Investment costs are the costs of building the physical network. It depends on the total length as well as the characteristics of the network (see Van Nes (2002), Vuchic (2005)). •Operating costs Operating costs are usually expressed defining two type of costs: fixed and variable costs (see Van Nes (2002), Vuchic (2005)). The fixed operating cost includes costs such as maintenance cost and overheads. The variable cost includes rolling stock operation and personnel costs. •Fleet acquisition cost It represents the investment cost of the rolling stock. •Revenues The revenue for a rapid transit system is determined by the fares paid by the travelers. It can be observed that if the fare is the same for all passengers independently of the length of their trips, this objective is proportional to the passenger attraction. By contrast, if the fare depends on the distance, the revenue is oriented towards the operator. •Profit The net profit of the rapid transit network is expressed as the difference between revenue and total cost in terms of monetary units (see Li et al. (2011b)). From the point of view of operators, the total revenue is the income derived from the passengers who use the rapid transit system. Note that the classification here presented is not strict. In fact, some objectives can be included into several perspectives at the same time and, therefore, depending on the author’s point of view the classification can be different. 2.3. A mathematical programming model We present a mathematical model that generalizes all models already considered in the literature. In the review we have focused on papers that deal with the rapid transit network design general problem. 39 Chapter 2. Modelling the rapid transit network design problem As mentioned, the main innovative point of our model with respect to current literature is the simultaneous treatment of network design, line planning and fleet acquisition problems. Moreover, line frequency and capacity are also considered, as well as several aspects related to rolling stock and personnel planning. Our general network design model also includes passenger transfers between the lines, flow conservation, an upper bound on costs, as well as location and allocation constraints, and a competing mode. As stated in the introduction, it is assumed that the mobility patterns are known but the demand captured by the RTS may vary according to the offered service (Kepaptsoglou and Karlaftis (2009), Ranjbari et al. (2011)). The main input data are the underlying network, that is, the potential location for the stations and their connections, the distance matrix between pairs of stations of the underlying network, the travel patterns as well as train capacities, building costs and operational related costs. We describe the infrastructure network by means of graphs, where stations are nodes and the links between stations are edges. The model uses the notation introduced in Section 5.2.1 and the variables defined in Section 5.2.2. The objective function considered in the model is a general function that combines all perspectives defined above. 2.3.1. Data and notation We assume the existence of a set N={1,...,n}of nodes representing potential sites for locating stations and a set A⊆N×Nof potential arcs. Each arc between two potential stations iand jwill be represented by a= (i, j). Let E={{i, j}:i, j ∈ N, i < j, (i, j) or (j, i)∈A}be a set of edges linking the elements of N(potential rail stretches or sections). Let GE=G(N, E) be the graph which represents the underlying network (from which sections and stations of lines are to be selected). For each node i,N(i) = {j∈N:{i, j} ∈ E}denotes the set of adjacent nodes to i. Let dij =dji be the length of edge {i, j} ∈ E. The parameter dij can also represent the time as well as the generalized cost needed to traverse edge {i, j}. Times can be transformed into distances by using the parameter λ, which represents the average distance traveled by a train in a hour (commercial speed). The undirected graph GE′=G(N, E′), represents the competing (private car, bus, etc.) mode network. The nodes are assumed to coincide with those of the rapid transit mode: they could represent origin or destination of the aggregated demands; however, edges are possibly different. Let d′ ij be the traversing time of edge {i, j} ∈ E′by the competing mode. Therefore, the whole network is a graph G=G(N, A′), where A′=E∪E′. In this work we assume all travels are concentrated at stations of the system, that is, the centroid of each transportation area is assumed to be 40 2.3. A mathematical programming model and carriages as follows: zF AC =X ℓ∈L Bℓ(Iloc +Icarr ·δℓ).(2.9) We can formulate the perspective’s community (zP C ) by combining the objectives above: zP C =ξc 1·zTrC +ξc 2·zSTT +ξc 3·zSC,(2.10) where ξc 1, ξc 2, ξc 3∈IR, which allows to the objective function to be homogenized. Concretely, these parameters allow us express all terms of (2.10) at same unit. For instance, Gallo et al. (2011) introduced several parameters representing the perceived value of time in order to transform the objective function into monetary terms. Secondly, we will consider the point of view of passengers by considering the following terms: •The total travel time (see zSTT ) •Direct trip The number of direct trips is measured by the following expression: zDT =X ℓ∈LX w∈W bℓ w,(2.11) where bℓ wis a variable explicitly defined as bℓ w=X ws∈ℓX wt∈ℓ,ws6=wt ¯ fRTS wgw. A drawback of this objective is that it may yield a network with few transfers but with long travel times when it is used alone. If we can compute other aspects zothers such as security, comfort, fares, etc, the objective function that generalizes the preferences of the users is the following: zP P =ξp 1zSTT +ξp 2zDT +ξp 3zothers,(2.12) where ξp 1, ξp 2, ξp 3∈IR, which allows to the objective function to be homogenized. 47 Chapter 2. Modelling the rapid transit network design problem Finally, we consider the perspectives’s operator. The main objective for the operator is the net profit of the public network (Li et al. (2011b)). This profit is expressed as the difference between revenue and total cost in terms of monetary units over a planning horizon. From the point of view of operators, the total revenue for the ˆρyears is computed as the number of passengers who use the PTN during the planning horizon, times the passenger fare η, plus the passenger subsidy, which is the same for all passengers independently of the length of their trips. So, the revenue is mathematically expressed as zREV = (η+τ)ρˆρX w∈W gw¯ fRTS w.(2.13) Specifically, the net profit is computed as the difference between the revenue and the system cost. zNET =zREV −zSC.(2.14) We are now able to describe a general objective function which generalize all perspectives. Table 2.2 shows the different terms which appears at each perspective definition and Table 2.1 presents some of possible combination of terms that can appear at each perspective. objective perspective zTrC zBC zOC zF AC zRTT zAT T zDT zothers zREV z1 Community X Passenger X Operator X X X X z2 Community X Passenger X Operator X X X X z3 Community X X X Passenger X Operator X z4 Community X Passenger X Operator X X X z5 Community X X Passenger X Operator X X X Table 2.1.: Possible combinations of terms to define objective functions. 48 2.3. A mathematical programming model zTrC zBC zOC zF AC zSTT zDT zothers zREV Community X X X X X Passenger X X X Operator X X X X Table 2.2.: Terms at each perspective. 2.3.4. Constraints We will group the constraints according to their aims as follows. •Budget constraints X {i,j}∈E cijxij +X i∈N ciyi≤Cmax.(2.15) •Design constraints xℓ ij ≤yℓ i,{i, j} ∈ E, i < j, ℓ ∈ L (2.16) xℓ ij ≤yℓ j,{i, j} ∈ E, i < j, ℓ ∈ L (2.17) xℓ ij =xℓ ji,{i, j} ∈ E, i < j, ℓ ∈ L (2.18) yi≤X ℓ∈L yℓ i, i ∈N(2.19) yℓ i≤yi, i ∈N, ℓ ∈ L (2.20) xij ≤X ℓ∈L xℓ ij,{i, j} ∈ E, i < j (2.21) X ℓ∈L xℓ ij ≤γxij,{i, j} ∈ E, i < j (2.22) X j∈N(i) xℓ ij ≤2, i ∈N, ℓ ∈ L (2.23) hℓ+X {i,j}∈E xℓ ij =X i∈N yℓ i, ℓ ∈ L (2.24) X i∈BX j∈B xℓ ij ≤ |B| − 1, B ⊆N, |B| ≥ 2, ℓ ∈ L (2.25) ℓminhℓ≤length(ℓ)≤ℓmaxhℓ, ℓ ∈ L.(2.26) 49 Chapter 2. Modelling the rapid transit network design problem •Demand conservation constraints X ℓ∈L X j∈N(ws) fwℓ wsj=¯ fRTS w, w = (ws, wt)∈W(2.27) X ℓ∈L X i∈N(wt) fwℓ iwt=¯ fRTS w, w = (ws, wt)∈W(2.28) X i∈N(k) fwℓ ik −X ℓ′∈L\{ℓ} fwℓℓ′ k+X ℓ′∈L\{ℓ} fwℓ′ℓ k−X j∈N(k) fwℓ kj = 0,(2.29) ℓ∈ L, w = (ws, wt)∈W, k 6={ws, wt}, k ∈N. •Location-allocation constraints fwℓ ij ≤xℓ ij, w ∈W, ℓ ∈ L,{i, j} ∈ E, i < j (2.30) fwℓℓ′ i≤yℓ i, w ∈W, ℓ, ℓ′∈ L, ℓ 6=ℓ′, i ∈N(2.31) fwℓℓ′ i≤yℓ′ i, w ∈W, ℓ, ℓ′∈ L, ℓ 6=ℓ′, i ∈N. (2.32) •Splitting demand constraints Many approaches assign passengers to the different modes according to binary variables (see Laporte et al. (2010, 2012)). Concretely, the demand is split into the railway system and the alternative mode according to the generalized costs of each mode and binary variables. Another approach, more realistic but computationally less efficient, is the assignment by logit type functions (Ort´uzar and Willumsem (1990)). Some works such as Mar´ın and Garc´ıa-R´odenas (2009) and Perea et al. (2014) use logit model to simulate the modal split. This approach estimates the proportion of users assigned to each mode for each origin-destination pair in a continuous way. So, the number of passengers who use a transport system varies depending on the service offered. For this function, two positive real parameters αand βfor each transport mode are needed. The parameter αsimulates the market share for each mode and βweights the importance of each mode (Mar´ın and Garc´ıa-R´odenas (2009)). We consider, αRAIL for the railway mode and αALT in the alternative mode. If we want to give the same importance to both modes, we fix the parameter βindependent of the modes as in Garc´ıa-R´odenas et al. (2006). Let us denote α=αALT −αRAIL. Therefore, the proportion of OD pair wusing the railway mode is 50 2.3. A mathematical programming model fRTS w=1 1 + e(α−β(uALT w−uRT S w)) , w ∈W(2.33) ¯ fRTS w≤fRTS w, w ∈W. (2.34) •Capacity constraints X w∈W fwℓ ij gw≤ψℓ·δℓ·Θ, ℓ ∈ L,{i, j} ∈ E. (2.35) •Binary constraints xij, yi, xℓ ij, yℓ i, hℓ, bℓ w∈ {0,1}, i ∈N, {i, j} ∈ E, ℓ ∈ L, w ∈W. •Integrality constraints δℓ∈ {δmin,...,δmax}, ℓ ∈ L ψℓ∈ {ψmin,...,ψmax}, ℓ ∈ L. •Bounding constraints fwℓ ij , fwℓ i, fwℓℓ′ i,¯ fRTS w, fRT S w, fALT w∈[0,1], i∈N, {i, j} ∈ E, ℓ, ℓ′∈ L, w ∈W. An upper bound on the total cost of the overall network is imposed in Constraint (2.15). Constraints (2.16) and (2.17) guarantee that an edge is selected to be built in the RTS only if its incident nodes are also selected. In order to allow edges to be used in both directions Constraint (2.18) must be considered. Constraints (2.19) and (2.20) force that a station iis built if and only if it is already included in the itinerary of a line. Constraints (2.21) impose that if an edge is built, then there exists a line that uses it. Constraints (2.22) define an upper bound on the number of lines that can traverse an edge. Constraints (2.23) force each node to have at most two associated edges of each line. Constraints (2.24) and (2.25) guarantee that lines are connected and do not contain cyclic subgraphs. Constraint (2.26) imposes that each line has at least ℓmin length units and at most ℓmax length units. Constraints (2.27)–(2.29) is flow conservation for each OD pair including transfers between lines. In order to allow the flow corresponding of each OD pair to 51 Chapter 2. Modelling the rapid transit network design problem use an edge of a line ℓonly if this edge belongs to ℓ, we impose constraints (2.30). In order to ensure that a transfer between two lines is made at node ionly if iis built for both lines, we include Constraints (2.31) and (2.32). The modal split is described by means of Constraints (2.33) and (2.34). Constraints (2.35) impose a limits on the maximum number of passengers that each line can transport per hour. The character of the variables as imposed in the remaining constraints. 2.4. Special cases We describe the main papers that deal with problems related to rapid transit network design problem and line planning as well as differences between the general model defined in Section 2.3 and each paper. Our survey is structured as follows. We classify papers into two categories: network design and network design with robustness aspect. In the network design category, we start with the first paper that describes the transit network design as an optimization problem (Laporte et al. (2007)), followed by an extension of the previous paper taking into account transfers between lines (see Garc´ıa-R´odenas et al. (2006)). Later, Guan et al. (2006) described a model combining the line planning problem and the passenger line assignment. In Section 2.4.4 a model which includes the incorporation of a variable number of lines is introduced. The main contributions of Mar´ın and Garc´ıa-R´odenas (2009) are the inclusion of location constraints based on minimizing the number of routing intersections and the consideration of a logit model, which improves the simulation of the demand behavior. Mar´ın and Jaramillo (2008) presented a model for the multi-period capacity expansion problem. The next model considered is that by Escudero and Mu˜noz (2009) which introduces a modification in the Mar´ın (2007) model in order to allow circular lines. However, the model does not guarantee that lines are connected paths. Mar´ın and Jaramillo (2009) proposes a Benders decomposition algorithm in order to improve the computational time of the model proposed for the rapid transit network design problem. In Section 2.4.9 a model based on transit routes is described by Kermanshahi et al. (2010). A bi-objective model which simultaneously minimizes the network design cost and maximizes origin-destination traffic capture is presented in Guti´errez-Jarpa et al. (2013). In order to model with robustness aspects, Laporte et al. (2010) presented a model using game theory. Later, Laporte et al. (2012) proposed a model for the design of a robust rapid transit network regarding to by introducing redundant capacity into the system. In Garc´ıa-Archilla et al. (2013) an integer linear programming model for the design of railway network infrastructure as well as their cor- 52 2.4. Special cases responding robust and probabilistic version are introduced. Finally, Cadarso and Mar´ın (2012) introduce recoverable robustness in the model proposed in Mar´ın and Jaramillo (2009). The rest of this section is dedicated to the preparation of a summary table which contains the main characteristics of the network design models above mentioned. 2.4.1. An integrated methodology for the rapid transit network design problem The main aim of Laporte et al. (2007) is to integrate the steps of network design and line planning into an optimization process. The authors introduce these steps by considering three stages. The first stage consists of selecting key nodes, i.e., main sites are considered as potential stations in rapid transit network which is being designed. The second stage is to design the core network, where the selected stations in the first stage are connected with a small number of alignments maximizing the trip coverage and the third named locating secondary stations, consists of determining the location of the rest of stations. So, an integer programming model is formulated according to the mode and route user decisions. Roth et al. (2012) have later studied the temporal evolution of the structure of the world’s subway networks. They showed that this structure converges to the same shape as that proposed in the work of Laporte et al. (2007): a core with branches radiating from it. We will now show the objective function used in this model and will comment differences with respect to the general model introduced in Section 2.3. Objective function and constraints The objective is the trip coverage. As in the general model, constraints are classified by groups taking into accounts their aims. •Budget constraints In this model, budget constraints impose a lower and upper bound on the cost of each line and on the overall network. •Design forcing The terminal stations for each line are selected from a set of potential stations. So, constraints (2.16)–(2.25) are modified by constrains where origins and destinations 53 Chapter 2. Modelling the rapid transit network design problem are fixed. •Routing demand conservation constraints In the model, the flow variables are binaries. The authors do not take into account transfers between trains of different lines and the flow is expressed without considering lines (that is, variables such as fwℓℓ′ iand fwℓ ij do not appear in the model). •Location-allocation constraints Due to the fact that flow variables are binary variables, constraints (2.30)–(2.32) are modified. In order to assign demand on an edge if it is previously built, flow and construction variables appear in constraints. •Splitting demand constraints These constraints guarantee that all demand of an OD pair is assigned to RTS mode if the RTS cost is less than the corresponding to the alternative mode. 2.4.2. Analysis of the parameters of transfers in rapid transit network design Although the paper Garc´ıa-R´odenas et al. (2006) was published on-line before than Laporte et al. (2007), the chronological order must be the contrary since Garc´ıa-R´odenas et al. (2006) is a continuation of Laporte et al. (2007). Garc´ıa-R´odenas et al. (2006) propose a new design model which includes transfers between lines. The objective function considered is the trip coverage taking into account a different transport mode competing with the public mode. The potential location for the stations, the distance matrix between pairs of nodes and the travel patterns are known. In the model, users choose the most convenient route (and mode) in order to carry out their trips. The problem they are concerned with is to choose a number of lines covering as much as possible the travel demand between potential stations, subject to different constraints. The authors have studied different values of the parameters such as transfer costs and line frequency. The proposed model has been tested on a network with six nodes. We now outline the differences between the proposed model in this paper and the general model. 54 2.4. Special cases Objective function and constraints The objective function is the trip coverage and differences with respect to general model are the followings •Budget constraints The construction cost associated to stations is not considered. A lower and upper bound on the line cost as well as on the overall network are imposed. •Design forcing The terminal stations for each line are selected in a set of potential stations. So, the constraints (2.16)–(2.25) are modified by constrains where a set of origins and destinations are fixed. •Routing demand conservation constraints The considered flow variables are binary. The authors do not take into account transfers between trains of different lines and the flow is expressed without considering lines (that is, variables such as fwℓℓ′ iand fwℓ ij do not appear in the model). •Location-allocation constraints Due to the fact that the variables are binary, constraints (2.30)–(2.32) are modified at the same manner as Laporte et al. (2007). •Splitting demand constraints These constraints guarantee that all demand of an OD pair is assigned to RTS mode if its corresponding cost is less than the corresponding to the alternative mode. •Transfer constraints The authors consider specific constraints to include transfers between trains of different lines. However, in the general model, these constraints are introduced according to the flow conservation constraints. To be more precise, variables in regard to transfer appear when balances between flows are done. 2.4.3. Simultaneous optimization of transit line configuration and passenger line assignment Guan et al. (2006) presented a model in which the line planning problem and the passenger line assignment are simultaneously considered. The model was formulated as a 55 Chapter 2. Modelling the rapid transit network design problem linear binary integer program. The authors first described both problems separately and then they formulated a model combining both problems. The line planning problem defined consists of finding a set of lines (of a given line pool) that connects all stations of a given infrastructure network, minimizing the total length of all lines. The passenger line assignment was described by means of paths (sequences of edges and nodes that connects origin-destination pairs). A set of feasible paths for each origin-destination pair is predefined and determined by the k-shortest path method according to in-vehicle travel time. Later, a penalty based on the expected time to transfer is added, for each transfer, to the in-vehicle time previously computed. To integrate both problems, the objective function is defined as a convex combination of the proposed at each problem: the total length of all transit length (for the line planning problem) and total passenger in-vehicle travel time and total number of passenger transfers (for the passenger line assignment). Constraints The constraints are as follows: •Budget constraints This group of constraints are not considered since that costs are included on the objective function. •Design forcing Due to the fact that the infrastructure network is already given, constraints such as (2.16)–(2.26) are not presented. •Routing demand conservation constraints This group of constraints is not defined. •Capacity constraints The authors assume the capacity on each arc as well as the frequency of each line are given. •Splitting demand constraints In this case, passengers are assigned on paths according to travel times. 56 2.4. Special cases •Splitting demand constraints By means of binary variables, passengers are assigned to each transport mode according to travel times and transfers. 2.4.10. Rapid transit network design for optimal cost and origin destination demand capture Guti´errez-Jarpa et al. (2013) present a model for the rapid transit network design according to two objectives: travel cost and captured traffic. Specifically, the authors describes a bi-objective model which simultaneously minimizes the network design cost taking into account distances between census tracts and stations, and maximizes origindestination traffic capture. To this end, the authors propose a methodology for designing a metro network considering a predefined shape. So, the model locates optimally stops on the topology selected, captures maximum origin-destination traffic and minimizes costs. Constraints of this model can be found in Appendix B. 2.4.11. A game theoretic framework for the Robust Railway Network Design problem In Laporte et al. (2010) a game theoretic framework is used in order to solve the problem of designing a railway transit network in presence of failures. First the authors describe a deterministic model for the problem of designing a railway transit network and then it is extended as follows. They consider only two agents acting in the problem: the planner and the demon. The planner wants to minimize trip coverage or total travel time whereas the demon makes the system works as bad as possible. In the paper two versions of this problem are formulated: Probabilistic Railway Network Design (PRND) and the Stochastic Railway Network Design (SRND) problem. These models are based on a integer lineal model. Later model, consists of deciding a set of potential stations and their connections as well as a line plan covering as many trips as possible in presence of an alternative mode. Objective function and constraints We will focus on the deterministic model introduced in this paper. The objective function is the trip coverage. The constraints that appear in this model are the following: •Budget constraints 63 Chapter 2. Modelling the rapid transit network design problem In this case, the constraints are similar to (2.15). •Design forcing This group of constraints is the same as that introduced in Section 2.4.4. •Routing demand conservation constraints Constraints (2.27)–(2.29) are replaced with constraints with binary variables. •Location-allocation constraints This group of constraints are expressed by means of binary variables. 2.4.12. Designing robust rapid transit networks with alternative routes The aim of Laporte et al. (2012) is to propose a model for the design of a robust rapid transit network. The authors consider that a network is robust when in the event of arc failures, the total trip coverage does not decrease too. Firstly, they deal with the deterministic model for the rapid transit network design problem. The mobility patterns in a metropolitan area as well as a different transportation mode competing with the RTS are known. The demand assignment is based on generalized costs. Secondly, they introduce robustness constraints in the model by means of new variables which provides alternative routes if one arc fails and permits avoid congestion on a restricted set of arcs. Finally, computational experiments are presented. Objective function and constraints We will focus on the deterministic model introduced in this paper. The objective function is the trip coverage. The constraints that appear in this model are the following: •Budget constraints In this case, the considered constraints are similar to (2.15). •Design forcing This group of constraints is the same that introduced in Section 2.4.4. •Routing demand conservation constraints Constraints (2.27)–(2.29) are replaced by constraints with binary variables. 64 2.4. Special cases •Location-allocation constraints This group of constraints are expressed by means of binary variables. •Splitting demand constraints These constraints force to demand to be assigned to the RTS mode if the generalized cost associated to public mode is not more than the corresponding cost of alternative mode. 2.4.13. GRASP algorithms for the robust railway network design In Garc´ıa-Archilla et al. (2013), an integer linear programming model for the design of railway network infrastructure (stations and links between stations) as well as their corresponding robust version are introduced. The paper is structured in two phases: firstly, the deterministic problem for the rapid transit network is considered and secondly, the robustness property of the rapid transit network is addressed. The authors describe a railway network design problem in presence of a competing mode. So, the demand uses the faster mode to go from its origin to its destination. The mobility patterns, the potential stations and construction costs are known. The authors propose to design lines in the line planning phase in order to avoid too complex models such as the ones described Laporte et al. (2010, 2012) (which consider lines in the design phase). The results obtained in a computational experience indicate the Greedy Randomized Adaptive Search Procedure (GRASP) algorithm is an excellent tool for the resolution of this problem. In a second phase, the probabilistic version for the railway network design is considered. This problem was originally introduced in Laporte et al. (2012), in which any link can fail but no more than one link can fail at the same time. In the event of link interruption, an alternative transportation mode is provided to passengers, which generates extra costs. Finally, a computational experiments illustrate the validity of GRASP algorithm. As mentioned at the beginning, we will check the differences with the general model. Objective function and constraints The objective function is the trip coverage. The introduced constraints are classified into different constraint groups. •Budget constraints These constraints are the same as in the general model. 65 Chapter 2. Modelling the rapid transit network design problem •Design forcing In this paper, the authors only consider the infrastructure network, and, therefore constraint (2.16) to (2.25) are changed according to xij and yi. •Routing demand conservation constraints Constrains (2.27) and (2.29) are also modified by using binary variables. They do not consider transfers between lines. •Location-allocation constraints The authors do not consider elastic demand and this group of constraints are modified. •Splitting demand constraints It is expressed in the same terms as previous models. 2.4.14. Recoverable robustness in rapid transit network design Cadarso and Mar´ın (2012) present an extension of the model in Mar´ın and Jaramillo (2009) by introducing robustness in the model. Concretely, the authors consider recoverable robustness in the rapid transit network design problem. They suppose interruption on edges and define a recovery algorithm: the demand is distributed on the network without the affected edge. The problem can be formulated as a two stage optimization problem. At each scenario an edge is eliminated. In the first stage the network is built and the second stage, recovery actions are carried out as a consequence of the considered scenario. 2.4.15. Summary table In this section we present a summary table which shows the main characteristics of all models that appear in the above sections. It will be useful in order to understand the differences in the revised models in the Sections (2.4.1)–(2.4.14). First of all, we will provide in Table (2.3) a number associated with each model in order to facilitate readability. We have compared these models in Table (2.4) under ten entries. The main characteristics are the objective functions, the set of feasible lines considered in the numerical examples, the constraints and the considered algorithms to obtain a solution. In Table (2.4) “BC” stands for “Budget Constraint”, “DFC” for “Design Forcing Constraint”, 66 2.5. Conclusions Literature Review Item Authors Paper 1 Laporte et al. (2007) An integrated Methodology for the Rapid Transit Network Design Problem 2 Garc´ıa-R´odenas et al. (2006) Analysis of the Parameters of Transfers in Rapid Transit Network Design 3 Guan et al. (2006) Simultaneous Optimization of Transit Line Configuration and Passenger Line Assignment 4 Mar´ın (2007) An extension to Rapid Transit Network Design Problem 5 Mar´ın and Garc´ıa-R´odenas (2009) Location of Infrastructure in Urban Railway Networks 6 Mar´ın and Jaramillo (2008) Urban Rapid Transit Network Capacity Expansion 7 Escudero and Mu˜noz (2009) An Approach for Solving a Modification of the Extended Rapid Transit Network Design Problem 8 Mar´ın and Jaramillo (2009) Urban Rapid Transit Network Design: Accelerated Benders Decomposition 9 Kermanshahi et al. (2010) Rapid Transit Network Design Using Simulated Annealing 10 Guti´errez-Jarpa et al. (2013) Rapid Transit Network Design for Optimal Cost and Origin Destination Demand Capture 11 Laporte et al. (2010) A Game Theoretic Framework for the Robust Railway Network Design Problem 12 Laporte et al. (2012) Designing Robust Rapid Transit Networks with Alternatives Routes 13 Garc´ıa-Archilla et al. (2013) GRASP Algorithms for the Robust Railway Network Design 14 Cadarso and Mar´ın (2012) Recoverable Robustness in Rapid Transit Network Design Table 2.3.: Classification of main papers on network design “FCC” for “Flow Conservation Constraint”, “LAC” for “Location Allocation Constraint”, “SDC” for “Splitting Demand Constraint”, “TC” for ”Transfer Constraint” and “CC” for “Capacity Constraint”. Summary table Constraints Model Year Objective functions lines BC DFC FCC LAC SDC TC CC Models/Algorithms 1 2004 Trip coverage 2 X X X X X ILP 2 2005 Trip coverage 3 X X X X X X ILP 3 2006 Costs and travel time 4 X X X ILP 4 2007 Trip coverage 3 X X X X X ILP routing cost Branch and bound 5 2008 Trip coverage, cost in the 2 X X X X X ILP alternative mode 6 2008 Covered demand and costs 4 X X X X X ILP/Branch and bound 7 2008 Trip coverage 3 X X X X X ILP/Branch and bound 8 2008 Covered demand and costs 4 X X X X X ILP/Branch and bound Benders decomposition 9 2010 Trip coverage – X X X X X (SA) algorithm 10 2013 Traffic demand and costs – XILP 11 2009 Trip coverage 3 X X X X X ILP 12 2010 Trip coverage 4 X X X X X ILP/Branch and bound 13 2011 Trip coverage – X X X X X GRASP algorithm 14 2012 Covered demand and costs 3 X X X X X ILP Table 2.4.: Characteristics of main papers addressing the network design problem 2.5. Conclusions In this chapter we have reviewed the existing literature on the rapid transit network design problem. We have proposed a general model which contains all characteristics of 67 Chapter 2. Modelling the rapid transit network design problem the different models considered in the domain of transit network design. We have dealt with the problem of determining the infrastructure network, the set of lines, the frequency of each line as well as the capacity of services for a rapid transit network. A key factor in our problem is the inclusion of a long-term public economic support for the operating and acquisition rolling stock. So, a mixed integer non-linear program model integrating network design, line planning and fleet investment has been proposed. Considering both problems is beneficial to achieve meaningful results. The trip assignment can be done more efficiently when frequencies are known. An analysis on the different perspective in the objectives when a network is designed has been done. Specifically, each objective is mathematically defined and different general objective is expressed. Moreover, long-term public economic support for a network profitable operation is considered as a key factor in the network design problem. In order to compare the different models, we have introduced a notation valid to all papers considered in Appendix A. Also we have provided a summary table which contains the main characteristics of all models. In Annals of Operations Research: D. Canca, A. De Los Santos, G. Laporte, J.A. Mesa. A General Rapid Network Design, Line Planning and Fleet Investment Integrated Model, conditionally accepted, that discount rate is incorporated to our problem adding new parameters. In this work we have done several experiments with our general model and the net profit on small networks. The model was solved using a branch-and-bound and a relaxed nonlinear programming problem (NLP). 68 Appendix A Data, notation and variables A.1. Data and notation In this appendix we state notations and variables needed to describe all models considered as special case of the general model. So, taking into account this appendix and the data, notation and variables described in Chapter 2, we can describe all the reviewed models. We introduce the following input data: •A set Ncof nodes representing centroid points. •A set Efrepresenting fictitious links between nodes of Ncand N. •For each node i,¯ N(i) = {j∈N:{i, j} ∈ E′}denotes the set of adjacent nodes to ion the graph related to the alternative mode. •Nodes oℓand dℓdenoting the origin and destination station in the itinerary of line ℓ, respectively. •An lower and upper bound, cℓ min and cℓ max on the construction cost of each line. •There exists a lower bound Cmin on the total construction cost of the RTS. •cRTS ij is the generalized cost to traverse the edge {i, j}by the RTS mode. •A penalty TP on the rapid transit travel time for each transfer. 69 Chapter A. Data, notation and variables •ucℓ iis the user cost for transferring line ℓat station i. •A sufficiently large real number Mand a small tolerance ε > 0. •Λ is a congestion factor. •ckis the cost construction of path k. • |k|number of elements of path k. •Γwk ij = 1 is the path-link incident matrix whose value is 1 if path kfor OD pair w, uses arc (i, j), 0 otherwise. •Let Γwbe the pre-identified feasible paths from OD pair w. •¯ Mis the maximum number of transfers allowed at each trip. •frℓis the frequency of line ℓ. •Θij is the capacity of arc (i, j)∈A. •M1≥1 + maxw∈W∧uALT wis a sufficiently large real number. •M2≥ |E|/2 is a sufficiently large real number. •Γ is the maximum number of paths. •Let Sbe the set of corridors. •Nsis the set of candidate nodes to be stations of the corridor s∈S. • |S|number of elements of S. •Ntis the terminal node set that are candidates to be end nodes. •lmin is the minimum length between two adjacent nodes. A.2. Variables The problems we are dealing with require the following variables: •˜ fw ij = 1 if demand of the OD pair wtraverses arc (i, j)∈A, 0 otherwise. 70 A.2. Variables •ϕw ij ∈[0,1] denotes the proportion of demand of wthat uses arc (i, j)∈E′on the alternative mode. •˜ϕw ij = 1 if demand of wtraverses arc (i, j)∈E′on the alternative mode, 0 otherwise. •˜ fwℓ ij = 1 if demand of wgoing through arc (i, j)∈Auses line ℓ, 0 otherwise. •˜ fwℓ i= 1 if demand of wtransfers in station ito line ℓ, 0 otherwise. •pw= 1 if demand of wis allocated to the RTS, 0 otherwise. •˜xℓ ij = 1 if line ℓtraverse arc (i, j)∈A. •˜xs ij = 1 if the arc (i, j) belongs to the corridor s∈S. •˜yi= 1 if and only if the node iis selected to be a end node. •˜ys i= 1 if and only if the node ibelongs to the corridor s∈S. •ˆ hk w= 1 if the path kis selected for OD pair w. •˜ fwℓ = 1 if demand of the OD wpair uses line ℓ. •˜ fwk ij = 1 if demand of wgoing through arc (i, j)∈Auses path k, 0 otherwise. •˜ fw i= 1 if demand of wtransfers at node i. 71 Chapter 3 Simultaneous frequency and capacity problem 3.1. Introduction In this chapter, we will focus on the line planning process. In the strategic planning process of a rapid transit network, decisions about a line plan, the size of trains and the number of crews are necessary. We assume the infrastructure (tracks and stations) as well as its associated lines are already given. In railway terminology, a line is characterized by several aspects: two different terminal stations, a sequence of intermediate stops, its frequency, and the vehicle capacity. The traditional line planning problem consists of finding a set of lines (a line plan) and their frequencies providing a good service according to a certain objective, which is usually oriented towards the passengers or the operator. A review of different objective functions is presented in Sch¨obel (2011). As in the rapid transit network design problems, the models can be classified into several categories depending on the point of view that is considered. A classification of these models is presented in Sch¨obel (2011). The author distinguishes between models oriented to passenger and models oriented to costs. Usually, the goal of models oriented to costs is to minimize the train operating costs. The problem presented in Claessens et al. (1998) consists of determining a set of lines from a line pool, the frequency and type of train for each line as well as the number of carriages for each train, minimizing costs related to train operation. The cost structure 79 Chapter 3. Simultaneous frequency and capacity problem is defined according to fixed costs per carriage and hour, variable costs per carriages and kilometer and variable costs per train and kilometer. By means of a modal split procedure, the passengers are assigned a priori in the system. In order to simplify the problem, the authors define binary variables representing if a line ℓis served by trains of type twith c carriages. However, the model is a nonlinear programming program and some techniques to make the problem manageable are considered. In Goossens et al. (2004) a branch-and- cut approach based on the models of Claessens et al. (1998) is described. More recently, Goossens et al. (2006) extend this model to the multi-type case in which not all trains need to stop at all stations. First they describe the same problem than Claessens et al. (1998) and then extend the model by considering different types of trains (regional, intercity and interregional). The passengers are assigned a priori to the different train types. This problem is described as a multi-commodity flow problem. With respect to passenger oriented, one of most common objectives in the literature is to maximize the number of direct trips, see Bussieck (1998) and Bussieck et al. (1997). A major drawback of this objective is that it does not take travel times into account, and therefore it may yield a network with few transfers but with long travel times. Another paper such as Sch¨obel and Scholl (2006) considered as objective function the total travel time of all passengers. In order to compute the travel time in the system, a penalty for each transfer representing the inconvenience for the passengers is introduced. In order to model the line planning problem, the authors define a graph structure named Change&Go. The aim is to find a set of lines, a path for each origin-destination pair, respecting a budget on the operating costs. The problem we are treating with consists of determining the frequency and the train size of each line, maximizing the net profit of line plan. Furthermore, we have assumed that all passengers willing to travel in the RTS can be transported. The passengers choose their routes and their transport mode according to traveling times, which are defined by means of the considered frequencies. Concretely, in this chapter we simultaneously select the frequency and the number of carriages for each line of the RTS maximizing the net profit. The following example shows how both the frequency and the number of carriages are decisive factors to be considered when planning rapid transit lines. Example 3.1.1 Consider a simple case in which S={1,2,3},L={ℓ1={1,2}, ℓ2= {2,3}}. A trip from 1to 3includes a waiting time at the origin station and a transfer time at station 2. Note that therefore the expected travel time of this OD pair depends on the frequencies of the lines, and thus passengers choose the RTS mode or the competing mode 80 3.1. Introduction depending on this. Note as well that if the number of potential passengers is large enough, then we also need to consider including more carriages in the trains, as the maximum allowed frequency might not be enough to transport them all. 123 ℓ1ℓ2 Figure 3.1.: Example with two lines. The main differences between our model and those defined in Claessens et al. (1998) and Goossens et al. (2006) are the following: they do not take into account an alternative mode competing with the rapid transit transport, they consider different train types and we present a model integrating the traffic assignment procedure in the optimization process. Furthermore, we present a different objective function which includes income derived from the passengers as well as costs related to the rolling stocks acquisition and personnel costs due to operation of trains. Thanks to the incorporation of a logit function, the level of demand will depend on the quality of the services offered. Moreover, we consider two different situations: the problem with an unlimited number of carriages and the problem with a maximum number of carriages. The first problem assumes the maximum number of possible carriages is a sufficiently large number in order to transport all people traveling on each line in the RTS. In other words, the RTS is a non-crowding network. In contrast, the capacitated problem has a limitation on the number of carriages and the RTS can become a congested network. For the last case, a congestion function measuring the level of in-vehicle crowding is introduced in the model. The remainder of the chapter is structured as follows. In Section 3.2 we describe the problem, the needed data and notations as well as the objective function. In Section 3.3 we formally define the problem for the case without capacity limitation, which is modeled in Section 3.3.1 as a mathematical programming program. A heuristic algorithm as well as efficient approaches are presented in Section 3.3.2. The problem with a limited number of carriages is introduced in Section 3.4. Computational experiments are carried out on Appendix C. Computational comments are presented in Section 3.5.2. The chapter ends with some conclusions. 81 Chapter 3. Simultaneous frequency and capacity problem 3.2. The problem As commented, the problem we are dealing with consists of maximizing the net profit of a line plan by selecting the frequency and the train size of each line, assuming that all passengers willing to travel in the RTS can be transported. We distinguish two different versions of this problem. At the first problem an unlimited number of possible carriages is considered. This yields solutions where the number of carriages per train is the minimum number of carriages so that all passengers can be transported. However, this is not true in the second version of this problem. In this problem a limited number of carriages is taken into account and the network can be a congested network. We introduce the crowding effect by means of a congestion function which is depending on the load on each arc. This function assigns a time penalty on each congested arc, therefore modifying, the problem instance. The crowding effect is assumed to be the in-vehicle crowding. In other words, we only assume congestion inside train and not at the platforms. We also want to remark that solutions in which platform crowding appears, are not taken into account. In both problems presented, we define a parameter σin order to allow solutions that exceed the capacity in a small number of passengers. Apart from the number of carriages, an important difference between the uncapacitated and capacitated problem is the congestion effect which influences on the passenger’s behavior and, therefore, on the profit. 3.2.1. Data and notation We now formally describe the Rapid Transit System Simultaneous Frequency and Capacity Problem (RTSSFCP), which takes the following input data. We assume the existence of a set of stations, N={i1,...,in}and a set of lines L={ℓ1,...,ℓ|L|}in the RTS. For the sake of readability we will identify a station with its subindex whenever this creates no confusion. Let denote lenℓand nℓbe the length and the number of stations of line ℓ, respectively. Each line ℓ∈ L is defined as ℓ={(i1, i2),(i2, i3),...,(inℓ−1, inℓ)}, where arcs form two paths; {i1, i2, i3,...,inℓ}and {inℓ, inℓ−1,...,i1}. Each couple of arcs (ij1, ij2) and (ij2, ij1) represents an edge {ij1, ij2}. In order to compute traffic flows we need the set of (directed) arcs associated with E. We therefore define Aas the set of (directed) arcs of the network. Note that E={{i, j}: (i, j)∈A, i < j}. Let ((N, E),L) be a RTS line network describing the RTS system. Let dij =dji be the length of edge {i, j} ∈ E. The parameter dij can also represent the time needed to traverse edge {i, j}, transforming distances in times by means of the parameter 82 3.2. The problem λ, which represents the average distance traveled by a train in a hour (commercial speed). We consider the same value of λfor all trains. Let νℓbe the cycle time of line ℓ, that is, the time necessary for a train of line ℓto go from the initial station to the final station and returning back. Note that νℓ= 2 ·lenℓ/λ. The competing mode (private car, bus, etc) is represented by an undirected graph GE′=G(N, E′). The nodes are assumed to be coincident with those of the rapid transit mode: they could represent origin or destination of the aggregated demands; however, edges are possibly different. For each edge {i, j} ∈ E′, let d′ ij be the traversing time of such link by the competing mode. Let W={w1,...,w|W|} ⊆ N×Nbe a set of ordered origin-destination (OD) pairs, w= (ws, wt). For each OD pair w∈W,gwis the expected number of passengers per hour for an average day and uALT wis the travel time using the alternative mode of OD pair w, respectively. With respect to costs, we distinguish three types: related to the operation, the personnel and the investment. Concerning rolling stock, we define a cost for operating one locomotive per unit of length cloc as well as a cost representing operating cost of one carriage ccarr per length unit. Both parameters include running costs such as fuel or energy consumption. These terms can be easily adapted to another type of rolling stock. Related to the personnel costs, a cost ccrew per train and year is given. For the rolling stock acquisition, we consider two costs: the purchase price of the necessary locomotives Iloc per train and the purchase price of one carriage Icarr. Concerning capacity, let Θ be the carriage capacity measured in number of passengers seating and standing. We consider a minimum number δmin of carriages and a sufficiently large number ∆ of carriages that can be included in a train. We define the capacity associated to a train as the maximum number of passengers that it can transport at any given time. More precisely, we define the capacity of a train of a line ℓby means of two factors: the capacity of a carriage (Θ) and the number of carriages forming the train (δℓ). We consider a fixed finite set of possible frequencies Ffor lines of the RTS. We assume the frequency of each line takes values between a minimum and maximum frequency in order to guarantee a certain level of service in the network. To be more precise, not all feasible frequency values between this minimum and maximum can be considered. Note that in real systems the frequencies have to produce a regular timetable. To take this requirement into account, we describe the set of ordered possible frequencies as F={φ1, φ2,...,φ|F|}, where each φq∈N,1≤q≤ |F| and |F| ≥ 2. Let ρbe the total number of hours that a train is operating per year and ηbe the fare per trip which is the same for all trips regardless of their length/duration. A parameter needed to compute the transfer time is uci, which 83 Chapter 3. Simultaneous frequency and capacity problem represents the time spent in changing platforms at station i. 3.3. Uncapacitated problem We now describe the Uncapacitated Rapid Transit System Simultaneous Frequency and Capacity Setting Problem (URTSSFCP) in more detail. Section 3.3.1 presents the mathematical programming program. In Section 3.3.2 several techniques for improving the efficiency of the mathematical programming model are presented. 3.3.1. A mathematical programming program We first introduce a mathematical programming program to solve the URTSSFCP, which uses the following sets of variables: •ψℓ∈ F is the frequency of line ℓ(number of services per hour). •δℓ∈ {δmin,...,∆}is the number of carriages used by trains of line ℓ. •uRTS w>0 represents the travel time of pair wusing the RTS network. •fRTS w∈[0,1] is the proportion of OD pair wusing the RTS network. •˜ fwℓ ij =(1,if the OD pair wtraverses arc (i, j)∈Ausing line ℓ 0,otherwise. •˜ fwℓℓ′ i=(1,if demand of pair wtransfers in station ifrom line ℓto line ℓ′ 0,otherwise. The average travel time associated to OD pair w= (ws, wt)∈Wusing the RTS network can be explicitly defined as follows: uRTS w=X ℓ∈L X j:{ws,j}∈ℓ 60 ˜ fwℓ wsj 2ψℓ + (60/λ)X ℓ∈L (X {i,j}∈ℓ ˜ fwℓ ij dij) +X ℓ∈L X ℓ′:ℓ′6=ℓX i∈ℓ∩ℓ′ ˜ fwℓℓ′ i(60 2ψℓ′ +uci), w = (ws, wt)∈W. (3.1) The first term in (3.1) is the average waiting time at the origin station. Since we are dealing with high frequencies systems, we assume passengers go to stations without knowing the exact departures time of trains and, therefore, it is reasonable assuming that the average waiting time is half the headway (time between consecutive services). The 84 3.3. Uncapacitated problem second term in (3.1) is the in-vehicle time. The third one is the time spent in transfers. For the reason previously commented, the average waiting time is assumed to be half the headway. In this case, we have to add the required time to change platforms. Another variable that can be explicitly defined is the assignment fRT S wof demand to the RTS system. We assume the number of passengers who use a transport system varies depending on the provided service. More specifically, the proportion of an OD pair using each mode may be different depending on the characteristics of the RTS to be designed and on the competing transport mode. Therefore, the demand is split between the RTS and the alternative mode according to the generalized cost of each mode. The modal split is modeled by using logit type functions (Ort´uzar and Willumsem (1990)) as opposed to binary variables which are used in very complex problems. Two real positive parameters are usually required: α, representing the market share of each mode, and β, representing the importance of each transportation mode (Mar´ın and Garc´ıa-R´odenas (2009)). Let αRTS and αALT be the market share of RTS and alternative mode, respectively. Let us denote α=αALT −αRT S. As in Garc´ıa-R´odenas et al. (2006), βis supposed to be independent of the modes. Therefore, the proportion of OD pair wusing the RTS mode is fRTS w=1 1 + e(α−β(uALT w−uRT S w)) , w ∈W. (3.2) The logit model estimates the proportion of users assigned to each mode for each origindestination pair in a continuous way. Note that this proportion depends on the travel time in each transport mode. In Schmidt and Sch¨obel (2010) the route decisions are integrated in the line planning problem. To this end, the authors consider a change and go graph. On this graph, a modified Dijkstra algorithm is applied and adapted to obtain the shortest path of an origin-destination pair. Objective function As mentioned, we consider the existence of public economic support for the operation of the RTS during certain planning horizon. This assumption is very common in the development of rapid transit networks around the world. Usually, governments provide subsidies on the basis of the number of passengers or passenger-kilometer in order to guarantee certain positive margin to companies exploiting the transportation system. For instance (see newspaper http://www.20minutos.es/noticia/2028399/0/madrid/empresasprivadas/metro-ligero/). 85 Chapter 3. Simultaneous frequency and capacity problem The objective function considered is the net profit zNET of the rapid transit network (Li et al. (2011b), Feifei and Haicheng (2012), Feifei (2014)). This profit is expressed as the difference between revenue and total operation cost in terms of monetary units over a planning horizon. In this chapter, we will not consider costs related to the construction of the RTS since the infrastructure network is already built. For the sake of readability, we will repeat some terms presented in Chapter 2. The total revenue for the ˆρyears is computed as the number of passengers who use the RTS during the planning horizon, times the passenger fare µplus the passenger subsidy, η, which is the same for all passengers independently of the length of their trips. So, the revenue is mathematically expressed as zREV = (η+µ)ρˆρX w∈W gwfRTS w.(3.3) The operation cost of a network is expressed by means of a fixed cost zF OC and a variable cost zV OC. The fixed operating cost includes maintenance costs and overheads. The fixed operating cost depends on the infrastructure. This term does not affect the objective function and is not considered, see Feifei and Haicheng (2012), Feifei (2014). The variable operating cost zV OC over the planning horizon is defined as the sum of the crew operating cost zCrOC and the rolling stock cost zRSOC . The crew operating cost zCrOC includes the crew cost induced by the operation of all trains in the time horizon ˆρ. This cost is affected by the required fleet size Bℓ. The required fleet for each line ℓcan be defined by means of the product of its frequency and its cycle time νℓas follows: Bℓ=⌈ψℓνℓ⌉=⌈2ψℓ·lenℓ/λ⌉. Thus, the crew operating cost in the planning horizon is zCrOC = ˆρ·ccrew X ℓ∈L Bℓ.(3.4) The rolling stock operation cost of a train in one hour is defined as the distance λtraveled by the train, times the cost of moving the train with δℓcarriages and is approximated by cloc +ccarrδℓ(Garc´ıa and Mart´ın (2012)). Therefore, the rolling stock operation cost 86 3.3. Uncapacitated problem in the whole planning horizon zRSOC is zRSOC = ˆρρ X ℓ∈L Bℓλ(cloc +ccarrδℓ),(3.5) and the variable operating cost in the planning horizon is zV OC =zRSOC +zCrOC. The fleet investment cost for each train is the cost of purchasing the locomotives and the carriages. Therefore, the fleet acquisition cost of all trains zF AC is computed as zF AC =X ℓ∈L Bℓ(Iloc +Icarr ·δℓ).(3.6) So, we define the net profit zNET associated to the rapid transit network as zNET =zREV −(zV OC +zF AC).(3.7) Constraints The constraints of the problem are formulated as follows. •Flow conservation constraints X ℓ∈L X j:(ws,j)∈ℓ ˜ fwℓ wsj= 1, w = (ws, wt)∈W(3.8) X ℓ∈L X i:(i,wt)∈ℓ ˜ fwℓ iwt= 1, w = (ws, wt)∈W(3.9) X ℓ∈L X j:(j,ws)∈ℓ ˜ fwℓ jws= 0, w = (ws, wt)∈W(3.10) X ℓ∈L X j:(wt,j)∈ℓ ˜ fwℓ wtj= 0, w = (ws, wt)∈W(3.11) X ℓ∈L X i:(i,k)∈ℓ ˜ fwℓ ik −X ℓ∈L X j:(k,j)∈ℓ ˜ fwℓ kj = 0, w = (ws, wt)∈W, k ∈N\ {ws, wt}.(3.12) 87 Chapter 3. Simultaneous frequency and capacity problem •Transfers 2˜ fwℓℓ′ i≥X k:(k,i)∈ℓ ˜ fwℓ ki +X k:(i,k)∈ℓ′ ˜ fwℓ′ ik −1 (3.13) 2˜ fwℓℓ′ i≤X k:(k,i)∈ℓ ˜ fwℓ ki +X k:(i,k)∈ℓ′ ˜ fwℓ′ ik ,(3.14) ℓ, ℓ′∈ L, ℓ 6=ℓ′, i ∈ℓ∩ℓ′, i 6=ws, i 6=wt, w = (ws, wt)∈W. •Capacity constraints X w∈W gwfRTS w˜ fwℓ ij ≤Θδℓψℓ, ℓ ∈ L,{i, j} ∈ ℓ. (3.15) •Binary constraints ˜ fwℓ ij ,˜ fwℓℓ′ k∈ {0,1}, k ∈N, (i, j)∈A, ℓ ∈ L, w ∈W. •Integer constraints δℓ∈ {δmin,...,∆}, ℓ ∈ L ψℓ∈ F, ℓ ∈ L. •Other constraints fRTS w=1 1 + e(α−β(uALT w−uRT S w)) ∈[0,1], w ∈W. Recall that the model includes constraints related to the proportion of passengers using the RTS (Equation (3.2)) as well as the travel time for each OD pair (Equation (3.1)). Constraints (3.8) to (3.12) are flow conservation constraints for the fvariables. Constraints (3.13) and (3.14) ensure that if an OD pair wenters station k∈Nusing one line and exits this station using another line, then a transfer is done. Constraints (3.15) indicates the total capacity per hour of such line is a sufficiently large number in order to transport all passengers preferring to travel in the RTS. The URTSSFCP consists of maximizing zNET subject to constraints (3.1), (3.2) and (3.8)– (3.15). 88 3.3. Uncapacitated problem Data: A frequency configuration in the way Cφq F= (φq, φq,...,φq). Loop I; for each line ℓdo Find the arc eℓof ℓwith maximum load; Find the minimum number of carriages δℓneeded to transport all passengers traversing arc eℓ; Keep δℓ. end Compute the profit zNET . Result:zNET associated to the frequency configuration Cφq F= (φq, φq,...,φq) and carriages (δℓ1,...,δℓ|L| ) Algorithm 5: Pseudocode for Loop I which is used in phase 1 and 2. Data: A configuration of frequencies (φq1,...,φq|L| ). Set z={}; for each line ℓpdo Obtain the best profit zpapplying Move+or Move−on the frequency φqp associated to ℓpand according to (φq1,...,φq|L|), by means of Loop II; z=z∪ {zp}. end return arg max z. Result: The frequency and carriages configuration of maximum profit. Algorithm 6: Pseudocode for the phase 3. Data: A configuration of frequencies Ccur F= (φq1,...,φq|L|). Set z= 0; for each line ℓpdo Obtain the best profit zpapplying Move+or Move−on the frequency φqp associated to ℓpand according to Ccur F, by means of Loop II. Do φqp=ˆ φqpand Ccur F= (φq1,...,ˆ φqp,...,φq|L| ); z=zp. end return z. Result: The frequency and carriages configuration of maximum profit. Algorithm 7: Pseudocode for the phase 4. 95 Chapter 3. Simultaneous frequency and capacity problem Example 3.3.1 Consider two lines ℓ1, ℓ2and five possible frequencies for each line, namely, F={1,2,3,4,5}. •Phase 1: calculate the net profit of the following frequencies: [1,1], [2,2], [3,3], [4,4], [5,5]. Assume that the best profit is given by configuration [3,3]. 12345 1 2 3 4 5 [3,3] Frequency ℓ1 Frequency ℓ2 How phase 1 works The best profit is assumed to be Cini F= [3,3]. Figure 3.2.: Phase 1. Initialization. •Phase 2: in this phase, the neighborhood of [3,3] is N(Cini F) = {[4,3],[2,3],[3,4],[3,2]}. Assume that configuration [3,4] yields the highest profit, so we keep this solution. 2 3 4 2 3 4 [3,3] Best profit [3,4] Frequency ℓ1 Frequency ℓ2 How phase 2 works The best profit is assumed to be Cneig F= [3,4]. Figure 3.3.: Phase 2. Neighborhood. •Phase 3: from solution [3,4], we start by increasing the frequency of the first line (note that [4,4] is not here analyzed). So we compute the next, [5,4], which let us 96 3.4. Capacitated problem assume yields a better profit. We then analyze [1,4] (as frequency 6 is not feasible), then [2,4],.. until we stop improving the profit. If at the first iteration of Move+ ([5,4]), a better profit is not obtained, we decrease the frequency of the first line in the same way as Move+. We do the same for the second line. Assume that the best solution in this phase is [3,1]. 12345 4 [3,4] 1st 2nd 3rd Frequency ℓ1 Frequency ℓ2 Step 1: Move+on first line 12345 4 [3,4] 1st 2nd 3rd Frequency ℓ1 Frequency ℓ2 Step 1: Move−on first line 3 1 2 3 4 5 3rd 2nd; STOP [3,4] 1st Frequency ℓ1 Frequency ℓ2 Step 2: Move+on line 2 3 1 2 3 4 5 1st 2nd; STOP [3,4] 3rd Frequency ℓ1 Frequency ℓ2 Step 2: Move−on line 2 Figure 3.4.: Phase 3. A local search by movements. •Phase 4: We now apply Move+or Move−on the frequency of each line in solution [3,1] as phase 3. Assume that the best solution found for first line is [4,1]. We now apply Move+or Move−to the second line in solution [4,1] while we improve the profit. The solution obtained after these steps is the final solution of the algorithm. 3.4. Capacitated problem As mentioned, in this section we will define the Capacitated Rapid Transit System Simultaneous Frequency and Capacity Setting Problem (CRTSSFCP) under assumption 97 Chapter 3. Simultaneous frequency and capacity problem 2345 1 1st; STOP 2nd 3rd [3,1] Frequency ℓ1 Frequency ℓ2 Step 1: Move+on line 1 2345 1 3rd; STOP 2nd 1st [3,1] Frequency ℓ1 Frequency ℓ2 Step 1: Move−on line 1 4 1 2 3 4 5 1st; STOP [4,1] 2nd 3rd Frequency ℓ1 Frequency ℓ2 Step 2: Move+on line 1 4 1 2 3 4 5 3rd [4,1] 2nd 1st; STOP Frequency ℓ1 Frequency ℓ2 Step 2: Move−on line 2 Figure 3.5.: Phase 4: a local search by movements. of a limited number of carriages. An interesting aspect to take into account in this problem are the crowding levels as a consequence of taking a limited capacity. In overcrowding situations, many passengers choose an alternative path or a different transportation mode. So, congestion not only causes an increase in the traveler’s disutility, but also a benefit loss to operators. For the sake of clarify, we introduce the following terms. Let κℓ ij be the number of passengers traversing arc (i, j) of ℓby hour. The train capacity of a line ℓis the carriage capacity Θ times the number of carriages associated to one train of ℓ. The carriage capacity have been defined as the nominal capacity or crush capacity (Oldfield and Bly (1988), Jara-D´ıaz and Gschwender (2003)) which includes both seating and standing. The maximum number of passenger Nbℓwho can travel on line ℓby hour can be computed as its frequency times its train capacity. By means of these terms, the load factor ℓ ij is defined as the ratio κℓ ij/Nbℓ. Observe that if ℓ ij ≤1, the arc (i, j)∈ℓis not affected by congestion. Therefore, if the train capacity of a line ℓis not enough to transport all passengers traveling inside ℓ, the rapid transit network can 98 3.4. Capacitated problem become a congested network. In recent research, the load factor is introduced to stipulate the crowding levels. There exists four crowding types: in-vehicle crowding, platform crowding, excessive waiting time and increased dwell time. We will analyze the in-vehicle crowding effects, which can be defined by means of crowding penalties. There are three possible ways to describe this term: time multiplier, the monetary value per time unit and the monetary value per trip. We will consider the time multiplier in our problem. Due to each transport mode is different, it is not possible to define a general crowding function valid for all transport modes, as stated Feifei and Haicheng (2012), Feifei (2014). De Palma et al. (2010) propose an exponential function for the crowding penalty in the context of railway system using a load factor. This crowding function is expressed as CF(ℓ ij) = 1 + ς1 1 + exp(ς2(1 −ℓ ij)) +ς3exp(ς4(ℓ ij −ς5)),(3.20) in which the parameters are positive and ς1and ς3should be carefully calibrated (see Feifei and Haicheng (2012)). The parameter ς5>1 represents the threshold from which the passengers starts to perceive overcrowding. It can be observed that this function reflects the inconvenience associated with in-vehicle crowding. The important point to note here is the form of this function. If the load factor ℓ ij ≤1, CF(ℓ ij) becomes approximately one, the second term in the Equation (3.20) is close to zero for a proper value of parameter ς2and the last term ς3exp(ς4(ℓ ij −ς5)) is approximately zero (recall ℓ ij < ς5). Analogously, when the load factor 1 ≤ℓ ij ≤ς5, in-vehicle crowding starts to working on the traveling time of arc (i,j). The penalty impact will be very depending on the ς2parameter. Our next goal is to introduce congestion in the model presented in Section 3.3 by means of the crowding function defined previously. To this end, we introduce the following variables and parameters. Let ℓ ij be the load factor on the arc (i, j)∈ℓdefined above. Due to the fact that we are only including in-vehicle crowding effects, solutions whose load factor is greater than the value of the parameter σare not allowed. Observe that if ℓ ij > σ, penalties according to the excess waiting time, platform crowding and increased dwell time have to be included in the model. In order to introduce the in-vehicle congestion effects on the model, we include constraint ℓ ij ≤σin the mathematical programming program defined in Section 3.3.1. The main difference between this model and that defined in Section 3.3 lies in the introduction of an upper bound δmax on the number of possible carriages. As a consequence, lines in specific sections of the RTS can be congested. We consider ¯ dℓ ij =CF(ℓ ij)·dij as 99 Chapter 3. Simultaneous frequency and capacity problem the perceived time to traverse arc (i, j) of ℓusing the rapid transit system. As commented, if the arc (i, j)∈ℓis not congested, ¯ dℓ ij ≃dij. So, variable uRT S wrepresenting the average travel time must be redefined. The average travel time associated to OD pair wusing the rapid transit network under crowding can be explicitly defined as follows: uRTS w=X ℓ∈L X j:{ws,j}∈ℓ 60 ˜ fwℓ wsj 2ψℓ + (60/λ)X ℓ∈L (X {i,j}∈ℓ ˜ fwℓ ij ¯ dℓ ij) +X ℓ∈L X ℓ′:ℓ′6=ℓX i∈ℓ∩ℓ′ ˜ fwℓℓ′ i(60 2ψℓ′ +uci), w = (ws, wt)∈W. (3.21) The first term in (3.21) is the waiting time at the origin station, which is also assumed to be half of time between services of this line. The second term is the in-vehicle time which can be affected by congestion. Finally, the last one constitutes the required time by the transfers. The rest of variables, parameters, constraints as well as objective function are equals to those defined in Section 3.3. This model has several limitations. The first one, is the time needed to find good solutions. The second and most important, is the problem complexity. Note that if the congestion function is activated, data related to distance change. So, the instance become to be different when the penalty is applied on the distances. Concretely, the congestion effect influences on the travel time of each path, and, therefore, on the number of passengers in the RTS. The passengers’ behavior is different in congestion presence and, as a consequence, it is different for each instance modification. It can be observed that the penalization process stops when the network is not congested or a fixed point is searched. In other words, passengers take a different path or mode and an equilibrium is searched (all passengers can be transported). The solution reflects not only the number of carriages and frequencies, but also a medium-term analysis of the passenger’s behavior under congestion. The excess waiting time effects can be incorporated on our problem as follows. The passengers affected by this aspect are who waiting for next train to the fact that the first train was full and they were left behind, increasing waiting time and discomfort to travel. In the context of bus transport, Oldfield and Bly (1988) presented a formal definition of this type of crowding. They expressed the waiting time according to headway and crowding level. However, the inclusion of excess waiting time effects in our model is not trivial. For the purpose, the travel time of all passengers waiting for next train is increased according to an additional time which depends on the frequency of the congested line. The rerouting passengers process is very difficult. This is due to the fact that the 100 3.4. Capacitated problem passengers affected by the excessive waiting time have different travel time from the rest of passengers and, as a consequence, a different instance associated. So, the initial instance is split into two different instances: one associated to excessive waiting time and the other one, related to in-vehicle crowding. Analogously, the origin-destination matrix is divided into two matrixes: one containing the passenger associated to the in-vehicle crowding and other one, according to the excessive waiting time. The crowding phenomenon is also defined as the congestion effect at train stations; the access/egress to/from the station, on platforms (see Douglas and Karpouzis (2005)) and on the increased dwell times as Lin and Wilson (1992). The following section is devoted to introduce two algorithms to solve our problem. 3.4.1. Two algorithms for our problem In this section we introduce two different algorithms that solve our problem: one with the nominal capacity and other one with number of seats. These algorithms check each possible frequency and each number of carriages per train of each line. The idea is to iteratively test all possible combinations of frequencies and carriages. Once the frequencies and carriages have been set, the shortest path on the rapid transit network for each OD pair can easily be computed by a modified Dijkstra algorithm. From these shortest paths the number of passengers traveling on each line and arc is calculated and the capacity constraint is tested on the arc with maximum load. If there is a congested arc, the penalization process is activated. Depending on the considered definition of carriage capacity, the congestion is perceived before or later. The perceived travel time to traverse each congested arc is defined as the travel time to traverse each arc times its corresponding penalty. When the penalization process is finished, the rerouting passenger process is activated. For the purpose, the shortest path taking into account transfer and waiting times on the RTS for each OD pair is recalculated and the capacity constraint is rechecked and so on. Due to the fact that travel time increase, the number of passengers on congested arc is smaller than in the previous iteration. Some passengers will take an alternative path or an alternative transport mode. This procedure breaks when the congestion ends or when a fixed point is reached. Algorithm 10 shows the pseudocode to solve the CRTSSCFP with nominal capacity and Algorithm 13 is the pseudocode to solve the CRTSSCFP with the number of seats at each carriage. For the congestion with the seat capacity, the in-vehicle crowding is activated when the load factor reaches 140% or standing density is over four passengers per square meter (see Feifei and Haicheng (2012), Feifei (2014)). 101 Chapter 3. Simultaneous frequency and capacity problem Data: A combination of frequencies and carriages Let niter = 0 be the number of iterations; Loop III(a): Check the capacity constraint for each line ℓdo Find the arc (i, j)∈ℓwith maximum load ℓ ij; if 1< ℓ ij ≤σthen penalize the traverse time of each arc by means of CF-function; niter =niter + 1; go Loop IV(a); end end Result: A rapid transit system. Algorithm 8: Checking the capacity constraint with nominal capacity. Data: A line network (S, L) Loop IV(a): Check fixed point if niter is equal to one then We define (Spre,Lpre) as (S, L); go Loop III(a); else if the network (S, L)is the same than (Spre,Lpre)then break; else We define (Spre,Lpre) as (S, L); go Loop III(a); end end Result: A rapid transit system. Algorithm 9: Testing the fixed point with nominal capacity. 102 3.4. Capacitated problem Data: A line network (S, L), a set of possible frequencies and a minimum and maximum capacity Set z={}; for each possible combination of frequencies and carriages do go Loop III(a); Compute the profit zNET ; z=z∪ {zNET } end return arg max{z}; Result: The frequency and capacity configuration with the maximum profit. Algorithm 10: The algorithm for the rapid transit system frequency and capacity setting problem under congestion with nominal capacity. Data: A combination of frequencies and carriages Let niter = 0 be the number of iterations; Loop III(b): Check the capacity constraint for each line ℓdo Find the arc (i, j)∈ℓwith maximum load ℓ ij; Let ˆℓ ij be the load with the nominal capacity; if ℓ ij >1.4and ˆℓ ij ≤σthen penalize the traverse time of each arc by means of CF-function; niter =niter + 1; go Loop IV(b); end end Result: A rapid transit system. Algorithm 11: Checking the capacity constraint with seat capacity. 103 Chapter 3. Simultaneous frequency and capacity problem Data: A line network (S, L) Loop IV(b): Check fixed point if niter is equal to one then We define (Spre,Lpre) as (S, L); go Loop III(b); else if the network (S, L)is the same than (Spre,Lpre)then break; else We define (Spre,Lpre) as (S, L); go Loop III(b); end end Result: A rapid transit system. Algorithm 12: Testing the fixed point with seat capacity. Data: A line network (S, L), a set of possible frequencies and a minimum and maximum capacity Set z={}; for each possible combination of frequencies and carriages do go Loop III(b); Compute the profit zNET ; z=z∪ {zNET } end return arg max{z}; Result: The frequency and capacity configuration with the maximum profit. Algorithm 13: An algorithm for the rapid transit system frequency and capacity setting problem under congestion with seat capacity. 3.5. Computational experiments All the calculations in this section were performed with a Java code in a computer with 8 Gb of RAM memory and 2.8 Ghz CPU. For purpose of evaluating the performance of our algorithms, we have used several instances of networks (see 3.5.1). Specifically, we have selected instances with 2,3,5 and 6 lines. There are no previously reported solutions for the proposed problem as far as we are 104 3.6. Conclusions 3.6. Conclusions We have described a problem in the line planning context, which consists of selecting, for each line, the number of services per hour and the number of train carriages in presence of a competing transportation mode. In this problem, all passengers preferring to use the RTS have a service and a certain net benefit is maximized. This problem requires to incorporate a long term public economic support for the operating and acquisition rolling stock. We have classified our problem into two categories: uncapacitated and capacitated problem. The first problem assumes the maximum number of possible carriages is a sufficiently natural number in order to allow all people preferring to travel in the RTS can be transported. The second one can lead to congested networks since the number of possible carriages is a limited value. We have proposed two different algorithms to solve the first problem: an exact and heuristic algorithm. The heuristic technique is a procedure based on a Local Search Algorithm. The modifications are done by means of an appropriated neighborhood structure and movements. The input data in the computational experiments has been based on real data in order to calibrate all parameters that appear in our problem. Moreover, we have randomly generated instances for different types of networks. Comparative tests on a large set of instances have shown that our heuristic in the uncapacitated problem can provide high quality solutions within reasonable computing times. Out of the 170 instances tested in the uncapacitated case, our algorithm was able to provide optimal solutions for most instances: it found the optimal solution in 155 instances (91.17%). On the other hand, the algorithm defined in Section 3.4 have been tested on small networks showing the effect of the congestion on the solutions. The congestion impact have been studied by means of a congestion function which measures the level of in-vehicle crowding. A total of 200 experiments were carried out in our analysis. From the obtained results, it can be observed that the profit is more economically interesting when the network is not a congested network. In other words, the demand is sensitive to congestion and it is more profitable to add carriages or trains than to lose passengers. This problem can easily be extended to the case of a set of possible lines (a line pool) analyzing iteratively all combinations of lines. For each possible set of lines, the problem is reduced to our problem. 111 Appendix C Computational results In the next section, we will report the results for each network, considering a sufficiently large number of carriages. Section C.0.2 is devoted to the congested case. C.0.1. Computational experiments for the uncapacitated problem We assume two possible values for the σparameter: 1.1 and 1.2. So, for σ= 1.1, if the number of passenger traveling inside each line is higher than capacity of line over 10%, the solution is taken into account. The δmax parameter was adjusted in the way all passengers willing to travel in the RTS can be transported. In fact, we consider δmax = 8 for the 6×2, 7 ×3, 8 ×3 and 15 ×5 configurations and δmax = 10 for the 20 ×6-configuration. A total of 170 experiments were carried out, as showed in Tables C.1, C.3, C.5, C.7 and C.9. In the most cases, the heuristic and the exact procedure lead to the same results. In the following, we will analyze each network separately. 6×2-configuration It can be observed that the average of all CPU times at the heuristic is 0.063375 seconds while if we consider the exact, its average is 0.19335 seconds. So, the heuristic improves the average CPU time in 67.22% respect to the exact. This indicates that the heuristic procedure is promising and that for instances of large size the heuristic is expected to be much faster than the exact procedure. Note that the maximum net profit is obtained for the Seed1-instance at all scenarios. However, the revenue at this instance is not the 113 Chapter C. Computational results highest in the first, second and fourth scenario. This is due to the high costs for the operation and investment trains. The profit and revenue are graphically represented in Figure C.1 and C.2 for the first and fourth scenario from Table C.1. 1 2 3 4 5 6 7 8 9 10 0.6 0.8 1 1.2 1.4 ·1010 instances euros First scenario profit revenue Figure C.1.: Revenue and profit for first scenario of 6 ×2-configuration. 1 2 3 4 5 6 7 8 9 10 1 1.2 1.4 1.6 1.8 ·1010 instances euros Fourth scenario profit revenue Figure C.2.: Revenue and profit for fourth scenario of 6 ×2-configuration. 114 Heuristic Exact Configuration instance fare σ zNET zREV ψℓδℓCPU time nb trips nb Trains zNET zREV ψℓδℓCPU time nb trips nb Trains example6 ×2 seed1 6 1.1 9.06E+09 1.3E+10 [3, 3] [8,5] 0.094 15675 6 9.06E+09 1.3E+10 [3, 3] [8,5] 0.109 15675 6 example6 ×2 seed2 6 1.1 8.22E+09 1.23E+10 [3, 3] [7,5] 0.031 14799 6 8.22E+09 1.23E+10 [3, 3] [7,5] 0.125 14799 6 example6 ×2 seed3 6 1.1 8.03E+09 1.19E+10 [3, 3] [5,5] 0.031 14259 6 8.03E+09 1.19E+10 [3, 3] [5,5] 0.125 14259 6 example6 ×2 seed4 6 1.1 7.21E+09 1.1E+10 [3, 3] [5,3] 0.031 13226 6 7.21E+09 1.1E+10 [3, 3] [5,3] 0.125 13226 6 example6 ×2 seed5 6 1.1 7.49E+09 1.18E+10 [4, 4] [5,4] 0.047 14221 8 7.49E+09 1.18E+10 [4, 4] [5,4] 0.109 14221 8 example6 ×2 seed6 6 1.1 8.16E+09 1.35E+10 [4, 5] [5,3] 0.047 16268 9 8.16E+09 1.35E+10 [4, 5] [5,3] 0.109 16268 9 example6 ×2 seed7 6 1.1 6.84E+09 1.22E+10 [4, 5] [4,3] 0.031 14701 9 6.84E+09 1.22E+10 [4, 5] [4,3] 0.125 14701 9 example6 ×2 seed8 6 1.1 6.03E+09 9.83E+09 [3, 3] [5,3] 0.047 11811 6 6.03E+09 9.83E+09 [3, 3] [5,3] 0.125 11811 6 example6 ×2 seed9 6 1.1 6.6E+09 1.02E+10 [3, 3] [5,3] 0.031 12204 6 6.6E+09 1.02E+10 [3, 3] [5,3] 0.125 12204 6 example6 ×2 seed10 6 1.1 7.41E+09 1.15E+10 [3, 3] [5,4] 0.031 13831 6 7.41E+09 1.15E+10 [3, 3] [5,4] 0.125 13831 6 example6 ×2 seed1 6 1.2 9.24E+09 1.3E+10 [3, 3] [7,4] 0.422 15675 6 9.24E+09 1.3E+10 [3, 3] [7,4] 0.5 15675 6 example6 ×2 seed2 6 1.2 8.41E+09 1.23E+10 [3, 3] [6,4] 0.11 14799 6 8.41E+09 1.23E+10 [3, 3] [6,4] 0.39 14799 6 example6 ×2 seed3 6 1.2 8.11E+09 1.19E+10 [3, 3] [5,4] 0.109 14259 6 8.11E+09 1.19E+10 [3, 3] [5,4] 0.391 14259 6 example6 ×2 seed4 6 1.2 7.21E+09 1.1E+10 [3, 3] [5,3] 0.125 13226 6 7.21E+09 1.1E+10 [3, 3] [5,3] 0.407 13226 6 example6 ×2 seed5 6 1.2 7.57E+09 1.18E+10 [4, 4] [5,3] 0.125 14221 8 7.57E+09 1.18E+10 [4, 4] [5,3] 0.391 14221 8 example6 ×2 seed6 6 1.2 8.16E+09 1.35E+10 [4, 5] [5,3] 0.187 16268 9 8.16E+09 1.35E+10 [4, 5] [5,3] 0.406 16268 9 example6 ×2 seed7 6 1.2 6.84E+09 1.22E+10 [4, 5] [4,3] 0.156 14701 9 6.84E+09 1.22E+10 [4, 5] [4,3] 0.422 14701 9 example6 ×2 seed8 6 1.2 6.03E+09 9.83E+09 [3, 3] [5,3] 0.125 11811 6 6.03E+09 9.83E+09 [3, 3] [5,3] 0.39 11811 6 example6 ×2 seed9 6 1.2 6.6E+09 1.02E+10 [3, 3] [5,3] 0.11 12204 6 6.6E+09 1.02E+10 [3, 3] [5,3] 0.407 12204 6 example6 ×2 seed10 6 1.2 7.52E+09 1.21E+10 [3, 4] [5,3] 0.125 14487 7 7.52E+09 1.21E+10 [3, 4] [5,3] 0.406 14487 7 example6 ×2 seed1 8 1.1 1.37E+10 1.87E+10 [4, 4] [7,4] 0.094 16880 8 1.37E+10 1.87E+10 [4, 4] [7,4] 0.125 16880 8 example6 ×2 seed2 8 1.1 1.23E+10 1.64E+10 [3, 3] [7,5] 0.031 14799 6 1.23E+10 1.64E+10 [3, 3] [7,5] 0.125 14799 6 example6 ×2 seed3 8 1.1 1.22E+10 1.86E+10 [5, 6] [4,3] 0.032 16795 11 1.22E+10 1.86E+10 [5, 6] [4,3] 0.125 16795 11 example6 ×2 seed4 8 1.1 1.09E+10 1.47E+10 [3, 3] [5,3] 0.032 13226 6 1.09E+10 1.47E+10 [3, 3] [5,3] 0.125 13226 6 example6 ×2 seed5 8 1.1 1.14E+10 1.61E+10 [4, 5] [5,3] 0.046 14493 9 1.14E+10 1.61E+10 [4, 5] [5,3] 0.125 14493 9 example6 ×2 seed6 8 1.1 1.27E+10 1.81E+10 [4, 5] [5,3] 0.047 16268 9 1.27E+10 1.81E+10 [4, 5] [5,3] 0.125 16268 9 example6 ×2 seed7 8 1.1 1.09E+10 1.63E+10 [4, 5] [4,3] 0.047 14701 9 1.09E+10 1.63E+10 [4, 5] [4,3] 0.125 14701 9 example6 ×2 seed8 8 1.1 9.47E+09 1.65E+10 [6, 6] [3,2] 0.047 14852 12 9.47E+09 1.65E+10 [6. 6] [3,2] 0.125 14852 12 example6 ×2 seed9 8 1.1 1.01E+10 1.68E+10 [6, 6] [3,3] 0.031 15151 12 1.01E+10 1.68E+10 [6, 6] [3,3] 0.125 15151 12 example6 ×2 seed10 8 1.1 1.14E+10 1.79E+10 [5, 5] [4,3] 0.031 16155 10 1.14E+10 1.61E+10 [3, 4] [6,3] 0.125 14487 7 example6 ×2 seed1 8 1.2 1.38E+10 1.85E+10 [3, 5] [8,3] 0.094 16677 8 1.38E+10 1.85E+10 [3, 5] [8,3] 0.125 16677 8 example6 ×2 seed2 8 1.2 1.25E+10 1.64E+10 [3, 3] [6,4] 0.031 14799 6 1.25E+10 1.64E+10 [3, 3] [6,4] 0.141 14799 6 example6 ×2 seed3 8 1.2 1.22E+10 1.86E+10 [6, 5] [3,3] 0.047 16795 11 1.22E+10 1.86E+10 [6, 5] [3,3] 0.109 16795 11 example6 ×2 seed4 8 1.2 1.09E+10 1.47E+10 [3, 3] [5,3] 0.031 13226 6 1.09E+10 1.47E+10 [3, 3] [5,3] 0.125 13226 6 example6 ×2 seed5 8 1.2 1.15E+10 1.58E+10 [4, 4] [5,3] 0.047 14221 8 1.15E+10 1.58E+10 [4, 4] [5,3] 0.125 14221 8 example6 ×2 seed6 8 1.2 1.27E+10 1.84E+10 [4, 6] [5,2] 0.031 16558 10 1.27E+10 1.84E+10 [4, 6] [5,2] 0.11 16558 10 example6 ×2 seed7 8 1.2 1.1E+10 1.67E+10 [4, 6] [4,2] 0.032 15089 10 1.1E+10 1.67E+10 [4, 6] [4,2] 0.125 15089 10 example6 ×2 seed8 8 1.2 9.55E+09 1.59E+10 [5, 6] [3,2] 0.047 14314 11 9.55E+09 1.59E+10 [5, 6] [3,2] 0.14 14314 11 example6 ×2 seed9 8 1.2 1.03E+10 1.62E+10 [5, 6] [3,2] 0.047 14560 11 1.03E+10 1.62E+10 [5, 6] [3,2] 0.125 14560 11 example6 ×2 seed10 8 1.2 1.17E+10 1.77E+10 [4, 6] [4,2] 0.047 15974 10 1.17E+10 1.77E+10 [4, 6] [4, 2] 0.125 15974 10 Table C.1.: Results for 6 ×2-configuration at uncapacitated case. The following Table C.2 presents a comparison between the exact and heuristic algorithm. The data here deported show that at the 97.5% the heuristic finds the optimal solution and average improve of the CPU time is 65.6%. 115 Chapter C. Computational results Comparison heuristic and exact Configuration instance fare σDif zNET Dif zNET % Dif time Dif time % example6 ×2 seed1 6 1.1 0 0 0.015 13.76147 example6 ×2 seed2 6 1.1 0 0 0.094 75.2 example6 ×2 seed3 6 1.1 0 0 0.094 75.2 example6 ×2 seed4 6 1.1 0 0 0.094 75.2 example6 ×2 seed5 6 1.1 0 0 0.062 56.88073 example6 ×2 seed6 6 1.1 0 0 0.062 56.88073 example6 ×2 seed7 6 1.1 0 0 0.094 75.2 example6 ×2 seed8 6 1.1 0 0 0.078 62.4 example6 ×2 seed9 6 1.1 0 0 0.094 75.2 example6 ×2 seed10 6 1.1 0 0 0.094 75.2 example6 ×2 seed1 6 1.2 0 0 0.078 18.4834 example6 ×2 seed2 6 1.2 0 0 0.28 71.79487 example6 ×2 seed3 6 1.2 0 0 0.282 72.12276 example6 ×2 seed4 6 1.2 0 0 0.282 69.28747 example6 ×2 seed5 6 1.2 0 0 0.266 68.03069 example6 ×2 seed6 6 1.2 0 0 0.219 53.94089 example6 ×2 seed7 6 1.2 0 0 0.266 63.03318 example6 ×2 seed8 6 1.2 0 0 0.265 67.94872 example6 ×2 seed9 6 1.2 0 0 0.297 72.97297 example6 ×2 seed10 6 1.2 0 0 0.281 69.21182 example6 ×2 seed1 8 1.1 0 0 0.031 24.8 example6 ×2 seed2 8 1.1 0 0 0.094 75.2 example6 ×2 seed3 8 1.1 0 0 0.093 74.4 example6 ×2 seed4 8 1.1 0 0 0.093 74.4 example6 ×2 seed5 8 1.1 0 0 0.079 63.2 example6 ×2 seed6 8 1.1 0 0 0.078 62.4 example6 ×2 seed7 8 1.1 0 0 0.078 62.4 example6 ×2 seed8 8 1.1 0 0 0.078 62.4 example6 ×2 seed9 8 1.1 0 0 0.094 75.2 example6 ×2 seed10 8 1.1 8183830 0.071632 0.094 75.2 example6 ×2 seed1 8 1.2 0 0 0.031 24.8 example6 ×2 seed2 8 1.2 0 0 0.11 78.01418 example6 ×2 seed3 8 1.2 0 0 0.062 56.88073 example6 ×2 seed4 8 1.2 0 0 0.094 75.2 example6 ×2 seed5 8 1.2 0 0 0.078 62.4 example6 ×2 seed6 8 1.2 0 0 0.079 71.81818 example6 ×2 seed7 8 1.2 0 0 0.093 74.4 example6 ×2 seed8 8 1.2 0 0 0.093 66.42857 example6 ×2 seed9 8 1.2 0 0 0.078 62.4 example6 ×2 seed10 8 1.2 0 0 0.078 62.4 Table C.2.: Comparison exact and heuristic for 6 ×2-configuration at uncapacitated case. 7×3-configuration At this configuration the average CPU time for the heuristic is 0.16995 and for the exact is 3.48045 seconds. That is, the heuristic improves the average CPU time in 95.12% respect to the exact. Detailed information on these solutions are shown in Table C.3. Note that due to the way in which we estimate the demand attraction (logit function) the higher the frequencies are, the higher the number of trips are. However, the maximum net profit and revenue is obtained for the Seed6-instance with minimum frequencies at all scenarios. The interpretation of this result is the following. As demand captured with minimum frequencies is high ( 81.57%), the number of carriages must be high since the number of trains is only 9 (see Table C.3). In this case, it does not compensate to attract more passengers since this fact would imply more trains and, therefore, more 116 costs. Observe that it is cheaper trains with many carriages than many trains with few carriages. Heuristic Exact Configuration instance fare σ zNET zREV ψℓδℓCPU time nb trips nb Trains zNET zREV ψℓδℓCPU time nb trips nb Trains example7 ×3 seed1 6 1.1 7.89E+09 1.54E+10 [3, 3, 3] [6,5,4] 0.219 18537 9 8.62E+09 1.8E+10 [3, 5, 4] [6,3,4] 3.562 21664 12 example7 ×3 seed2 6 1.1 9.99E+09 1.77E+10 [3, 3, 3] [6,6,5] 0.172 21302 9 9.99E+09 1.77E+10 [3, 3, 3] [6,6,5] 3.516 21302 9 example7 ×3 seed3 6 1.1 8.76E+09 1.57E+10 [3, 3, 3] [6,4,4] 0.172 18898 9 8.76E+09 1.57E+10 [3, 3, 3] [6,4,4] 3.484 18898 9 example7 ×3 seed4 6 1.1 8.35E+09 1.54E+10 [3, 3, 3] [6,5,4] 0.156 18547 9 8.57E+09 1.75E+10 [3, 4, 5] [6,5,3] 3.484 21011 12 example7 ×3 seed5 6 1.1 8.7E+09 1.61E+10 [3, 3, 3] [5,5,5] 0.156 19287 9 8.7E+09 1.61E+10 [3, 3, 3] [5,5,5] 3.485 19287 9 example7 ×3 seed6 6 1.1 1.11E+10 1.91E+10 [3, 3, 3] [6,6,6] 0.157 22918 9 1.11E+10 1.91E+10 [3, 3, 3] [6,6,6] 3.484 22918 9 example7 ×3 seed7 6 1.1 8.05E+09 1.54E+10 [3, 3, 3] [5,5,4] 0.172 18537 9 8.05E+09 1.54E+10 [3, 3, 3] [5,5,4] 3.484 18537 9 example7 ×3 seed8 6 1.1 8.91E+09 1.62E+10 [3, 3, 3] [5,4,5] 0.156 19520 9 8.91E+09 1.62E+10 [3, 3, 3] [5,4,5] 3.485 19520 9 example7 ×3 seed9 6 1.1 8.36E+09 1.58E+10 [3, 3, 3] [5,5,5] 0.157 18972 9 8.36E+09 1.58E+10 [3, 3, 3] [5,5,5] 3.515 18972 9 example7 ×3 seed10 6 1.1 9.4E+09 1.72E+10 [3, 3, 3] [6,4,5] 0.156 20686 9 9.4E+09 1.72E+10 [3, 3, 3] [6,4,5] 3.516 20686 9 example7 ×3 seed1 6 1.2 8.14E+09 1.54E+10 [3, 3, 3] [5,4,4] 0.203 18537 9 8.85E+09 1.88E+10 [3, 5, 5] [5,3,4] 3.5 22606 13 example7 ×3 seed2 6 1.2 1.01E+10 1.77E+10 [3, 3, 3] [6,5,5] 0.172 21302 9 1.01E+10 1.77E+10 [3, 3, 3] [6,5,5] 3.438 21302 9 example7 ×3 seed3 6 1.2 8.89E+09 1.57E+10 [3, 3, 3] [5,4,4] 0.157 18898 9 8.89E+09 1.57E+10 [3, 3, 3] [5,4,4] 3.453 18898 9 example7 ×3 seed4 6 1.2 8.49E+09 1.54E+10 [3, 3, 3] [5,5,4] 0.157 18547 9 8.71E+09 1.75E+10 [3, 4, 5] [5,5,3] 3.484 21011 12 example7 ×3 seed5 6 1.2 8.7E+09 1.61E+10 [3, 3, 3] [5,5,5] 0.156 19287 9 8.7E+09 1.61E+10 [3, 3, 3] [5,5,5] 3.484 19287 9 example7 ×3 seed6 6 1.2 1.12E+10 1.91E+10 [3, 3, 3] [6,5,6] 0.172 22918 9 1.12E+10 1.91E+10 [3, 3, 3] [6,5,6] 3.469 22918 9 example7 ×3 seed7 6 1.2 8.15E+09 1.54E+10 [3, 3, 3] [5,4,4] 0.156 18537 9 8.15E+09 1.54E+10 [3, 3, 3] [5,4,4] 3.469 18537 9 example7 ×3 seed8 6 1.2 8.91E+09 1.62E+10 [3, 3, 3] [5,4,5] 0.172 19520 9 8.91E+09 1.62E+10 [3, 3, 3] [5,4,5] 3.484 19520 9 example7 ×3 seed9 6 1.2 8.36E+09 1.58E+10 [3, 3, 3] [5,5,5] 0.156 18972 9 8.36E+09 1.58E+10 [3, 3, 3] [5,5,5] 3.485 18972 9 example7 ×3 seed10 6 1.2 9.4E+09 1.72E+10 [3, 3, 3] [6,4,5] 0.172 20686 9 9.4E+09 1.72E+10 [3, 3, 3] [6,4,5] 3.468 20686 9 example7 ×3 seed1 8 1.1 1.48E+10 2.51E+10 [3, 5, 5] [6,4,4] 0.281 22606 13 1.48E+10 2.51E+10 [3, 5, 5] [6,4,4] 3.5 22606 13 example7 ×3 seed2 8 1.1 1.59E+10 2.36E+10 [3, 3, 3] [6,6,5] 0.156 21302 9 1.59E+10 2.36E+10 [3, 3, 3] [6,6,5] 3.453 21302 9 example7 ×3 seed3 8 1.1 1.4E+10 2.1E+10 [3, 3, 3] [6,4,4] 0.172 18898 9 1.4E+10 2.1E+10 [3, 3, 3] [6,4,4] 3.469 18898 9 example7 ×3 seed4 8 1.1 1.35E+10 2.06E+10 [3, 3, 3] [6,5,4] 0.156 18547 9 1.44E+10 2.33E+10 [3, 4, 5] [6,5,3] 3.469 21011 12 example7 ×3 seed5 8 1.1 1.4E+10 2.14E+10 [3, 3, 3] [5,5,5] 0.157 19287 9 1.4E+10 2.14E+10 [3, 3, 3] [5,5,5] 3.484 19287 9 example7 ×3 seed6 8 1.1 1.75E+10 2.54E+10 [3, 3, 3] [6,6,6] 0.156 22918 9 1.75E+10 2.54E+10 [3, 3, 3] [6,6,6] 3.469 22918 9 example7 ×3 seed7 8 1.1 1.32E+10 2.06E+10 [3, 3, 3] [5,5,4] 0.156 18537 9 1.32E+10 2.06E+10 [3, 3, 3] [5,5,4] 3.485 18537 9 example7 ×3 seed8 8 1.1 1.43E+10 2.17E+10 [3, 3, 3] [5,4,5] 0.156 19520 9 1.45E+10 2.43E+10 [3, 5, 5] [5,3,4] 3.484 21923 13 example7 ×3 seed9 8 1.1 1.37E+10 2.18E+10 [3, 3, 4] [5,6,4] 0.172 19685 10 1.37E+10 2.18E+10 [3, 3, 4] [5,6,4] 3.469 19685 10 example7 ×3 seed10 8 1.1 1.53E+10 2.37E+10 [3, 4, 3] [6,3,5] 0.172 21329 10 1.53E+10 2.37E+10 [3. 4. 3] [6,3,5] 3,515 21329 10 example7 ×3 seed1 8 1.2 1.51E+10 2.51E+10 [3, 5, 5] [5,3,4] 0.25 22606 13 1.51E+10 2.51E+10 [3, 5, 5] [5,3,4] 3.468 22606 13 example7 ×3 seed2 8 1.2 1.6E+10 2.36E+10 [3, 3, 3] [6,5,5] 0.156 21302 9 1.6E+10 2.36E+10 [3, 3, 3] [6,5,5] 3.438 21302 9 example7 ×3 seed3 8 1.2 1.41E+10 2.1E+10 [3, 3, 3] [5,4,4] 0.157 18898 9 1.41E+10 2.1E+10 [3, 3, 3] [5,4,4] 3.484 18898 9 example7 ×3 seed4 8 1.2 1.36E+10 2.06E+10 [3, 3, 3] [5,5,4] 0.156 18547 9 1.45E+10 2.33E+10 [3, 4, 5] [5,5,3] 3.5 21011 12 example7 ×3 seed5 8 1.2 1.4E+10 2.14E+10 [3, 3, 3] [5,5,5] 0.172 19287 9 1.4E+10 2.14E+10 [3, 3, 3] [5,5,5] 3.469 19287 9 example7 ×3 seed6 8 1.2 1.76E+10 2.54E+10 [3, 3, 3] [6,5,6] 0.156 22918 9 1.76E+10 2.54E+10 [3, 3, 3] [6,5,6] 3.453 22918 9 example7 ×3 seed7 8 1.2 1.33E+10 2.06E+10 [3, 3, 3] [5,4,4] 0.172 18537 9 1.33E+10 2.06E+10 [3, 3, 3] [5,4,4] 3.438 18537 9 example7 ×3 seed8 8 1.2 1.43E+10 2.17E+10 [3, 3, 3] [5,4,5] 0.156 19520 9 1,47E+10 2.43E+10 [3, 5, 5] [5,3,3] 3.469 21923 13 example7 ×3 seed9 8 1.2 1.38E+10 2.18E+10 [3, 3, 4] [5,5,4] 0.171 19685 10 1.38E+10 2.18E+10 [3, 3, 4] [5,5,4] 3,469 19685 10 example7 ×3 seed10 8 1.2 1.53E+10 2.37E+10 [3, 4, 3] [6,3,5] 0.172 21329 10 1.53E+10 2.37E+10 [3, 4, 3] [6,3,5] 3.484 21329 10 Table C.3.: Results for 7 ×3 configuration at uncapacitated case. The following Table C.4 presents a comparison between the exact and heuristic algorithm. The data here deported show that at the 80% the heuristic finds the optimal solution and average improve of the CPU time is 95.11%. The average error at these 117 Chapter C. Computational results cases is 4.7%. Comparison heuristic and exact Configuration instance fare σDif zNET Dif zNET % Dif time Dif time % example7 ×3 seed1 6 1.1 7.25E+08 8.414799 3.343 93.85177 example7 ×3 seed2 6 1.1 0 0 3.344 95.10808 example7 ×3 seed3 6 1.1 0 0 3.312 95.06315 example7 ×3 seed4 6 1.1 2.22E+08 2.594155 3.328 95.52239 example7 ×3 seed5 6 1.1 0 0 3.329 95.52367 example7 ×3 seed6 6 1.1 0 0 3.327 95.49369 example7 ×3 seed7 6 1.1 0 0 3.312 95.06315 example7 ×3 seed8 6 1.1 0 0 3.329 95.52367 example7 ×3 seed9 6 1.1 0 0 3.358 95.53343 example7 ×3 seed10 6 1.1 0 0 3.36 95.56314 example7 ×3 seed1 6 1.2 7.02E+08 7.935962 3.297 94.2 example7 ×3 seed2 6 1.2 0 0 3.266 94.99709 example7 ×3 seed3 6 1.2 0 0 3.296 95.45323 example7 ×3 seed4 6 1.2 2.22E+08 2.552337 3.327 95.49369 example7 ×3 seed5 6 1.2 0 0 3.328 95.52239 example7 ×3 seed6 6 1.2 0 0 3.297 95.0418 example7 ×3 seed7 6 1.2 0 0 3.313 95.50303 example7 ×3 seed8 6 1.2 0 0 3.312 95.06315 example7 ×3 seed9 6 1.2 0 0 3.329 95.52367 example7 ×3 seed10 6 1.2 0 0 3.296 95.04037 example7 ×3 seed1 8 1.1 0 0 3.219 91.97143 example7 ×3 seed2 8 1.1 0 0 3.297 95.48219 example7 ×3 seed3 8 1.1 0 0 3.297 95.0418 example7 ×3 seed4 8 1.1 9.06E+08 6.291492 3.313 95.50303 example7 ×3 seed5 8 1.1 0 0 3.327 95.49369 example7 ×3 seed6 8 1.1 0 0 3.313 95.50303 example7 ×3 seed7 8 1.1 0 0 3.329 95.52367 example7 ×3 seed8 8 1.1 1.74E+08 1.199384 3.328 95.52239 example7 ×3 seed9 8 1.1 0 0 3.297 95.0418 example7 ×3 seed10 8 1.1 0 0 3.343 95.10669 example7 ×3 seed1 8 1.2 0 0 3.218 92.79123 example7 ×3 seed2 8 1.2 0 0 3.282 95.46248 example7 ×3 seed3 8 1.2 0 0 3.327 95.49369 example7 ×3 seed4 8 1.2 9.06E+08 6.230734 3.344 95.54286 example7 ×3 seed5 8 1.2 0 0 3.297 95.0418 example7 ×3 seed6 8 1.2 0 0 3.297 95.48219 example7 ×3 seed7 8 1.2 0 0 3.266 94.99709 example7 ×3 seed8 8 1.2 3.48E+08 2.372124 3.313 95.50303 example7 ×3 seed9 8 1.2 0 0 3.298 95.07063 example7 ×3 seed10 8 1.2 0 0 3.312 95.06315 Table C.4.: Comparison exact and heuristic for 7 ×3-configuration at uncapacitated case. 8×3-configuration The data related to this configuration are shown in the Table C.5. The maximum net profit and revenue are obtained for the Seed9-instance in the third first scenarios. The captured demand represents at these cases the 61.67% on the total trips number. In the last scenario, the maximum revenue is searched for Seed3-instance (63.85% demand) and the maximum net profit for the Seed9-instance. The average CPU time in the heuristic is 0.2836 and the exact is 5.89 seconds, which represents an improvement of 95.18% in the time. 118 Heuristic Exact Configuration instance fare σ zNET zREV ψℓδℓCPU time nb trips nb Trains zNET zREV ψℓδℓCPU time nb trips nb Trains example8 ×3 seed1 6 1.1 5.09E+09 1.14E+10 [3, 3, 3] [2,4,3] 0.359 13724 9 5.09E+09 1.14E+10 [3, 3, 3] [2,4,3] 5.75 13724 9 example8 ×3 seed2 6 1.1 4.78E+09 1.16E+10 [3, 3, 3] [3,5,3] 0.266 13922 9 4.78E+09 1.16E+10 [3, 3, 3] [3,5,3] 5.906 13922 9 example8 ×3 seed3 6 1.1 7.99E+09 1.46E+10 [4, 3, 3] [3,5,5] 0.281 17521 10 7.99E+09 1.46E+10 [4, 3, 3] [3,5,5] 5.828 17521 10 example8 ×3 seed4 6 1.1 8.26E+09 1.48E+10 [4, 3, 3] [3,5,5] 0.282 17756 10 8.26E+09 1.48E+10 [4, 3, 3] [3,5,5] 5.984 17756 10 example8 ×3 seed5 6 1.1 6.96E+09 1.27E+10 [3, 3, 3] [3,4,3] 0.281 15229 9 6.96E+09 1.27E+10 [3, 3, 3] [3,4,3] 6.015 15229 9 example8 ×3 seed6 6 1.1 7.34E+09 1.39E+10 [3, 3, 3] [3,6,3] 0.266 16749 9 7.34E+09 1.39E+10 [3, 3, 3] [3,6,3] 5.781 16749 9 example8 ×3 seed7 6 1.1 6.14E+09 1.27E+10 [3, 3, 3] [2,5,3] 0.265 15257 9 6.14E+09 1.27E+10 [3, 3, 3] [2,5,3] 5.782 15257 9 example8 ×3 seed8 6 1.1 5.85E+09 1.31E+10 [4, 3, 3] [3,5,4] 0.266 15742 10 5.85E+09 1.31E+10 [4, 3, 3] [3,5,4] 5.781 15742 10 example8 ×3 seed9 6 1.1 9.95E+09 1.59E+10 [3, 3, 3] [5,5,4] 0.266 19115 9 9.95E+09 1.59E+10 [3, 3, 3] [5,5,4] 5.859 19115 9 example8 ×3 seed10 6 1.1 7.58E+09 1.45E+10 [3, 3, 3] [5,6,4] 0.281 17388 9 7.58E+09 1.45E+10 [3, 3, 3] [5,6,4] 6.078 17388 9 example8 ×3 seed1 6 1.2 5.09E+09 1.14E+10 [3, 3, 3] [2,4,3] 0.328 13724 9 5.09E+09 1.14E+10 [3, 3, 3] [2,4,3] 5.859 13724 9 example8 ×3 seed2 6 1.2 4.91E+09 1.16E+10 [3, 3, 3] [2,5,3] 0.266 13922 9 4.91E+09 1.16E+10 [3, 3, 3] [2,5,3] 5.922 13922 9 example8 ×3 seed3 6 1.2 8.07E+09 1.46E+10 [4, 3, 3] [3,5,4] 0.281 17521 10 8.07E+09 1.46E+10 [4, 3, 3] [3,5,4] 5.828 17521 10 example8 ×3 seed4 6 1.2 8.38E+09 1.42E+10 [3, 3, 3] [3,5,4] 0.266 17103 9 8.38E+09 1.42E+10 [3, 3, 3] [3,5,4] 5.922 17103 9 example8 ×3 seed5 6 1.2 7.02E+09 1.27E+10 [3, 3, 3] [3,4,2] 0.281 15229 9 7.02E+09 1.27E+10 [3, 3, 3] [3,4,2] 6.141 15229 9 example8 ×3 seed6 6 1.2 7.34E+09 1.39E+10 [3, 3, 3] [3,6,3] 0.265 16749 9 7.34E+09 1.39E+10 [3, 3, 3] [3,6,3] 5.719 16749 9 example8 ×3 seed7 6 1.2 6.14E+09 1.27E+10 [3, 3, 3] [2,5,3] 0.265 15257 9 6.14E+09 1.27E+10 [3, 3, 3] [2,5,3] 5.766 15257 9 example8 ×3 seed8 6 1.2 5.99E+09 1.31E+10 [4, 3, 3] [3,4,4] 0.266 15742 10 6E+09 1.42E+10 [5, 3, 4] [3,4,3] 5.781 17105 12 example8 ×3 seed9 6 1.2 1E+10 1.59E+10 [3, 3, 3] [4,5,4] 0.265 19115 9 1E+10 1.59E+10 [3, 3, 3] [4,5,4] 5.813 19115 9 example8 ×3 seed10 6 1.2 7.83E+09 1.45E+10 [3, 3, 3] [4,5,4] 0.281 17388 9 7.83E+09 1.45E+10 [3, 3, 3] [4,5,4] 6.063 17388 9 example8 ×3 seed1 8 1.1 8.89E+09 1.52E+10 [3, 3, 3] [2,4,3] 0.312 13724 9 8.89E+09 1.52E+10 [3, 3, 3] [2,4,3] 5.719 13724 9 example8 ×3 seed2 8 1.1 8.65E+09 1.54E+10 [3, 3, 3] [3,5,3] 0.265 13922 9 8.65E+09 1.54E+10 [3, 3, 3] [3,5,3] 5.875 13922 9 example8 ×3 seed3 8 1.1 1.29E+10 2.01E+10 [5, 3, 3] [3,5,5] 0.281 18153 11 1.29E+10 2.01E+10 [5, 3, 3] [3,5,5] 5.781 18153 11 example8 ×3 seed4 8 1.1 1.35E+10 2.1E+10 [5, 3, 4] [3,5,4] 0.297 18944 12 1.37E+10 2.18E+10 [6, 3, 4] [3,5,4] 5.875 19651 13 example8 ×3 seed5 8 1.1 1.12E+10 1.69E+10 [3, 3, 3] [3,4,3] 0.266 15229 9 1.12E+10 1.69E+10 [3, 3, 3] [3,4,3] 6.047 15229 9 example8 ×3 seed6 8 1.1 1.2E+10 1.86E+10 [3, 3, 3] [3,6,3] 0.266 16749 9 1.2E+10 1.86E+10 [3, 3, 3] [3,6,3] 5.703 16749 9 example8 ×3 seed7 8 1.1 1.04E+10 1.69E+10 [3, 3, 3] [2,5,3] 0.265 15257 9 1.04E+10 1.69E+10 [3, 3, 3] [2,5,3] 5.828 15257 9 example8 ×3 seed8 8 1.1 1.05E+10 1.9E+10 [5, 3, 4] [3,5,4] 0.313 17105 12 1.05E+10 1.9E+10 [5, 3, 4] [3,5,4] 5.734 17105 12 example8 ×3 seed9 8 1.1 1.53E+10 2.12E+10 [3, 3, 3] [5,5,4] 0.266 19115 9 1.53E+10 2.12E+10 [3, 3, 3] [5,5,4] 5.859 19115 9 example8 ×3 seed10 8 1.1 1.24E+10 1.93E+10 [3, 3, 3] [5,6,4] 0.266 17388 9 1.24E+10 1.93E+10 [3, 3, 3] [5,6,4] 6.125 17388 9 example8 ×3 seed1 8 1.2 8.89E+09 1.52E+10 [3, 3, 3] [2, 4, 3] 0.328 13724 9 8.89E+09 1.52E+10 [3, 3, 3] [2,4,3] 5.813 13724 9 example8 ×3 seed2 8 1.2 8.77E+09 1.54E+10 [3, 3, 3] [2,5,3] 0.266 13922 9 8.77E+09 1.54E+10 [3, 3, 3] [2,5,3] 5.875 13922 9 example8 ×3 seed3 8 1.2 1.3E+10 2.01E+10 [5, 3, 3] [3,5,4] 0.329 18153 11 1.3E+10 2.01E+10 [5, 3, 3] [3,5,4] 5.89 18153 11 example8 ×3 seed4 8 1.2 1.37E+10 2.18E+10 [6, 3, 4] [3,5,4] 0.328 19651 13 1.37E+10 2.18E+10 [6, 3, 4] [3,5,4] 5.938 19651 13 example8 ×3 seed5 8 1.2 1.13E+10 1.76E+10 [4, 3, 3] [2,5,2] 0.281 15846 10 1.13E+10 1.76E+10 [4, 3, 3] [2,5,2] 6.172 15846 10 example8 ×3 seed6 8 1.2 1.2E+10 1.86E+10 [3, 3, 3] [3,6,3] 0.266 16749 9 1.2E+10 1.86E+10 [3, 3, 3] [3,6,3] 5.843 16749 9 example8 ×3 seed7 8 1.2 1.04E+10 1.69E+10 [3, 3, 3] [2,5,3] 0.297 15257 9 1.04E+10 1.69E+10 [3, 3, 3] [2,5,3] 5.984 15257 9 example8 ×3 seed8 8 1.2 1.07E+10 1.9E+10 [5, 3, 4] [3,4,3] 0.313 17105 12 1.07E+10 1.9E+10 [5, 3, 4] [3,4,3] 5.812 17105 12 example8 ×3 seed9 8 1.2 1.53E+10 2.12E+10 [3, 3, 3] [4,5,4] 0.281 19115 9 1.53E+10 2.12E+10 [3, 3, 3] [4,5,4] 5.844 19115 9 example8 ×3 seed10 8 1.2 1.27E+10 1.93E+10 [3, 3, 3] [4,5,4] 0.281 17388 9 1.27E+10 1.93E+10 [3, 3, 3] [4,5,4] 6.11 17388 9 Table C.5.: Results for 8 ×3-configuration at uncapacitated case. Table C.6 shows relevant details in order to compare the exact and heuristic algorithm. It can be observed that the optimal solution is found in 95% of the carried out experiments and the average improve of the CPU time is 95.18%. 119 Chapter C. Computational results Comparison heuristic and exact Configuration instance fare σDif zNET Dif zNET % Dif time Dif time % example8 ×3 seed1 6 1.1 0 0 5.391 93.75652 example8 ×3 seed2 6 1.1 0 0 5.64 95.49611 example8 ×3 seed3 6 1.1 0 0 5.547 95.17845 example8 ×3 seed4 6 1.1 0 0 5.702 95.28743 example8 ×3 seed5 6 1.1 0 0 5.734 95.32835 example8 ×3 seed6 6 1.1 0 0 5.515 95.39872 example8 ×3 seed7 6 1.1 0 0 5.517 95.41681 example8 ×3 seed8 6 1.1 0 0 5.515 95.39872 example8 ×3 seed9 6 1.1 0 0 5.593 95.45998 example8 ×3 seed10 6 1.1 0 0 5.797 95.37677 example8 ×3 seed1 6 1.2 0 0 5.531 94.40178 example8 ×3 seed2 6 1.2 0 0 5.656 95.50827 example8 ×3 seed3 6 1.2 0 0 5.547 95.17845 example8 ×3 seed4 6 1.2 0 0 5.656 95.50827 example8 ×3 seed5 6 1.2 0 0 5.86 95.4242 example8 ×3 seed6 6 1.2 0 0 5.454 95.36632 example8 ×3 seed7 6 1.2 0 0 5.501 95.40409 example8 ×3 seed8 6 1.2 16537852 0.275527 5.515 95.39872 example8 ×3 seed9 6 1.2 0 0 5.548 95.44125 example8 ×3 seed10 6 1.2 0 0 5.782 95.36533 example8 ×3 seed1 8 1.1 0 0 5.407 94.5445 example8 ×3 seed2 8 1.1 0 0 5.61 95.48936 example8 ×3 seed3 8 1.1 0 0 5.5 95.13925 example8 ×3 seed4 8 1.1 1.93E+08 1.41026 5.578 94.94468 example8 ×3 seed5 8 1.1 0 0 5.781 95.60112 example8 ×3 seed6 8 1.1 0 0 5.437 95.33579 example8 ×3 seed7 8 1.1 0 0 5.563 95.45299 example8 ×3 seed8 8 1.1 0 0 5.421 94.54133 example8 ×3 seed9 8 1.1 0 0 5.593 95.45998 example8 ×3 seed10 8 1.1 0 0 5.859 95.65714 example8 ×3 seed1 8 1.2 0 0 5.485 94.35747 example8 ×3 seed2 8 1.2 0 0 5.609 95.47234 example8 ×3 seed3 8 1.2 0 0 5.561 94.41426 example8 ×3 seed4 8 1.2 0 0 5.61 94.47625 example8 ×3 seed5 8 1.2 0 0 5.891 95.44718 example8 ×3 seed6 8 1.2 0 0 5.577 95.44754 example8 ×3 seed7 8 1.2 0 0 5.687 95.03676 example8 ×3 seed8 8 1.2 0 0 5.499 94.61459 example8 ×3 seed9 8 1.2 0 0 5.563 95.19165 example8 ×3 seed10 8 1.2 0 0 5.829 95.40098 Table C.6.: Comparison exact and heuristic for 8 ×3-configuration at uncapacitated case. 15 ×5-configuration In this section, we have tested our algorithms on networks with 15 nodes and 5 lines. The results of these experiments are shown in Table C.7. It can be observed that our heuristic was able to find the optimal solution for most of instances (90%). The maximum profit is searched for the Seed-4 instance at all scenarios. However, the maximum revenue is obtained for Seed2-instance in the first, second and third scenario and Seed8-instance for the last scenario. In Figure C.3 and C.4 the revenue and profit are graphically represented for the first and fourth scenario, respectively. 120 Configuration 6 ×2, σ= 1.1, fare=6 instance δmax profit revenue ψℓδℓnoiterations CPU time nb trips % demand nb trains seed1 8 9.06E+09 1.3E+10 [3, 3] [8, 5] 0 5.344 15675 77.46 6 seed2 7 8.22E+09 1.23E+10 [3, 3] [7, 5] 0 4.156 14799 72.11 6 seed2 8 8.22E+09 1.23E+10 [3, 3] [7, 5] 0 5.593 14799 72.11 6 seed3 5 8.03E+09 1.19E+10 [3, 3] [5, 5] 0 2.078 14259 65.22 6 seed3 6 8.03E+09 1.19E+10 [3, 3] [5, 5] 0 3.25 14259 65.22 6 seed3 7 8.03E+09 1.19E+10 [3, 3] [5, 5] 0 4.625 14259 65.22 6 seed3 8 8.03E+09 1.19E+10 [3, 3] [5, 5] 0 6.157 14259 65.22 6 seed4 5 7.21E+09 1.1E+10 [3, 3] [5, 3] 0 2.187 13226 63.29 6 seed4 6 7.21E+09 1.1E+10 [3, 3] [5, 3] 0 3.469 13226 63.29 6 seed4 7 7.21E+09 1.1E+10 [3, 3] [5, 3] 0 4.86 13226 63.29 6 seed4 8 7.21E+09 1.1E+10 [3, 3] [5, 3] 0 6.625 13226 63.29 6 seed5 6 7.49E+09 1.18E+10 [4, 4] [5, 4] 0 3.125 14221 70.85 8 seed5 7 7.49E+09 1.18E+10 [4, 4] [5, 4] 0 4.468 14221 70.85 8 seed5 8 7.49E+09 1.18E+10 [4, 4] [5, 4] 0 6.093 14221 70.85 8 seed6 6 8.16E+09 1.35E+10 [4, 5] [5, 3] 0 3.172 16268 79.15 9 seed6 7 8.16E+09 1.35E+10 [4, 5] [5, 3] 0 4.5 16268 79.15 9 seed6 8 8.16E+09 1.35E+10 [4, 5] [5, 3] 0 6.157 16268 79.15 9 seed7 5 6.84E+09 1.22E+10 [4, 5] [4, 3] 0 2.14 14701 69.1 9 seed7 6 6.84E+09 1.22E+10 [4, 5] [4, 3] 0 3.328 14701 69.1 9 seed7 7 6.84E+09 1.22E+10 [4, 5] [4, 3] 0 4.735 14701 69.1 9 seed7 8 6.84E+09 1.22E+10 [4, 5] [4, 3] 0 6.328 14701 69.1 9 seed8 5 6.03E+09 9.83E+09 [3, 3] [5, 3] 0 2.172 11811 58.4 6 seed8 6 6.03E+09 9.83E+09 [3, 3] [5, 3] 0 3.375 11811 58.4 6 seed8 7 6.03E+09 9.83E+09 [3, 3] [5, 3] 0 4.765 11811 58.4 6 seed8 8 6.03E+09 9.83E+09 [3, 3] [5, 3] 0 6.406 11811 58.4 6 seed9 5 6.6E+09 1.02E+10 [3, 3] [5, 3] 0 2.14 12204 58.4 6 seed9 6 6.6E+09 1.02E+10 [3, 3] [5, 3] 0 3.297 12204 58.4 6 seed9 7 6.6E+09 1.02E+10 [3, 3] [5, 3] 0 4.703 12204 58.4 6 seed9 8 6.6E+09 1.02E+10 [3, 3] [5, 3] 0 6.391 12204 58.4 6 seed10 5 7.41E+09 1.15E+10 [3, 3] [5, 4] 0 2.11 13831 66.5 6 seed10 6 7.41E+09 1.15E+10 [3, 3] [5, 4] 0 3.281 13831 66.5 6 seed10 7 7.41E+09 1.15E+10 [3, 3] [5, 4] 0 4.688 13831 66.5 6 seed10 8 7.41E+09 1.15E+10 [3, 3] [5, 4] 0 6.453 13831 66.5 6 Table C.11.: Results for 6 ×2-configuration at capacitated case. 127 Chapter C. Computational results by the in-vehicle crowding when the congestion is introduced in our problem as show Tables C.13 and C.14. For instance, it can be observed that the optimal solution for seed1-configuration at the capacitated case has one more carriage than the uncapacitated case. In other words, when the congestion is taken into account, the passenger’s behavior changes, and it is more economically interesting to add a carriage than to lose passengers. 1 2 3 4 5 6 7 10 109.6 109.8 1010 instances euros First scenario uncapacitated capacitated uncapacitated with congestion Figure C.6.: Profit for 7 ×3-configuration. Optimal solution for uncapacitated problem, capacitated problem and the uncongestion optimal solution with the congestion effect. deltaMax=5 profit revenue passengers nb iterations seed5 7.23E+09 1.46E+10 17525 1 seed7 3.50E+09 1.09E+10 13075 2 Table C.13.: Results for uncapacitated optimal solutions of 7×3-configuration with crowding and δmax = 5. 128 Configuration 7 ×3, sigma 1.1, fare=6 instance δmax profit revenue ψℓδℓnoiterations CPU time nb trips nb trains seed1 2 -2.11E+09 1.93E+10 [10, 10, 10] [2, 2, 2] 0 10.688 23221 30 seed1 3 3.44E+09 1.93E+10 [6, 6, 10] [3, 3, 2] 0 41.562 23208 22 seed1 4 7.86E+09 1.88E+10 [4, 5, 5] [4, 4, 4] 0 124.797 22606 14 seed1 5 7.86E+09 1.88E+10 [4, 5, 5] [4, 4, 4] 0 242.328 22606 14 seed1 6 8.52E+09 1.88E+10 [3, 5, 5] [6, 4, 4] 0 289.381 22606 seed2 1 -2.05E+10 1.69E+10 [20, 20, 15] [1, 1, 1] 2 1.047 20348 55 seed2 2 -3.68E+09 1.77E+10 [10, 10, 10] [2, 2, 2] 0 10.906 21304 30 seed2 3 4.18E+09 1.77E+10 [6, 6, 6] [3, 3, 3] 0 43.265 21302 18 seed2 4 6.55E+09 1.77E+10 [5, 4, 5] [4, 4, 4] 0 123.516 21302 14 seed2 5 7.89E+09 1.77E+10 [4, 4, 4] [5, 4, 5] 0 259.11 21302 12 seed2 6 9.89E+09 1.77E+10 [3, 3, 3] [6, 6, 6] 0 300.52 21302 seed3 2 -2.43E+09 1.77E+10 [10, 10, 10] [2, 2, 2] 0 10.984 21258 30 seed3 3 4.90E+09 1.64E+10 [6, 5, 5] [3, 3, 3] 0 43.25 19656 16 seed3 4 7.37E+09 1.63E+10 [4, 4, 4] [4, 4, 4] 0 125.781 19590 12 seed3 5 8.03E+09 1.57E+10 [4, 3, 3] [4, 4, 5] 0 263.515 18898 10 seed3 6 8.66E+09 1.57E+10 [3, 3, 3] [6, 4, 5] 0 299.444 18898 seed4 2 -3.14E+09 1.81E+10 [10, 12, 10] [2, 2, 2] 0 10.36 21803 32 seed4 3 2.83E+09 1.80E+10 [6, 10, 6] [3, 3, 3] 0 40.359 21622 22 seed4 4 7.90E+09 1.75E+10 [4, 5, 4] [4, 4, 4] 0 111.406 21011 14 seed4 5 7.90E+09 1.75E+10 [4, 5, 4] [4, 4, 4] 0 239.375 21011 14 seed4 6 8.56E+09 1.75E+10 [3, 5, 4] [6, 4, 4] 0 271.957 21011 seed5 1 -1.75E+10 1.81E+10 [15, 20, 20] [1, 1, 1] 1 1.187 21697 55 seed5 2 -2.91E+09 1.81E+10 [10, 10, 10] [2, 2, 2] 0 11.734 21767 30 seed5 3 4.61E+09 1.64E+10 [5, 5, 6] [3, 3, 3] 0 47.063 19719 16 seed5 4 6.72E+09 1.61E+10 [4, 4, 4] [4, 4, 4] 0 127.765 19299 12 seed5 5 8.07E+09 1.61E+10 [3, 3, 4] [5, 5, 4] 0 284.297 19291 10 seed5 6 8.59E+09 1.61E+10 [3, 3, 3] [5, 5, 6] 0 313.92 19287 seed6 2 -2.50E+09 1.92E+10 [10, 10, 10] [2, 2, 2] 0 10.547 23056 30 seed6 3 3.07E+09 1.92E+10 [6, 6, 10] [3, 3, 2] 0 40.922 23056 22 seed6 4 7.92E+09 1.92E+10 [5, 4, 5] [4, 4, 4] 0 110.953 23056 14 seed6 5 9.23E+09 1.92E+10 [4, 4, 4] [5, 4, 5] 0 237.844 23056 12 seed6 6 1.06E+10 1.92E+10 [3, 3, 4] [6, 6, 5] 0 270.085 23046 seed7 1 -1.96E+10 1.69E+10 [15, 20, 20] [1, 1, 1] 1 1.172 20255 55 seed7 2 -4.11E+09 1.73E+10 [10, 10, 10] [2, 2, 2] 0 11.578 20786 30 seed7 3 4.47E+09 1.71E+10 [5, 6, 6] [3, 3, 3] 0 44.907 20582 17 seed7 4 6.52E+09 1.60E+10 [4, 4, 4] [4, 4, 4] 0 123.547 19267 12 seed7 5 7.94E+09 1.54E+10 [3, 3, 3] [5, 5, 5] 0 275.75 18537 9 seed7 6 7.94E+09 1.54E+10 [3, 3, 3] [5, 5, 5] 0 299.318 18537 seed8 1 -1.46E+10 1.85E+10 [15, 15, 20] [1, 1, 1] 0 1.203 22286 50 seed8 2 -2.77E+09 1.85E+10 [10, 10, 10] [2, 2, 2] 0 11.625 22241 30 seed8 3 5.27E+09 1.78E+10 [5, 6, 6] [3, 3, 3] 1 46.296 21399 17 seed8 4 7.58E+09 1.82E+10 [4, 5, 5] [4, 3, 4] 0 126.765 21923 14 seed8 5 8.91E+09 1.62E+10 [3, 3, 3] [5, 4, 5] 0 281.672 19520 9 seed8 6 8.91E+09 1.62E+10 [3, 3, 3] [5, 4, 5] 0 307.259 19520 seed9 2 -4.64E+09 1.79E+10 [10, 12, 10] [2, 2, 2] 0 11.172 21563 32 seed9 3 2.50E+09 1.79E+10 [5, 10, 6] [3, 3, 3] 0 42.766 21532 21 seed9 4 6.73E+09 1.76E+10 [4, 5, 5] [4, 4, 4] 0 116.094 21170 14 seed9 5 8.36E+09 1.58E+10 [3, 3, 3] [5, 5, 5] 0 260.547 18972 9 seed9 6 8.36E+09 1.58E+10 [3, 3, 3] [5, 5, 5] 0 282.689 18972 seed10 1 -2.08E+10 1.81E+10 [20, 15, 20] [1, 1, 1] 1 1.078 21741 55 seed10 2 -3.96E+09 1.82E+10 [10, 10, 10] [2, 2, 2] 1 11.218 21927 30 seed10 3 4.27E+09 1.77E+10 [6, 5, 6] [3, 3, 3] 1 43.266 21210 17 seed10 4 7.53E+09 1.77E+10 [5, 3, 4] [4, 4, 4] 0 118.922 21329 12 seed10 5 8.39E+09 1.77E+10 [4, 3, 4] [5, 4, 4] 0 264.172 21329 11 seed10 6 9.36E+09 1.77E+10 [3, 3, 4] [6, 4, 4] 0 297.072 21329 Table C.12.: Results for 7 ×3-configuration at capacitated case. 129 Chapter C. Computational results deltaMax=6 profit revenue passengers nb iterations seed1 6.33E+09 1.57E+10 18918 1 seed2 5.75E+09 1.35E+10 16205 2 seed3 7.05E+09 1.42E+10 17086 2 seed4 7.54E+09 1.65E+10 19769 1 seed5 7.23E+09 1.46E+10 17525 1 seed6 8.15E+09 1.61E+10 19339 1 seed7 3.50E+09 1.09E+10 13075 2 seed10 8.50E+09 1.63E+10 19605 1 Table C.14.: Results for uncapacitated optimal solutions of 7 ×3-configuration with crowding and δmax = 6. 8×3-configuration Detailed information on the results for 8 ×3-configuration is reported in Tables C.15 and C.16. The results provided in this table reveal, for most cases, the system becomes productive from three carriages. As observed in 7 ×3-configuration, the frequencies are highs when the capacities are small, in order to transport all passenger willing to travel on the RTS. The average CPU time for δmax = 1 is 1.36 seconds whereas for δmax = 6 is 823. The optimal solutions for uncapacitated case are affected by the in-vehicle crowding at the capacitated case as show Tables C.17 and C.18. 130 Configuration 8 ×3, sigma 1.1, fare 6 instance δmax profit revenue ψℓδℓnoiterations CPU time nb trips nb Trains seed1 1 -8.74E+09 1.40E+10 [10, 15, 10] [1, 1, 1] 0 1.69 16788 25 seed1 2 1.64E+09 1.14E+10 [3, 6, 6] [2, 2, 2] 0 16.38 13735 15 seed1 3 3.89E+09 1.14E+10 [3, 4, 4] [2, 3, 3] 0 63.96 13734 11 seed1 4 5.01E+09 1.14E+10 [3, 3, 3] [2, 4, 4] 0 171.90 13724 9 seed1 5 5.01E+09 1.14E+10 [3, 3, 3] [2, 4, 4] 0 564.78 13724 9 seed1 6 5.01E+09 1.14E+10 [3, 3, 3] [2, 4, 4] 0 1011.83 13724 9 seed2 1 -7.65E+09 1.16E+10 [3, 15, 12] [1, 1, 1] 0 1.90 13936 30 seed2 2 -1.72E+09 1.16E+10 [3, 10, 6] [1, 2, 2] 0 17.82 13927 19 seed2 3 3.29E+09 1.16E+10 [3, 5, 3] [3, 3, 3] 0 66.50 13922 11 seed2 4 3.99E+09 1.16E+10 [3, 4, 3] [3, 4, 3] 0 173.29 13922 10 seed2 5 4.78E+09 1.16E+10 [3, 3, 3] [3, 5, 3] 0 570.36 13922 9 seed2 6 4.78E+09 1.16E+10 [3, 3, 3] [3, 5, 3] 0 1018.70 13922 9 seed3 1 -1.06E+10 1.64E+10 [15, 15, 20] [1, 1, 1] 0 1.25 19661 50 seed3 2 -1.91E+09 1.56E+10 [10, 10, 10] [2, 2, 2] 0 11.41 18758 30 seed3 3 6.04E+09 1.46E+10 [4, 5, 5] [3, 3, 3] 1 48.61 17553 14 seed3 4 6.96E+09 1.46E+10 [4, 4, 4] [3, 4, 4] 0 137.19 17552 12 seed3 5 7.99E+09 1.46E+10 [4, 3, 3] [3, 5, 5] 0 468.77 17521 10 seed3 6 7.99E+09 1.46E+10 [4, 3, 3] [3, 5, 5] 0 863.56 17521 10 seed4 1 -1.17E+10 1.79E+10 [20, 15, 20] [1, 1, 1] 0 1.08 21458 55 seed4 2 1.26E+09 1.36E+10 [5, 10, 4] [2, 2, 2] 0 12.97 16312 119 seed4 3 6.37E+09 1.67E+10 [6, 5, 6] [3, 3, 3] 0 42.84 20037 17 seed4 4 7.53E+09 1.58E+10 [5, 4, 4] [3, 4, 4] 0 125.29 18944 14 seed4 5 8.26E+09 1.48E+10 [4, 3, 3] [3, 5, 5] 0 439.73 17756 10 seed4 6 8.26E+09 1.48E+10 [4, 3, 3] [3, 5, 5] 0 820.11 17756 10 seed5 1 -8.35E+09 1.56E+10 [15, 15, 12] [1, 1, 1] 0 1.31 18688 42 seed5 2 -2.10E+08 1.73E+10 [10, 10, 10] [2, 2, 2] 0 10.77 20751 30 seed5 3 5.90E+09 1.31E+10 [3, 5, 3] [3, 3, 3] 0 54.10 15778 11 seed5 4 6.96E+09 1.27E+10 [3, 3, 3] [3, 4, 3] 0 151.52 15229 9 seed5 5 6.96E+09 1.27E+10 [3, 3, 3] [3, 4, 3] 0 513.94 15229 9 seed5 6 6.96E+09 1.27E+10 [3, 3, 3] [3, 4, 3] 0 946.48 15229 9 Table C.15.: Results for 8 ×3-configuration at capacitated case for seed1 to seed5- instances. 131 Chapter C. Computational results Configuration 8 ×3, sigma 1.1, fare 6 instance δmax profit revenue ψℓδℓnoiterations CPU time nb trips nb Trains seed6 1 -1.57E+10 1.56E+10 [15, 20, 15] [1, 1, 1] 0 1.171 18785 50 seed6 2 -2.80E+09 1.49E+10 [10, 10, 6] [2, 2, 2] 1 11.374 17850 26 seed6 3 4.66E+09 1.45E+10 [4, 6, 4] [3, 3, 3] 0 47.051 17459 14 seed6 4 5.91E+09 1.40E+10 [3, 5, 3] [3, 4, 4] 0 130.277 16798 11 seed6 5 6.56E+09 1.40E+10 [3, 4, 3] [3, 5, 4] 0 449.984 16795 10 seed6 6 7.25E+09 1.39E+10 [3, 3, 3] [3, 6, 4] 0 841.11 16749 9 seed7 1 -8.16E+09 1.28E+10 [4, 15, 15] [1, 1, 1] 0 1.919 15361 34 seed7 2 -1.29E+09 1.28E+10 [5, 10, 5] [2, 2, 2] 0 17.8 15333 20 seed7 3 4.01E+09 1.21E+10 [3, 5, 3] [3, 3, 3] 1 66.675 14514 11 seed7 4 5.32E+09 1.27E+10 [3, 4, 3] [2, 4, 4] 0 172.147 15258 10 seed7 5 6.05E+09 1.27E+10 [3, 3, 3] [2, 5, 4] 0 573.578 15257 9 seed7 6 6.05E+09 1.27E+10 [3, 3, 3] [2, 5, 4] 0 1045.719 15257 9 seed8 1 -1.34E+10 1.49E+10 [12, 15, 20] [1, 1, 1] 0 1.125 17940 47 seed8 2 -2.32E+09 1.48E+10 [6, 10, 10] [2, 2, 2] 0 11.311 17725 26 seed8 3 4.09E+09 1.44E+10 [5, 5, 5] [3, 3, 3] 0 47.457 17362 15 seed8 4 4.97E+09 1.42E+10 [5, 4, 4] [3, 4, 4] 0 133.303 17105 13 seed8 5 5.77E+09 1.31E+10 [4, 3, 3] [3, 5, 5] 0 466.813 15742 10 seed8 6 5.77E+09 1.31E+10 [4, 3, 3] [3, 5, 5] 0 862.828 15742 10 seed9 1 -1.29E+10 1.77E+10 [20, 20, 15] [1, 1, 1] 0 1.077 21248 55 seed9 2 -1.60E+08 1.71E+10 [10, 10, 10] [2, 2, 2] 0 10.75 20498 30 seed9 3 7.73E+09 1.68E+10 [5, 5, 5] [3, 3, 3] 0 42.355 20202 15 seed9 4 8.80E+09 1.60E+10 [4, 4, 3] [4, 4, 4] 0 120.277 19229 11 seed9 5 9.95E+09 1.59E+10 [3, 3, 3] [5, 5, 4] 0 430.297 19115 9 seed9 6 9.95E+09 1.59E+10 [3, 3, 3] [5, 5, 4] 0 815 19115 9 seed10 1 -1.77E+10 1.72E+10 [20, 20, 15] [1, 1, 1] 0 1.109 20612 55 seed10 2 -2.43E+09 1.71E+10 [10, 10, 10] [2, 2, 2] 0 10.921 20566 30 seed10 3 5.16E+09 1.58E+10 [5, 6, 4] [3, 3, 3] 0 43.197 19033 15 seed10 4 6.61E+09 1.48E+10 [4, 4, 3] [4, 4, 4] 0 124.801 17776 11 seed10 5 6.97E+09 1.45E+10 [3, 4, 3] [5, 4, 4] 0 438.688 17396 10 seed10 6 7.58E+09 1.45E+10 [3, 3, 3] [5, 6, 4] 0 866.312 17388 9 Table C.16.: Results for 8 ×3-configuration at capacitated case for seed6 to seed10- instances. deltaMax=5 profit revenue passengers nb iterations seed1(delta=4 also) 4.06E+09 1.04E+10 12497 1 seed8 5.17E+09 1.24E+10 14921 1 Table C.17.: Results for 8 ×3-configuration at capacitated case. 132 deltaMax=6 profit revenue passengers nb iterations seed1 4.06E+09 1.04E+10 12497 1 seed6 5.31E+09 1.19E+10 14317 1 seed8 5.17E+09 1.24E+10 14921 1 Table C.18.: Results for 8 ×3-configuration at capacitated case. 133 Chapter 4 An adaptive neighborhood search heuristic for metro network design 4.1. Introduction In this chapter we will focus on the network design and line planning taking into account aspects related to rolling stock and personnel costs. Concretely, we will analyze a particular case from the general model proposed in Chapter 2, which integrates the stages in the railway process above commented. The problem consists of maximizing the net profit of a RTS by selecting the location of stations and their connections, a set of lines, each characterized by two different terminal stations, a sequence of intermediate stations (an itinerary), frequencies of each line and the size of trains, assuming that all passengers willing to travel in the RTS can be transported. We assume the existence of an alternative transportation system (e.g. private car, bus, bicycle) competing with the RTS as well as passengers choose their routes and their transport mode according to traveling times. As mentioned in Chapter 2, the travel time is composed of several terms: waiting time, in vehicle time and transfer time. Each term is depending of the system’s characteristics such as the topology, the line configuration as well as the considered frequencies. The demand is supposed to be elastic and changes accordingly to the characteristics. This aspect is included in the model by means of a logit function. Moreover, we will concentrate on the effective resolution of this problem for small and medium instances. Due to the complexity of the problem that we are proposing, a heuristic procedure is needed to solve 135 Chapter 4. An adaptive neighborhood search heuristic for metro network design the problem for instances of large size. Specifically, we propose a new method based on the Adaptive Large Neighborhood Search Heuristic (ALNS) which provides a powerful algorithmic framework capable of simultaneously handling the network design, line planning, rolling stock and personnel planning. This algorithm is an iterative procedure that combines the network design problem and the line planning problem described in Chapter 3. Concretely, at each iteration it defines a possible infrastructure and line configuration, that is, a Rapid Transit Line (RTL), and the HLSA heuristic is applied on this network in order to evaluate the RTS built. Figure 4.1 shows a flow chart for this procedure. The main contributions of this chapter are the introduction of a mathematical programming programm to solve small instances of our problem as well as the development of a powerful ALNS heuristic to solve real instances. Input data ALNS RTL HLSA (Chapter 3) Net profit Figure 4.1.: Flow chart for the ALNS and the HLSA algorithms. The remainder of this chapter is organized as follows. In next section we will review the different techniques used for solving the rapid transit network design problem. In Section 4.2 we propose a mathematical programming program for the problem that integrates the rapid transit network design problem and line planing problem. Some techniques for improving the efficiency of our model are presented in Section 4.2.4. Our ALNS algorithm is presented in Section 4.3. Computational experiments are carried out on Section 4.4. The chapter ends with some conclusions. 4.1.1. Literature review on algorithms for RTND Last decades, mixed-integer models for the rapid transit network design (RTND) have been proposed. First studies are concentrated on the problem of designing a single rapid transit alignment. Gendreau et al. (1995) described the main criteria used to design rapid transit alignments, Dufourd et al. (1996) proposed a tabu search algorithm for solving this 136