# A New Approach to Shortest Route Finding in a Railway Network with Two Track Gauges and Gauge Changeovers

Authors: Alberto Almech; Eugenio Roanes-Lozano; Carmen Solano-Macías; Antonio Hernando
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

The Spanish railway network is a complex one, due to the existence ofstandard gauge (1,435 mm), Iberian gauge (1,668 mm), and dual gauge (with three rails) subnetworks, as well as connections between the two first subnetworks (at the so-called gauge changeovers), usable by dual gauge trains. Two of the authors developed a package for shortest route finding, and consumes, costs, and emissions calculations in the Spanish railway network (within the frame of two research projects funded by the Fundación de los Ferrocarriles Españoles–Spanish Railways Foundation). Nevertheless, the approach required from a curious specific algorithm to be developed ad hoc. In this paper, a much simpler approach to shortest route finding in such a network, which merges the three subnetworks into two and considers the gauge changeovers as connections between the two new subnetworks, is detailed. This approach allows to use any standard shortest route algorithm. It has been implemented in the computer algebra system Maple and is applied in this paper both to small specific cases and to the whole Spanish railway network.


---

## Body

## 1. Introduction

### 1.1. About the Previously Developed PackageRutasOptiRed and Its Algorithm

Shortest route finding in a railway network is a topic where two of the authors have worked for several years. In the frame of two research projects funded by theFundación de los Ferrocarriles Españoles (Spanish Railways Foundation), they developed from scratch in 2010 and 2011 a complex piece of software (denoted RutasOptiRed). The first version can find shortest routes and evaluate with high precision timings for the different pieces of rolling stock of Renfe Operadora (Spanish Railways operator) running on Adif (ADministrador de Infraestructuras Ferroviarias, that is, Spanish Railway Infrastructure Administrator) railway network [1]. The second version adds to this the possibility to detail the electric and Diesel consumes, CO2 emissions, and costs [2]. An example of application can be found in [3].In order to achieve a high precision,RutasOptiRed requires details of all parts of the sections in the railway network, as well as of all the different pieces of rolling stock, to be given as input (in order to obtain precise results). Each edge of the undirected weighted graph (note that as all the graphs considered hereinafter are undirected weighted graphs, so we shall refer to them as graphs for the sake of brevity) has a list of characteristics associated as follows: track gauge, maximum speed, etc.It even has an appropriate GUI that allows to comfortably introduce the data of each scenario (Figure1).Figure 1
Example of data introduction toRutasOptiRed: the user is asking to perform the computations corresponding to a Class 334 locomotive hauling 11 Talgo VI alloy coaches in the Badajoz–Madrid Chamartín route.Adif network includes two track gauges, some sections with three rails (dual gauge) and several gauge changeovers (what will be detailed in Section 1.3). Such a network required RutasOptiRed to use a curious specific algorithm to be developed ad hoc. It is a complex and unintuitive adaptation of Dijkstra’s algorithm:(i)
A different graph is built for each class of trains (!)(ii)
The track gauge the train is using at each moment is considered(iii)
The vertices represent the sections between stations, and the edges represent the possibility of that class of trains to pass from one section to the other (!), according to the track gauge it is using at that moment.This latter algorithm is convoluted and is detailed in a separate paper [4].


### 1.2. About the New Approach Introduced in This Article

In the present paper, a much simpler approach to shortest route finding in such a complex network is introduced:(i)
It merges the three subnetworks (standard gauge, Iberian gauge, and dual gauge) into two imaginary (in the sense that they do not correspond to any existing subnetwork) ones(ii)
It considers the gauge changeovers as connections between the two new subnetworksThe main advantage of this new approach is that vertices and edges are assigned the usual way. Consequently, any standard shortest route algorithm can be used.Based on the new approach, aMaple (Maple is a trademark of Waterloo Maple Inc.) package that allows to explore different alternatives in any railway network with two different track gauges and gauge changeovers has been developed.The work presented here is an improved and extended version of a work presented at CMMSE’2017 conference [5].


### 1.3. The Complex Spanish Railway Network: A Brief Overview

As said above,Adif is in charge of the Spanish railway network, meanwhile Renfe Operadora runs the passengers trains.The Spanish railway network is particularly complex [6], because it has tracks of two gauges: standard gauge (1,435 mm) and Iberian gauge (broad gauge: 1,668 mm) as well as dual gauge sections (Figure 2).Figure 2
The Spanish Iberian and standard gauge railway network (2018) (courtesy of theFundación de los Ferrocarriles Españoles (Spanish Railways Foundation)). The legend of the map is translated afterwards. First column: standard track gauge (1,435 mm); electrified double track; electrified single track. Second column: Iberian track gauge (1,668 mm); electrified double track; electrified single track; nonelectrified double track; nonelectrified single track. Third column: Dual track gauge sections (1,435–1,668 mm) (they are enumerated afterwards).Iberian gauge was the choice for the Spanish main network in the XIXth Century, but all the new high-speed lines since the first one (the 1992 Madrid–Seville) have been built in standard gauge. Note that some isolated sections of the high-speed network have been provisionally opened in Iberian gauge using dual gauge concrete sleepers (Ourense–Santiago section of the NW high-speed line) or are planned to be provisionally opened this way (sections within Extremadura region of the Madrid–Badajoz–Lisbon high-speed line) (see Figure 2).Dual gauge (also denoted mixed gauge) sections have three rails [7], one common rail on one side of the sleepers and two rails on the other side. Trains of the narrower gauge use the common rail and the closest rail. Trains of the wider gauge use the common rail and the furthest rail.In the beginning of 2019, the dual gauge sections are the Tardienta–Huesca section of the Canfranc line (South of the Central Pyrenees) and sections along the so-calledMediterranean corridor: a long section North of Valencia, a by-pass of Barcelona and some sections North of Barcelona, between this city and the French border (see Mapa 6 in [8]). More are planned or under work.Moreover, theIberian gauge and standard gauge subnetworks are not isolated. At some locations, there are gauge changeovers [9, 10] that connect both subnetworks (their present location can also be found in Mapa 6 in [8]).Note thatRenfe owns some classes of dual gauge locomotive hauled trains and multiple units [11]. Since 1969 till the beginning of the XXIst Century, locomotive hauled Talgo trains crossed the French border toward Paris and Geneva (Portugal has the same track gauge as Spain). This was no longer necessary when the Spanish standard gauge network reached the French border, and gauge changeovers are now situated within Spain.Nowadays, there are not only dual gauge coaches but only whole train sets, like theTalgo pushed-pulled classes 130 and 730 (the latter is hybrid and can work in both electric and Diesel modes) (Figure 3) and multiple units like CAF classes 120 and 121 (Figure 4).Figure 3
ATalgo Class 130 push-pull dual gauge bivoltage train of Renfe rolling stock. Class 730 is identical except that it incorporates an electrical power generator wagon immediately after each locomotive.Figure 4
ACAF Class 121 dual gauge bivoltage multiple unit of Renfe rolling stock.The narrow gauge network (1,000 mm) is nowadays run byAdif, after absorbing FEVE (Narrow Gauge Railway Company) on December 31, 2012. Nevertheless, the 1,000 mm network is not considered here, as it is isolated from the 1,435 mm and 1,668 mm networks, and there is no rolling stock that can run on narrow gauge tracks and also on tracks of any of the other two gauges.


