< Back to blog
PUBLISH DATE:
UPD:
Yaryna KordubaYaryna KordubaFull-Stack Software Developer

Advancing Transport Networks: The Scientific Approach and Software Solution

How to explore the structure of transport systems, identify their main characteristics, and assess their resistance to attacks.

advancing transport networks

This article describes the analysis of the public transport networks (PTNs) of Lviv, Ukraine, and Bristol, England. In this analysis, we explore the structure of the transport systems, identify their main characteristics, and assess their resistance to attacks. For that, we consider the public transport systems as the networks of nodes and connections between them. Data processing is conducted with the help of such software solutions as RxJS  and a library for geospatial analysis turf.  

Problem Description & Historical Precedent

Rapid urbanization is one of the key characteristics of the modern world. In 1800, only 3% of the world population lived in cities. However, by 2007, the number of city residents had exceeded 50%. What is the definition of a comfortable urban space? How to stimulate the development of urban business, culture, and infrastructure? 

“American” Way of Urban Development

There were a lot of frankly unsuccessful ideas for urban planning. One of such examples is the "American way." Mass "automobilization" and slow development of public transport are its main features. Such a concept was used in Detroit city planning. In the 1950s, the city was "the car capital of the world" and one of the wealthiest parts of the USA. The plants of Ford, Chrysler, and General Motors created thousands of working places. More and more citizens were buying cars at affordable prices.

At the same time, the public transport system stagnated. The big corporations in their marketing campaigns said that public transport was the option for the poor. The companies representatives stood for the dismantlement of the electric transport lines and extensive construction of highways. In the end, the mass automobilization led to the city collapse, and Detroit became the big car parking. Even the building of The Michigan Theatre was transformed into a parking lot.

The Michigan Theatre today. Retrieved from the article of Matthew Lambros The Michigan Theatre 
The Michigan Theatre today. Retrieved from the article of Matthew Lambros The Michigan Theatre 

Middle-class representatives started moving away, leaving the whole neighborhoods abandoned. Those who stayed in the city were usually unemployed or people with low income. A lot of criminal groups appeared. In the 70s, because of the oil crisis, the outflow of the citizens only increased. In general, in the last 50 years, the population of Detroit decreased by 2.5 times. The modern Detroit is the city of abandoned streets where people are sometimes scared to get out of their cars.

Abandoned Packard plant. 
Retrieved from Wikipedia
Abandoned Packard plant. Retrieved from Wikipedia

“European” Way of Urban Development

However, there is another, the "European" way of development. One of its examples is Amsterdam – the bicycle capital of the world. In the middle of the 20th century, the city could also choose automobilization. The authorities began destroying entire blocks to build new roads there. However, such actions evoked the resistance of city residents. Another reason for complaints was an increasingly high death rate because of the car accidents. The activists of the group Stop de Kindermoord ("Stop Killing Children") regularly arranged strikes and blocked roads with bicycles. In the 70s, because of high prices for oil, the authorities introduced new politics aimed to decrease the use of personal transport. They organized "Days without the cars" and built networks of bicycle roads. Nowadays, the streets of Amsterdam are planned with the priority to pedestrians. There are not too many cars in the city. To reach destinations, citizens usually use bicycles or public transport. The public transport network includes 4 subway and 15 tram lines, 43 bus routes, and 6 ferries. The ferries are free of charge. Amsterdam and the Netherlands as a whole is an example of proper city planning. The most significant transport nodes often look like multilevel stations with the subway, bus stop, train station, and bicycle parking lot at different levels. Their main characteristics are elegance and simplicity. The passengers do not feel lost and quickly get to understand where they need to go. One of such transport nodes is The Hague Central Station.

The Hague Central Station. Retrieved from the blog of Alexander Shutyuk 
The Hague Central Station. Retrieved from the blog of Alexander Shutyuk 

The goal of urban studies is to explore the examples of city planning, understand mistakes, and develop a system of urban planning recommendations. 

In the next part of this article, we would like to explain the scientific method of urban exploration using the examples of Lviv, Ukraine, and Bristol, England.

The Tale of Two Cities

Bristol

In Bristol, you can travel by bus, tram, or ferry.

Retrieved from bristolferry.com
Retrieved from bristolferry.com

According to the research of ESP Group – the transport contact center of Great Britain, the public transport system of Bristol is one of the least comfortable in the UK. The city takes the last, 26th position with the index 5.31 out of 10. There are various reasons for such rating:

  • Unpunctuality and tardiness of the transport

  • Insufficient number of vehicles

  • High price

  •  Low service quality

  • Road congestion

  • High level of gas emission. 

To increase the speed of travel, the city authorities renovated two historical bridges and constructed a new one. The city center was made pedestrian. In 2018, Metrobus – a three-routes network of high-speed buses – was launched. The citizens of Bristol often joke that the system of teleportation is another project under development. Its implementation should end in the next 700 years.