### 1.4. Related Works

There are many issues regarding railway operation: planning, timetabling, scheduling, etc., (see, e.g., [12–14]) or line planning [15], just to mention a few, but they consider normal railway networks (that is, railway networks of a certain unique track gauge).The goal of our work is shortest route finding in a railway network with two track gauges. There are many works on shortest route finding applied to road traffic [16, 17], railway networks [18–21], transportation in general [22], and accessibility considering times [19], but we know of no similar work dealing with railway networks with two track gauges and gauge changeovers (except the already mentioned RutasOptiRed).


### 1.5. The Curious Madrid–Canfranc Counterexample

Let us analyze an example of what makes impossible to directly use a shortest route algorithm in a naive approach to the Spanish railway network (this problem arose when testing the first version ofRutasOptiRed).Let us consider the Madrid–Zaragoza–Tardienta–Huesca–Canfranc route ofAdif railway network.There are two railway connections between Madrid and Zaragoza: one is the classic Iberian gauge line and the other is part of the Madrid–Barcelona high-speed line (in NE Spain).Meanwhile, Zaragoza–Tardienta–Huesca–Canfranc is a branch line in Central Pyrenees (Figure2). Its Tardienta–Huesca section was chosen to test new technical solutions such as dual gauge (three rails) tracks and dual voltage catenary (commutable between 3,000 V DC and 25,000 V AC, according to the kind of train traversing the section). Note that classic lines are electrified at 3,000 V DC and and high-speed lines at 25,000 V AC.Summarizing, the situation of this peculiar route is the following:(i)
There are gauge changeovers at Madrid Chamartín and Madrid Atocha railway stations (the two main Madrid stations)(ii)
There are international gauge and Iberian gauge lines: Madrid–Zaragoza–Tardienta(iii)
There is a gauge changeover at Zaragoza Delicias station, but no one further toward Canfranc(iv)
The Tardienta–Huesca is a dual gauge section(v)
The Huesca–Canfranc section is an Iberian gauge oneThis route and its characteristics are represented in a simplified way in Figure5.Figure 5
Between Madrid and Zaragoza and between Zaragoza and Tardienta, there is a high-speed line of standard gauge (thick line) and an Iberian gauge line (dashed line). There are gauge changeovers at Madrid and Zaragoza (stars). Between Tardienta and Huesca, there is a dual gauge section (thin line). Between Tardienta and Huesca, there is only an Iberian gauge line (dashed line).In this case, if we ask for the shortest route between Madrid and Canfranc, a standard shortest route algorithm will try to reach the intermediate stations (Zaragoza and Tardienta) as fast as possible. For a variable gauge train, we would obtain the following routes:(i)
Madrid–Zaragoza: train set to standard gauge, along the high-speed line(ii)
Zaragoza–Tardienta: train set to standard gauge, along the high-speed line(iii)
Tardienta–Huesca: train set to standard gauge, along the dual gauge sectionBut then, the train would reach Huesca set as a standard gauge train, and there is no gauge changeover at Huesca, so the train could not go on (the rest of the route is an Iberian gauge section)!Then, the surprising solution given by a standard shortest route algorithm would be to return to the (far away) gauge changeover at Zaragoza and to return back to Huesca on Iberian gauge!Summarizing, the existence of a dual gauge section (with three rails)(i)
that is not at any of the ends of the route(ii)
that has not got gauge changeovers at their endpointsmakes impossible to use a classic shortest route algorithm such as Dijkstra’s [23] and Floyd’s [24] (that is, algorithms that consider that the piece of rolling stock can move from any section of the network or subnetwork to another, without taking into account how the gauge of a variable gauge train is set).


## 1.1. About the Previously Developed PackageRutasOptiRed and Its Algorithm

Shortest route finding in a railway network is a topic where two of the authors have worked for several years. In the frame of two research projects funded by theFundación de los Ferrocarriles Españoles (Spanish Railways Foundation), they developed from scratch in 2010 and 2011 a complex piece of software (denoted RutasOptiRed). The first version can find shortest routes and evaluate with high precision timings for the different pieces of rolling stock of Renfe Operadora (Spanish Railways operator) running on Adif (ADministrador de Infraestructuras Ferroviarias, that is, Spanish Railway Infrastructure Administrator) railway network [1]. The second version adds to this the possibility to detail the electric and Diesel consumes, CO2 emissions, and costs [2]. An example of application can be found in [3].In order to achieve a high precision,RutasOptiRed requires details of all parts of the sections in the railway network, as well as of all the different pieces of rolling stock, to be given as input (in order to obtain precise results). Each edge of the undirected weighted graph (note that as all the graphs considered hereinafter are undirected weighted graphs, so we shall refer to them as graphs for the sake of brevity) has a list of characteristics associated as follows: track gauge, maximum speed, etc.It even has an appropriate GUI that allows to comfortably introduce the data of each scenario (Figure1).Figure 1
Example of data introduction toRutasOptiRed: the user is asking to perform the computations corresponding to a Class 334 locomotive hauling 11 Talgo VI alloy coaches in the Badajoz–Madrid Chamartín route.Adif network includes two track gauges, some sections with three rails (dual gauge) and several gauge changeovers (what will be detailed in Section 1.3). Such a network required RutasOptiRed to use a curious specific algorithm to be developed ad hoc. It is a complex and unintuitive adaptation of Dijkstra’s algorithm:(i)
A different graph is built for each class of trains (!)(ii)
The track gauge the train is using at each moment is considered(iii)
The vertices represent the sections between stations, and the edges represent the possibility of that class of trains to pass from one section to the other (!), according to the track gauge it is using at that moment.This latter algorithm is convoluted and is detailed in a separate paper [4].


## 1.2. About the New Approach Introduced in This Article

In the present paper, a much simpler approach to shortest route finding in such a complex network is introduced:(i)
It merges the three subnetworks (standard gauge, Iberian gauge, and dual gauge) into two imaginary (in the sense that they do not correspond to any existing subnetwork) ones(ii)
It considers the gauge changeovers as connections between the two new subnetworksThe main advantage of this new approach is that vertices and edges are assigned the usual way. Consequently, any standard shortest route algorithm can be used.Based on the new approach, aMaple (Maple is a trademark of Waterloo Maple Inc.) package that allows to explore different alternatives in any railway network with two different track gauges and gauge changeovers has been developed.The work presented here is an improved and extended version of a work presented at CMMSE’2017 conference [5].


## 1.3. The Complex Spanish Railway Network: A Brief Overview

As said above,Adif is in charge of the Spanish railway network, meanwhile Renfe Operadora runs the passengers trains.The Spanish railway network is particularly complex [6], because it has tracks of two gauges: standard gauge (1,435 mm) and Iberian gauge (broad gauge: 1,668 mm) as well as dual gauge sections (Figure 2).Figure 2
The Spanish Iberian and standard gauge railway network (2018) (courtesy of theFundación de los Ferrocarriles Españoles (Spanish Railways Foundation)). The legend of the map is translated afterwards. First column: standard track gauge (1,435 mm); electrified double track; electrified single track. Second column: Iberian track gauge (1,668 mm); electrified double track; electrified single track; nonelectrified double track; nonelectrified single track. Third column: Dual track gauge sections (1,435–1,668 mm) (they are enumerated afterwards).Iberian gauge was the choice for the Spanish main network in the XIXth Century, but all the new high-speed lines since the first one (the 1992 Madrid–Seville) have been built in standard gauge. Note that some isolated sections of the high-speed network have been provisionally opened in Iberian gauge using dual gauge concrete sleepers (Ourense–Santiago section of the NW high-speed line) or are planned to be provisionally opened this way (sections within Extremadura region of the Madrid–Badajoz–Lisbon high-speed line) (see Figure 2).Dual gauge (also denoted mixed gauge) sections have three rails [7], one common rail on one side of the sleepers and two rails on the other side. Trains of the narrower gauge use the common rail and the closest rail. Trains of the wider gauge use the common rail and the furthest rail.In the beginning of 2019, the dual gauge sections are the Tardienta–Huesca section of the Canfranc line (South of the Central Pyrenees) and sections along the so-calledMediterranean corridor: a long section North of Valencia, a by-pass of Barcelona and some sections North of Barcelona, between this city and the French border (see Mapa 6 in [8]). More are planned or under work.Moreover, theIberian gauge and standard gauge subnetworks are not isolated. At some locations, there are gauge changeovers [9, 10] that connect both subnetworks (their present location can also be found in Mapa 6 in [8]).Note thatRenfe owns some classes of dual gauge locomotive hauled trains and multiple units [11]. Since 1969 till the beginning of the XXIst Century, locomotive hauled Talgo trains crossed the French border toward Paris and Geneva (Portugal has the same track gauge as Spain). This was no longer necessary when the Spanish standard gauge network reached the French border, and gauge changeovers are now situated within Spain.Nowadays, there are not only dual gauge coaches but only whole train sets, like theTalgo pushed-pulled classes 130 and 730 (the latter is hybrid and can work in both electric and Diesel modes) (Figure 3) and multiple units like CAF classes 120 and 121 (Figure 4).Figure 3
ATalgo Class 130 push-pull dual gauge bivoltage train of Renfe rolling stock. Class 730 is identical except that it incorporates an electrical power generator wagon immediately after each locomotive.Figure 4
ACAF Class 121 dual gauge bivoltage multiple unit of Renfe rolling stock.The narrow gauge network (1,000 mm) is nowadays run byAdif, after absorbing FEVE (Narrow Gauge Railway Company) on December 31, 2012. Nevertheless, the 1,000 mm network is not considered here, as it is isolated from the 1,435 mm and 1,668 mm networks, and there is no rolling stock that can run on narrow gauge tracks and also on tracks of any of the other two gauges.


## 1.4. Related Works

There are many issues regarding railway operation: planning, timetabling, scheduling, etc., (see, e.g., [12–14]) or line planning [15], just to mention a few, but they consider normal railway networks (that is, railway networks of a certain unique track gauge).The goal of our work is shortest route finding in a railway network with two track gauges. There are many works on shortest route finding applied to road traffic [16, 17], railway networks [18–21], transportation in general [22], and accessibility considering times [19], but we know of no similar work dealing with railway networks with two track gauges and gauge changeovers (except the already mentioned RutasOptiRed).


## 1.5. The Curious Madrid–Canfranc Counterexample