Lviv

The history of the Lviv public transport began with the omnibus, which served the passengers since 1835. In 1880, the first horse-drawn tram appeared at the city streets. 

At the end of the 19th century, the horse trams already could not handle the passenger flow. Therefore, in 1893, a tender for construction of electric tram lines was held. The German company Siemens & Halske constructed 8.3km of the tram lines and built the tram depot with the electrical station. In 1894, 16 trams got on their route for the first time. Interestingly, the traffic is left-hand. The movement direction was changed to the right-hand just in 1922 year. 

Halytska Square in Lviv
Halytska Square in Lviv

Till the middle of the 20th century, the trams remained the primary transport of the city. In 1928, the buses appeared, and in 1952, the trolleybus lines started operating.

In the 60s, the idea of subway lines construction appeared. The construction of the first underground station began behind Pototskyy palace. Suddenly, the ground started sinking, and a 30cm-wide crack appeared on the palace building. The workers stopped the construction works and filled the tunnel with concrete. In 2008, the idea of subway construction appeared in the general city plan again, but the implementation did not take place.

Lviv underground tram scheme
Lviv underground tram scheme

At the beginning of the 21st century, the number of cars on the roads increased. People spent a lot of time in traffic jams, and the transport companies did not stick to the schedule. The city was noisy, and the air was polluted with gas emissions. 

Before Euro-2012, a French company Louis Berger began the reorganization of the Lviv transport network with the financial support from EBRD (European Bank for Reconstruction and Development).

One of the goals of the project was to facilitate the traffic in the city center. Six new radial bus routes appeared with their terminal stops making a circle around the central part of the city. 

Stops that form a circle around the city centre
Stops that form a circle around the city centre

Forty chord routes started operating to provide connections between the suburbs. The bus routes that duplicated the electric transport lines were canceled. GPS devices appeared in the buses. In 2012, the Lviv Center for Traffic Management started working. The bicycle roads also appeared, and Lviv center became pedestrian. The tram network also faced the changes. 

Nowadays, the authorities are working on increasing the number of public transport with the priority going to trams and trolleybuses.

Public Transport as a Complex Network

One of the methods of transport systems analysis is a complex network theory. In terms of this theory, we consider a transport system as a set of nodes (vertices) and connections (edges) between them. The nodes and their connections form a network – a graph. There are different ways to represent a transport system as a graph: L-space, P-space, and C-space.

For example, here are the parts of Lviv tram routes #3, #6, and #8:

ptnLSpace-min

L-Space ("Space of Stops")

Let’s mark each transport stop as a node and edges between as routes. Their representation in L-space looks like this:

ptnLSpace-min

P-Space ("Space of Transfers")

Let's build a graph that resembles L-space, and the stops are marked as nodes as well. However, the two stops are connected with an edge if they belong to the same route. Mathematically, the routes in P-space are complete subgraphs of a transport network.

ptnPSpace-min

C-Space ("Space of Routes")

Let’s generalize the appearance of transport systems. In C-space, we mark the routes as network nodes. Every two routes are connected if they have at least one common stop. The trams #3 and #8 have common stops. However, the tram line #6 is fully isolated. Thus, our C-space looks like this:

ptnCSpace-min

Data Processing

For the exploration, we chose the public transport systems of two cities: Lviv and Bristol.  

Lviv stops heatmap
Lviv stops heatmap

Bristol stops heatmap
Bristol stops heatmap

Our goal is to explore the structure of the transport network. We aim to know how well connected and stable it is, how many large stops it has, and which stops are the most important for the robust network functioning. 

Therefore, we can simplify the transport data (the illustration below shows the simplification steps):

  1. Merge the stops that lay within radius R = 40m from each other;

  2. Reject route directions;

  3. If there are a few connections between stops, leave only one.

With the simplified transport data, we build L-space representations.

Transport network simplification steps
Transport network simplification steps

Software Solution

To process the dataset of Bristol from ATCO-CIF format (special format used for British transport data) we used ATCO-CIF parser. The geospatial coordinates for Bristol were provided in OS Grid system. Thus, we converted  them into latitude and longitude with Geodesy Library. All the further geospatial operations, such as filtering of the stops according to the city boundaries, and DBSCAN clusterization of the stops, were conducted with the help of the library for geospatial analysis turf.

The visualizations used in the work were made with d3 and mapbox-gl. (The repository for the article can be found here).

Network Topological Characteristics in L-Space

We can characterize a network by various mathematical characteristics: node degree, shortest path, assortativity and clustering coefficient, etc. 

And already before the topological estimations we saw the important differences between Lviv and Bristol transport networks. One of them is that Bristol network in L-space has almost two times more nodes than Lviv network. 

Lviv and Bristol networks in L-space. The size and brightness of a node indicate the number of its connections.