Let us analyze an example of what makes impossible to directly use a shortest route algorithm in a naive approach to the Spanish railway network (this problem arose when testing the first version ofRutasOptiRed).Let us consider the Madrid–Zaragoza–Tardienta–Huesca–Canfranc route ofAdif railway network.There are two railway connections between Madrid and Zaragoza: one is the classic Iberian gauge line and the other is part of the Madrid–Barcelona high-speed line (in NE Spain).Meanwhile, Zaragoza–Tardienta–Huesca–Canfranc is a branch line in Central Pyrenees (Figure2). Its Tardienta–Huesca section was chosen to test new technical solutions such as dual gauge (three rails) tracks and dual voltage catenary (commutable between 3,000 V DC and 25,000 V AC, according to the kind of train traversing the section). Note that classic lines are electrified at 3,000 V DC and and high-speed lines at 25,000 V AC.Summarizing, the situation of this peculiar route is the following:(i)
There are gauge changeovers at Madrid Chamartín and Madrid Atocha railway stations (the two main Madrid stations)(ii)
There are international gauge and Iberian gauge lines: Madrid–Zaragoza–Tardienta(iii)
There is a gauge changeover at Zaragoza Delicias station, but no one further toward Canfranc(iv)
The Tardienta–Huesca is a dual gauge section(v)
The Huesca–Canfranc section is an Iberian gauge oneThis route and its characteristics are represented in a simplified way in Figure5.Figure 5
Between Madrid and Zaragoza and between Zaragoza and Tardienta, there is a high-speed line of standard gauge (thick line) and an Iberian gauge line (dashed line). There are gauge changeovers at Madrid and Zaragoza (stars). Between Tardienta and Huesca, there is a dual gauge section (thin line). Between Tardienta and Huesca, there is only an Iberian gauge line (dashed line).In this case, if we ask for the shortest route between Madrid and Canfranc, a standard shortest route algorithm will try to reach the intermediate stations (Zaragoza and Tardienta) as fast as possible. For a variable gauge train, we would obtain the following routes:(i)
Madrid–Zaragoza: train set to standard gauge, along the high-speed line(ii)
Zaragoza–Tardienta: train set to standard gauge, along the high-speed line(iii)
Tardienta–Huesca: train set to standard gauge, along the dual gauge sectionBut then, the train would reach Huesca set as a standard gauge train, and there is no gauge changeover at Huesca, so the train could not go on (the rest of the route is an Iberian gauge section)!Then, the surprising solution given by a standard shortest route algorithm would be to return to the (far away) gauge changeover at Zaragoza and to return back to Huesca on Iberian gauge!Summarizing, the existence of a dual gauge section (with three rails)(i)
that is not at any of the ends of the route(ii)
that has not got gauge changeovers at their endpointsmakes impossible to use a classic shortest route algorithm such as Dijkstra’s [23] and Floyd’s [24] (that is, algorithms that consider that the piece of rolling stock can move from any section of the network or subnetwork to another, without taking into account how the gauge of a variable gauge train is set).


## 2. The New Approach: Key Idea

As the problem is shortest route finding in a dual gauge railway network, we consider that the trains can run along tracks of both gauges and can pass through gauge changeovers (in order to take advantage of possibilities of the whole railway network). If only Iberian gauge or standard gauge trains were to be considered, it would be enough to prune the graph accordingly.The key idea in the new approach presented here is to make up a fictitious new graph (from the three initial subnetworks of standard/Iberian/dual gauge) that incorporates all the track gauge information, but without associating track gauge details to its edges.From a more visual point of view, the part of the railway infrastructure that can be traversed by trains of each of the two track gauges occupies a level or layer in the form of a subgraph (note that these two graphs do not correspond to any existing subnetwork). These levels are connected to each other (at certain vertices) by means of (artificially added) edges that correspond to the gauge changeovers.Introducing these two layers will require to consider two vertices for each station that can be reached by trains of the two different track gauges (as will be detailed in Section2.1).This way any standard shortest route algorithm (such as Dijkstra’s [23] and Floyd’s [24]) can be used.Let us detail the new approach afterwards.


### 2.1. The New Approach: Notation and Initial (Given) Graphs

LetH be a graph. We shall denote by VH the set of vertices of H and by EH the set of edges of H.LetS be the set of stations of the railway network. The names of these stations should not have subscripts.As expected, three graphs are initially considered (and must be given as input). As usual, but unlikeRutasOptiRed [1, 2, 4], the vertices of the graphs represent the stations and the edges of the graphs correspond to the sections of the railway network. These graphs are as follows:(i)
Gi=Vi,Ei: graph corresponding to the Iberian gauge railway network(ii)
Gs=Vs,Es: graph corresponding to the standard gauge railway network(iii)
Gd=Vd,Ed: graph corresponding to the dual gauge railway networkHere,Vzz∈i,s,d are the sets of vertices (stations) and Ezz∈i,s,d are the sets of edges (sections of railway line) of the Iberian/standard/dual gauge railway networks (respectively). The weight associated to each edge is the corresponding timing (introduced directly or through length and average speed).


### 2.2. The New Approach: Making up a Fictitious New Graph,G∗, Containing all the Information

Let us begin with the initial graphsGi, Gs, and Gd described in Section 2.1.The process to be carried out in order to build the new graph,G∗, can be summarized as follows:(i)
If a station can be reached by trains of the two track gauges (either along normal tracks or dual gauge tracks), it will be described by two different vertices.For instance, Zaragoza main station (Estación de Zaragoza Delicias) has tracks of both track gauges, and we shall consider two vertices: Zaragozai and Zaragozas (standing for Zaragoza Iberian gauge and Zaragoza standard gauge, respectively), even if there is only one real station.More formally, let us denote(1)B=VGi∩VGs∪VGd.For all verticesv∈B, two vertices, vi and vs, will be considered instead of the original v.(ii)
Let us denote(2)Bi=viv∈B;Bs=vsv∈B.(iii)
Let us name byCi⊆Bi and Cs⊆Bs the sets of stations where a gauge changeover is installed.ObviouslyCi and Cs consist of the same names with different subscripts, that is,(3)stationi∈Ci⟺stations∈Cs.as gauge changeovers connect the standard gauge and Iberian gauge tracks of the same station.(iv)
Let us represent by(4)GzSy,z∈i,s,d,y∈i,s.the graph obtained by exchanging in the initial graphGz=Vz,Ez the name of all vertices, v, such that vy∈By, by vy.This way four new graphs are obtained:(a)
GiSi, corresponding to the Iberian gauge subnetwork, with some vertices with an added subscript “i,”(b)
GdSi, corresponding to the dual gauge subnetwork, with some vertices with an added subscript “i,”(c)
GsSs, corresponding to the standard gauge subnetwork, with some vertices with an added subscript “s,”(d)
GdSs, corresponding to the dual gauge subnetwork, with some vertices with an added subscript “s.”(v)
Now two new graphs can be constructed, corresponding to the accessibility in each track gauge, respectively:(5)Gi∗=GiSi∪GdSi,Gs∗=GsSs∪GdSs.Note thatGi∗ and Gs∗ correspond to the sections of the network that can be traversed by an Iberian gauge train/standard gauge train, respectively. Let us recall that the names of stations with tracks of both track gauges, like Zaragoza, have been substituted by the names with i and s subscripts, like Zaragozai and Zaragozas, accordingly.(vi)
Finally, the two previous graphs are merged in a single graph,G∗ (Figure 6), and the connectivity between them is introduced by giving the gauge changeover positions (the edges corresponding to the gauge changeovers are of the form Zaragozai,Zaragozas). More formally,(6)G∗=V∗,E∗,where(7)V∗=VGi∗∪VGs∗,E∗=EGi∗∪EGs∗∪vi,vsvi∈Ci∧vs∈Cs.Figure 6
A 3D representation of graphG∗ capturing the global accessibility of a certain railway network with two gauges. The two planes (layers) represented are z=0 (lower) and z=1 (upper). The z-axis is, as usual, the vertical axis. Graph Gi∗ is represented in the upper plane, and its edges are drawn in blue. Graph Gs∗ is represented in the lower plane, and its edges are drawn in red. Therefore, the stations with Iberian gauge tracks are in the upper plane (z=1) and their names have an “i” subscript or no subscript at all. Meanwhile, all the stations with standard gauge tracks are in the lower plane (z=0) and their names have an “s” subscript or no subscript at all. The x and y coordinates of the stations of the forms vi and vs (like Zaragozai and Zaragozas) are identical. The vertical connections (in green) between the two horizontal planes represent the location of the gauge changeovers (that only sometimes exist in stations with tracks of both track gauges).


### 2.3. The New Approach: Remark

The goal is to compute the shortest possible route for a given piece of rolling stock. Therefore, it will be supposed that an appropriate class of trains will be chosen by the end user (either standard gauge train, Iberian gauge train or dual gauge train). For instance, it is impossible to reach Cáceres with a class 103 train because this is a standard gauge train and this station is only in the Iberian gauge network.Moreover, the piece of rolling stock chosen should be able to take advantage of the maximum speeds of the different sections of the route in order to obtain correct results.Observe that the goal of the new piece of software described in this paper is only one of the goals ofRutasOptiRed, but the main one. The new approach that merges the dual gauge subnetwork with the Iberian and standard gauge networks allows to use a much simpler coding and algorithm.


### 2.4. The New Approach: Advantages

In the new approach, only either the real or theoretical average speed and length or the scheduled timing have to be assigned to each edge ofG∗. As the edges correspond to sections of railway line or to gauge changeovers, origin to destination timings can be easily computed (just adding the timings of the sections along the route).In the example described in Section1.5 (Madrid–Canfranc line), the new approach proposed in this paper would consider the graph of Figure 7. It is clear that the error mentioned in Section 1.5 cannot arise, and the route chosen would be the following:(i)
Madrid–Zaragoza (train set to standard gauge, along the high-speed line, because the speed is higher than in the Iberian gauge line)(ii)
Gauge change at Zaragoza(iii)
Zaragoza–Tardienta (train set to Iberian gauge, along the Iberian gauge line)(iv)
Tardienta–Huesca (train set to Iberian gauge, along the dual gauge section)(v)
Huesca–Canfranc (train set to Iberian gauge, along the Iberian gauge line)Figure 7
3D representation in the new approach of the graphG∗ corresponding to the Madrid–Canfranc routes. The five stations in the upper layer have Iberian gauge tracks. All except Canfranc have standard gauge tracks too (so they appear in the lower layer too). There are vertical connections at Madrid and Zaragoza because there are gauge changeovers installed at these stations.Because when at Zaragozas, the only way to go on to Canfranc is to move to the upper layer, which can be reached at Zaragoza through the gauge changeover.


### 2.5. The New Approach: A Final Remark

Let us observe that the origin (respectively, destination) of the route can be stations with tracks of the two track gauges (such as Madrid in Figure7). In such case, the end user should choose the track gauge the train is set to when departing (respectively, arriving).In case a wrong track gauge choice was made by the end user at an origin or destination station with gauge changeovers, the package would ask for passing through the gauge changeover there first, what is trivial to correct.


## 2.1. The New Approach: Notation and Initial (Given) Graphs

LetH be a graph. We shall denote by VH the set of vertices of H and by EH the set of edges of H.LetS be the set of stations of the railway network. The names of these stations should not have subscripts.As expected, three graphs are initially considered (and must be given as input). As usual, but unlikeRutasOptiRed [1, 2, 4], the vertices of the graphs represent the stations and the edges of the graphs correspond to the sections of the railway network. These graphs are as follows:(i)
Gi=Vi,Ei: graph corresponding to the Iberian gauge railway network(ii)
Gs=Vs,Es: graph corresponding to the standard gauge railway network(iii)
Gd=Vd,Ed: graph corresponding to the dual gauge railway networkHere,Vzz∈i,s,d are the sets of vertices (stations) and Ezz∈i,s,d are the sets of edges (sections of railway line) of the Iberian/standard/dual gauge railway networks (respectively). The weight associated to each edge is the corresponding timing (introduced directly or through length and average speed).


## 2.2. The New Approach: Making up a Fictitious New Graph,G∗, Containing all the Information