Lviv and Bristol networks in L-space. The size and brightness of a node indicate the number of its connections.
Lviv and Bristol networks in L-space. The size and brightness of a node indicate the number of its connections.

Node Degree

A node degree k is the number of edges that connect it to other nodes. That is in L-space the node degree of a stop indicates the number of the stops that are adjacent to it. The node degree tells about the importance of the node for the system. The accident at a stop with one connection would not cause the transport collapse. At the same time, the accident at one of the central stops, where many routes intersect, can stop the operating of the whole system. In the context of the overall network, we use the average node degree:

kavg = ⅀k_i / N,

where N is the number of nodes in the network. The value of kavg is often close to 2 as most of the stops in a network are intermediate stops with two edges. 

Findings:

  • In Bristol, the average node degree is much higher than in Lviv:  kavg BRS=3.4, and kavg LWO=2.6. That is the average Bristol stop has much more connections than the one of Lviv. 

  • The maximal node degrees also have significant differences. In Bristol kmax BRS = 25, and in Lviv kmax LWO = 10. In other words, the most significant transport node of Bristol has 2.5 more connections than the most significant node on Lviv.​

Shortest Path

Usually, we can choose from a few route options to travel between two transport stops. The shortest path lAB between the stops A and B would be the path with the smallest number of nodes (in this case, stops). For the analysis of the whole network, we use the mean shortest path lavg. 

Findings:

  • For Bristol lavg BRS= 12 stops

  • For Lviv lavg LWO = 14 stops.

Network Diameter D

D is the longest path from all the optimal paths in a network. In L-space it indicates the number of stops between two farthest stops in the transport network. 

Findings:

  • The diameter of the Bristol network DBRS = 37 stops.

  • For Lviv network DLWO = 40 stops.

Clustering Coefficient C

Clustering coefficient C describes the tendencies of the nodes to group together. C(i) for the node i shows how many of its neighbors are the neighbors of each other. 

image65-min

This way, we can know whether our transport network is strongly connected or not. 

Findings:

  • The clustering coefficient of the Bristol network is much higher than that of Lviv.

  • Cavg BRS=0.1

  • Cavg LWO=0.05.

Assortativity

Assortativity r shows the tendencies of forming the connections in a network. If in a network r > 0, an average node tends to form connections with the nodes of similar node degree (large nodes with large nodes, small nodes with small). Such a network is called assortative. r < 0 means that the network nodes tend to connect the nodes with non-similar node degree. Such a network is called disassortative. 

Findings:

  • In Bristol  rBRS = 0.31 – the Bristol network is assortative.

  • In Lviv  rLWO = −0.03 – Lviv transport network is slightly dissortative.

Network Stability Under Attacks

The 9 of January 2017 the workers of The London Underground went on strike. 114 out of 270 subway stations stopped operating. 75 stations more worked partially. The stoppage of the most popular transport in the city led to a collapse. Also, malfunctions in the network may appear accidentally. More than that, terrorist acts or strikes occur at the most important parts of the transport network to cause the most critical harm. 

How could it be predicted?

Molloy-Reed Criterion 

We can analyze the network resilience to the deletion of the node in different ways. One of them is the Molloy-Reed criterion. With this criterion, having only the general network characteristics, we can predict the stability of a network to random deletions of the nodes. We consider a network to be stable if it contains the largest connected component GCC. The largest connected component is the largest network subgraph by the number of nodes in which a path between any two nodes exist. The higher the value of Molloy-Reed Criterion is, the more stable the network is. Both Lviv and Bristol networks are stable to random removals of the nodes. 

Conclusions

The public transport networks of Lviv and Bristol have a lot in common. Both networks are stable to the attacks and similarly react to different attack scenarios. The shortest path length efficiency, the network diameters, and the average number of transfers are almost similar. Both Lviv and Bristol networks have relatively low average shortest path lengths and high clustering coefficients. However, some characteristics of transport systems differ sharply. Although the area of Bristol is smaller than the area of Lviv, the number of its transport stops is almost two times higher than in Lviv. In the majority of the spaces, the Bristol network has higher average and maximal node degrees. ​

What Is Next?

In this exploration, we analyze the "skeletons" of the networks using the static data. The next step is to analyze the networks together with their dynamic processes. These processes include the changes in transport and passenger flow during a day. It is also reasonable to consider the capacities of stops and routes during the simulations. In such simulations, removal of one node causes the redistribution of its load to the other nodes. If the load at the node exceeds its capacity, this node also falls out of the network. In such a way, one can explore the cascade destruction of the network.

The article is based on the B.Sc. thesis written by Yaryna Korduba at the Ukrainian Catholic University under supervision of Prof. Yurij Holovatch, (ICMP, Lviv) and Dr. Robin de Regt (Coventry university). Thanks to Mykhailo Ivankiv, and Oles Kozak for helping with the research.