Let us begin with the initial graphsGi, Gs, and Gd described in Section 2.1.The process to be carried out in order to build the new graph,G∗, can be summarized as follows:(i)
If a station can be reached by trains of the two track gauges (either along normal tracks or dual gauge tracks), it will be described by two different vertices.For instance, Zaragoza main station (Estación de Zaragoza Delicias) has tracks of both track gauges, and we shall consider two vertices: Zaragozai and Zaragozas (standing for Zaragoza Iberian gauge and Zaragoza standard gauge, respectively), even if there is only one real station.More formally, let us denote(1)B=VGi∩VGs∪VGd.For all verticesv∈B, two vertices, vi and vs, will be considered instead of the original v.(ii)
Let us denote(2)Bi=viv∈B;Bs=vsv∈B.(iii)
Let us name byCi⊆Bi and Cs⊆Bs the sets of stations where a gauge changeover is installed.ObviouslyCi and Cs consist of the same names with different subscripts, that is,(3)stationi∈Ci⟺stations∈Cs.as gauge changeovers connect the standard gauge and Iberian gauge tracks of the same station.(iv)
Let us represent by(4)GzSy,z∈i,s,d,y∈i,s.the graph obtained by exchanging in the initial graphGz=Vz,Ez the name of all vertices, v, such that vy∈By, by vy.This way four new graphs are obtained:(a)
GiSi, corresponding to the Iberian gauge subnetwork, with some vertices with an added subscript “i,”(b)
GdSi, corresponding to the dual gauge subnetwork, with some vertices with an added subscript “i,”(c)
GsSs, corresponding to the standard gauge subnetwork, with some vertices with an added subscript “s,”(d)
GdSs, corresponding to the dual gauge subnetwork, with some vertices with an added subscript “s.”(v)
Now two new graphs can be constructed, corresponding to the accessibility in each track gauge, respectively:(5)Gi∗=GiSi∪GdSi,Gs∗=GsSs∪GdSs.Note thatGi∗ and Gs∗ correspond to the sections of the network that can be traversed by an Iberian gauge train/standard gauge train, respectively. Let us recall that the names of stations with tracks of both track gauges, like Zaragoza, have been substituted by the names with i and s subscripts, like Zaragozai and Zaragozas, accordingly.(vi)
Finally, the two previous graphs are merged in a single graph,G∗ (Figure 6), and the connectivity between them is introduced by giving the gauge changeover positions (the edges corresponding to the gauge changeovers are of the form Zaragozai,Zaragozas). More formally,(6)G∗=V∗,E∗,where(7)V∗=VGi∗∪VGs∗,E∗=EGi∗∪EGs∗∪vi,vsvi∈Ci∧vs∈Cs.Figure 6
A 3D representation of graphG∗ capturing the global accessibility of a certain railway network with two gauges. The two planes (layers) represented are z=0 (lower) and z=1 (upper). The z-axis is, as usual, the vertical axis. Graph Gi∗ is represented in the upper plane, and its edges are drawn in blue. Graph Gs∗ is represented in the lower plane, and its edges are drawn in red. Therefore, the stations with Iberian gauge tracks are in the upper plane (z=1) and their names have an “i” subscript or no subscript at all. Meanwhile, all the stations with standard gauge tracks are in the lower plane (z=0) and their names have an “s” subscript or no subscript at all. The x and y coordinates of the stations of the forms vi and vs (like Zaragozai and Zaragozas) are identical. The vertical connections (in green) between the two horizontal planes represent the location of the gauge changeovers (that only sometimes exist in stations with tracks of both track gauges).


## 2.3. The New Approach: Remark

The goal is to compute the shortest possible route for a given piece of rolling stock. Therefore, it will be supposed that an appropriate class of trains will be chosen by the end user (either standard gauge train, Iberian gauge train or dual gauge train). For instance, it is impossible to reach Cáceres with a class 103 train because this is a standard gauge train and this station is only in the Iberian gauge network.Moreover, the piece of rolling stock chosen should be able to take advantage of the maximum speeds of the different sections of the route in order to obtain correct results.Observe that the goal of the new piece of software described in this paper is only one of the goals ofRutasOptiRed, but the main one. The new approach that merges the dual gauge subnetwork with the Iberian and standard gauge networks allows to use a much simpler coding and algorithm.


## 2.4. The New Approach: Advantages

In the new approach, only either the real or theoretical average speed and length or the scheduled timing have to be assigned to each edge ofG∗. As the edges correspond to sections of railway line or to gauge changeovers, origin to destination timings can be easily computed (just adding the timings of the sections along the route).In the example described in Section1.5 (Madrid–Canfranc line), the new approach proposed in this paper would consider the graph of Figure 7. It is clear that the error mentioned in Section 1.5 cannot arise, and the route chosen would be the following:(i)
Madrid–Zaragoza (train set to standard gauge, along the high-speed line, because the speed is higher than in the Iberian gauge line)(ii)
Gauge change at Zaragoza(iii)
Zaragoza–Tardienta (train set to Iberian gauge, along the Iberian gauge line)(iv)
Tardienta–Huesca (train set to Iberian gauge, along the dual gauge section)(v)
Huesca–Canfranc (train set to Iberian gauge, along the Iberian gauge line)Figure 7
3D representation in the new approach of the graphG∗ corresponding to the Madrid–Canfranc routes. The five stations in the upper layer have Iberian gauge tracks. All except Canfranc have standard gauge tracks too (so they appear in the lower layer too). There are vertical connections at Madrid and Zaragoza because there are gauge changeovers installed at these stations.Because when at Zaragozas, the only way to go on to Canfranc is to move to the upper layer, which can be reached at Zaragoza through the gauge changeover.


## 2.5. The New Approach: A Final Remark

Let us observe that the origin (respectively, destination) of the route can be stations with tracks of the two track gauges (such as Madrid in Figure7). In such case, the end user should choose the track gauge the train is set to when departing (respectively, arriving).In case a wrong track gauge choice was made by the end user at an origin or destination station with gauge changeovers, the package would ask for passing through the gauge changeover there first, what is trivial to correct.


## 3. Implementation

The new package is implemented inMaple, using its GraphTheory package. This way the implementation is brief, only a few pages long. Details are avoided for the sake of space. The code is available from the authors.Dijkstra’s algorithm is used because it is the one offered byMaple for this purpose. Nevertheless, this is just an example. The new approach presented in this article can be implemented using any shortest route algorithm in any appropriate software.


### 3.1. Data Introduction 2D and 3D Graph Plotting

Let us detail the steps of the data introduction to the present implementation and its possibilities.Step 1: firstly,Maple’s GraphTheory and plots packages must be loaded:with(GraphTheory):with(plots):Step 2: in order to produce an approximate plot, the package begins by defining a bidimensional array of possible locations for the stations, that is, the vertices ofGi, Gs, and Gd. So, the second step consists in declaring the number of rows and columns of nodes in the rectangular lattice where the stations have to be allocated (they will have to be manually allocated, when introducing the edges of the railway networks, in positions that approximately correspond to their geographical coordinates). For example,rows:=8:columns:=12:Step 3: afterwards, the code of the package presented here can be loaded:read(`RouteDual04.mpl`):Step 4: the sections of each of the three railway networks (edges of the graphs) have to be given through their end points, lengths and average speeds of the different sections. The package obtains the times per section (for each track gauge) from the distances and speeds. For instance,introdata(nodo(3, 3),"Los Rosales", nodo(4, 3),"Lora", 20, 160):introduces an Iberian gauge section.Meanwhile,t:=nodes:introdata(t+nodo(6, 5),"C. Real_s", t+nodo(5, 5),"Puertollano_s", 39, 270):introduces a standard gauge sectionThe dual gauge sections require a slightly more complex data introduction as their vertices have to define two virtual stations (one for each gauge). An example of introduction of the data of a section isd:=2∗nodes:introdata(d+nodo(12, 13),"Huesca", d+nodo(12, 12),"Tardienta", 22, 160):stations[nodo(12, 13)]:="Huesca_i":stations[nodes+nodo(12, 13)]:="Huesca_s":stations[nodo(12, 12)]:="Tardienta_i":stations[nodes+nodo(12, 12)]:="Tardienta_s":These sets of commands should be followed by a finalgenerate_A(i);generate_timings_A(i);wherei=0,1,2 correspond to the Iberian, standard and dual gauge networks.Step 5: the graphs of the different track gauges showing times and speeds can be plotted immediately after generating the corresponding A(i) by typing:display(A);(In Figure8, note that the speeds have been obtained from the Mapa 8 of the Anexo H of the official document [25], but these are very optimistic if taken as average speeds, because they do not consider partial speed limitations along the section. Anyway, we shall consider them as illustration.)Step 6: it is possible to erase the unused vertices in the timings graphs (thanks to an appropriate procedure developed ad hoc). The pruned graph can be obtained by typingdisplay(AT);instead (in Figure9 the timings of the Iberian gauge subnetwork in SW Spain) are shown).Step 7: then, the timing to pass a gauge changeover and their locations in the lattice have to be introduced. For example,gauge_changeovers(10,{15, 17, 41, 70, 84, 90});Step 8: the real names of the nodes (stations) of the two layers can be shown instead of the numbers of the nodes (if desired), in order the end user to comfortably manipulate the package. It is enough to type:names(0):Step 9: a 2D representation of the whole network, where the three initial graphs have been merged into two,Gi∗, Gs∗, as explained above, that also shows the gauge changeovers can be obtained by typing (see Figure 10):display(IT);Step 10: finally, a 3D representation of the whole network (in two levels) can be obtained by typing (see Figure11):nice_3D();TwoLevels3DPlot;Observe that how to represent a certain route can be found inSection 4.


### 3.2. Obtaining the Best Route and Timing

The analysis of the Madrid––Seville route is included as illustration (here, we suppose that the input data of the network have already been introduced). If, for example, the end user types:Route_M_S:=bestRoute(H,"Madrid At_s","Sevilla_s"):the following output is obtained:[["Madrid At_s", "C. Real_s", "Puertollano_s", "Cordoba_s", "Sevilla_s"], 122]that is, the best route and the corresponding timing (in minutes) have been stored in variable Route_M_S. The best route is a list of stations. They can be shown by typing:Route_M_S[1];["Madrid At_s", "C. Real_s", "Puertollano_s", "Cordoba_s", "Sevilla_s"]Route_M_S[2];122Let us underline that the best timing (a Madrid–Seville nonstop) is nowadays 2 h 20m = 140 m. The approximation is not bad, as(i)
It has to be taken into account that high-speed trains in Spain are scheduled with a margin of a few minutes (due to a strict money back policy if there are small delays)(ii)
The first kilometers in the neighborhood of the origin and destination stations are traversed at limited speed(iii)
Not all intermediate stations are passed at full speed (details that are not considered by the package).


## 3.1. Data Introduction 2D and 3D Graph Plotting

Let us detail the steps of the data introduction to the present implementation and its possibilities.Step 1: firstly,Maple’s GraphTheory and plots packages must be loaded:with(GraphTheory):with(plots):Step 2: in order to produce an approximate plot, the package begins by defining a bidimensional array of possible locations for the stations, that is, the vertices ofGi, Gs, and Gd. So, the second step consists in declaring the number of rows and columns of nodes in the rectangular lattice where the stations have to be allocated (they will have to be manually allocated, when introducing the edges of the railway networks, in positions that approximately correspond to their geographical coordinates). For example,rows:=8:columns:=12:Step 3: afterwards, the code of the package presented here can be loaded:read(`RouteDual04.mpl`):Step 4: the sections of each of the three railway networks (edges of the graphs) have to be given through their end points, lengths and average speeds of the different sections. The package obtains the times per section (for each track gauge) from the distances and speeds. For instance,introdata(nodo(3, 3),"Los Rosales", nodo(4, 3),"Lora", 20, 160):introduces an Iberian gauge section.Meanwhile,t:=nodes:introdata(t+nodo(6, 5),"C. Real_s", t+nodo(5, 5),"Puertollano_s", 39, 270):introduces a standard gauge sectionThe dual gauge sections require a slightly more complex data introduction as their vertices have to define two virtual stations (one for each gauge). An example of introduction of the data of a section isd:=2∗nodes:introdata(d+nodo(12, 13),"Huesca", d+nodo(12, 12),"Tardienta", 22, 160):stations[nodo(12, 13)]:="Huesca_i":stations[nodes+nodo(12, 13)]:="Huesca_s":stations[nodo(12, 12)]:="Tardienta_i":stations[nodes+nodo(12, 12)]:="Tardienta_s":These sets of commands should be followed by a finalgenerate_A(i);generate_timings_A(i);wherei=0,1,2 correspond to the Iberian, standard and dual gauge networks.Step 5: the graphs of the different track gauges showing times and speeds can be plotted immediately after generating the corresponding A(i) by typing:display(A);(In Figure8, note that the speeds have been obtained from the Mapa 8 of the Anexo H of the official document [25], but these are very optimistic if taken as average speeds, because they do not consider partial speed limitations along the section. Anyway, we shall consider them as illustration.)Step 6: it is possible to erase the unused vertices in the timings graphs (thanks to an appropriate procedure developed ad hoc). The pruned graph can be obtained by typingdisplay(AT);instead (in Figure9 the timings of the Iberian gauge subnetwork in SW Spain) are shown).Step 7: then, the timing to pass a gauge changeover and their locations in the lattice have to be introduced. For example,gauge_changeovers(10,{15, 17, 41, 70, 84, 90});Step 8: the real names of the nodes (stations) of the two layers can be shown instead of the numbers of the nodes (if desired), in order the end user to comfortably manipulate the package. It is enough to type:names(0):Step 9: a 2D representation of the whole network, where the three initial graphs have been merged into two,Gi∗, Gs∗, as explained above, that also shows the gauge changeovers can be obtained by typing (see Figure 10):display(IT);Step 10: finally, a 3D representation of the whole network (in two levels) can be obtained by typing (see Figure11):nice_3D();TwoLevels3DPlot;Observe that how to represent a certain route can be found inSection 4.


## 3.2. Obtaining the Best Route and Timing

The analysis of the Madrid––Seville route is included as illustration (here, we suppose that the input data of the network have already been introduced). If, for example, the end user types:Route_M_S:=bestRoute(H,"Madrid At_s","Sevilla_s"):the following output is obtained:[["Madrid At_s", "C. Real_s", "Puertollano_s", "Cordoba_s", "Sevilla_s"], 122]that is, the best route and the corresponding timing (in minutes) have been stored in variable Route_M_S. The best route is a list of stations. They can be shown by typing:Route_M_S[1];["Madrid At_s", "C. Real_s", "Puertollano_s", "Cordoba_s", "Sevilla_s"]Route_M_S[2];122Let us underline that the best timing (a Madrid–Seville nonstop) is nowadays 2 h 20m = 140 m. The approximation is not bad, as(i)
It has to be taken into account that high-speed trains in Spain are scheduled with a margin of a few minutes (due to a strict money back policy if there are small delays)(ii)
The first kilometers in the neighborhood of the origin and destination stations are traversed at limited speed(iii)
Not all intermediate stations are passed at full speed (details that are not considered by the package).


## 4. Case Study: A Nontrivial Example in the Whole Spanish Railway Network

The package has been used to analyze the Madrid–Seville, Madrid-–Badajoz and Badajoz-–Lisbon routes, based in present and historically available lines [26–28].It is clear that the accuracy of the timings obtained strongly depends on the accuracy of the input data.In order to show the possibilities of the new package when treating bigger networks, we shall consider afterwards the whole Spanish railway network, excluding the narrow gauge subnetwork (see Figure12). Note that all lines with passengers services are considered, but not all stations (only the main ones and all the junctions, in order to declare all the sections of the network considered).Figure 8
Diagrams of the Iberian gauge railway network of SW Spain. In this figure, distances are shown on the left and theoretical speeds on the right.
(a)
(b)Figure 9
Diagram of the best possible timings obtained for the Iberian gauge railway network of SW Spain. Vertex 34 is Madrid, 19 is Badajoz, and 3 is Seville.Figure 10
Diagram of graphG∗ corresponding to SW Spain showing the best possible timings (in hours) for both Iberian and standard gauges subnetworks (and for passing through the gauge changeovers).Figure 11
3D plot of graphG∗ corresponding to South Spain showing Iberian and standard gauge subnetworks and their connections (gauge changeovers).Figure 12
3D plot of graphG∗ corresponding to the whole Spanish railway network (excluding the narrow gauge subnetwork) showing the Iberian and standard gauges subnetworks (in the lower and upper planes, respectively) and the location of their connections (gauge changeovers).Let us compute a nontrivial example in the whole network: the best route from Valencia (in the West coast) and Canfranc, (in the NW). Once the data have been introduced, and the graphs have been computed (see Section3.1), it is very simple to ask the system or a best route and timing. To store it, for example, in variable Route_V_C, it is enough to type:Route_V_C:=bestRoute(H,"Valencia_s","Canfranc");Route_V_C:=[["Valencia_s", "Requena_s", "Bif. Albacete_s", "Cuenca_s", "Madrid At_s", "Guadalajara_s", "Calatayud_s", "Zaragoza_s", "Tardienta_s", "Tardienta_i", "Huesca_i", "Canfranc"], 237]Route_V_C is a list with two elements: its first element is a list detailing the best route found and its second element is the estimated time (237 minutes in this case).Maple took 0.015 seconds to perform this computation in a standard computer.Afterwards a 2D diagram of the route, distinguishing when the train is set to Iberian or to standard gauge, can be asked by typingPlottingRoute2d(H, Route_V_C);PlotRoute2d;and the plot of Figure 13 is obtained (let us recall that there are dual gauge sections, so how the train is set is the most precise information).Figure 13
2D plot of the Valencia–Canfranc best route (the part of the route where the train is set to standard gauge is on the right hand side, and the part where it is set to Iberian gauge is on the left hand side). The long horizontal connection represents the pass through a gauge changeover.Finally, a 3d diagram of the route, that allocates the sections when the train is set to standard gauge in the upper plane and to Iberian gauge on the lower plane, can also be constructed just by typingPlottingRoute3d(H, Route_V_C,{});PlotRoute3d;This way only the names of the stations and junctions along the route appear in the diagram, but it is possible to make other names to appear too. For instance,PlottingRoute3d(H, Route_V_C,{"Sevilla_i","Sevilla_s", "Barcelona_i","Barcelona_s"});PlotRoute3d;plot the same diagram but Sevilla_i, Sevilla_s, Barcelona_i and Barcelona_s, although not on the route, are correctly allocated in the corresponding plane of the 3D diagram (Figure 14).Figure 14
3D plot of the Valencia–Canfranc best route. The part of the route where the train is set to standard gauge is on the upper plane (in red) and the part where it is set to Iberian gauge is on the lower plane (in green). The long vertical connection represents the pass through a gauge changeover (in green).


## 5. Conclusions

Using an appropriate approach to shortest route finding and timings computation in a dual gauge railway network turns it into a simple problem. This way any standard shortest route algorithm can be used, for instance, those included in the built-in graph packages of some computer algebra systems.We know of no comparable package treating railway networks with dual gauge sections and gauge changeovers (what makes it impossible to directly use standard shortest route algorithms). The related package implemented by the authors some years ago uses a completely different and far more complex mathematical model.



---

*Source: 8146150-2019-12-05.xml*