Keywords

1 Introduction

The subway systems in general are critical urban infrastructures, exposed to frequent disruptions. Various factors contribute towards serious schedule delays, including having the entire system shut down. A temporary shutdown of a means of public transport is relatively rare, but has a serious impact over the activity of a city. Moreover, if this unfortunate event was not due to natural hazards or temporary failures of the system, but purposely targeted attacks, it poses then security issues.

In this paper, we analyze the scenario where a threat propagates through the network using the subway system. For this, we tackle two research questions: 1. What is the longest ride one can have in a threat propagation, such as a flee attempt using the subway system within a limited travel time and at a specific time of the day? 2. What is the maximal number of stations one can reach in a flee attempt using the subway system within a limited travel time and at a specific time of the day?

We conducted the analysis on a subway system modeled as a mathematical network where the stations are nodes and the connection between pair of stations are edges [1]. The train frequency at each station, the corresponding subway line(s) of each station, and the travel time between adjacent stations are encoded as weights on edges. Hence, the research questions can be redefined as:

  1. 1.

    What is the longest day-dependent and time-dependent (i.e., day- and time dependent) shortest path of a subway network. (Recall that the shortest path is the path between two nodes in a network having the smallest edge-weight sum.)

  2. 2.

    What is the maximal day-time dependent sub-network (component) of a subway network? (Recall that the maximal component is a connected sub-network that starting from a root node of the network covers a range of nodes that satisfies a given maximal edge-weight sum.)

The first question is a particular application of the weighted shortest path problem [2] that can be solved efficiently using Dijkstra’s algorithm [3]. The second question is a particular application of the constrained maximum-weight connected graph problem [4]. The latter is the focus of this paper. Here, the first problem is treated as a sub-problem of the second. Namely, a rooted day-time dependent component is a collection of the corresponding shortest paths starting from a root node to each node of a maximal edge-weight range of nodes. We consider the maximal day-time dependent component (MDTDC) to be the main problem, and the longest day-time dependent shortest path (LDTDSP) to be the sub-problem.

Various optimized solutions to this problem are available in [5,6,7]. The application range is very diversified and similar analyzes are applied to biological systems [8,9,10], wildlife corridors design [11, 12], forest planning [13], communication network design [4], computer vision [14], and few others.

Our main contribution is a well-defined analysis method that we apply to subway networks. The subway networks are special because of the variation of the edge weight value. Thus, we consider the weights to have two sets of values, depending on which case they fall into. One case is when two adjacent nodes are part of the same subway line; in that case the weight value on the edge represents the travel time between nodes. In the second case, when two adjacent nodes are not part of the same subway line, then the weight value on the edge represents the sum of waiting times at the starting node and the travel time between nodes.

A detailed description of the conducted analysis is given in Sect. 2. The Munich subway network proves to be a good candidate [15, 16] for our analysis due to its size, ridership [17], and train frequency variation over train time schedules [18]. More details on the data collection is given in Sect. 3. The results are presented and discussed in Sect. 4. The paper concludes with considerations on the application on this network and remarks for other subway networks.

2 The MDTDC Problem with the LDTDSP Sub-problem

2.1 Formulation

Let \( G = (V,E) \) be a graph and \( v_{i} \in V \) a random starting node. Knowing all edges \( e_{ij} \) of that node, the time of the day (or the hour of the schedule) \( t_{D} \), the corresponding frequencies \( f(t_{D} , e_{ij} ) \), and their travel times along the edges \( d(v_{i} , v_{j} ) \), we define the component \( G_{c} \) of \( G \) of all nodes that can be reached in time \( t \) starting at \( t = 0 \) from \( v_{i} \).

All the vertices \( v_{h} \) in \( G_{c} \) satisfy the condition that there is a shortest path from \( v_{i} \) to \( v_{h} \) such that it can be traveled along in time less than \( t \):

$$ P\left( {v_{i} ,v_{h} } \right) = \mathop {\hbox{min} }\limits_{{P\left( {v_{i} ,v_{h} } \right)}} \left( {\sum\nolimits_{{e_{ij} \in P\left( {v_{i} ,v_{h} } \right)}} {\alpha \frac{60}{{f(t_{D} , e_{ij} ) }} + d(v_{i} , v_{j} )} } \right) \le t $$
(1)

where \( P\left( {v_{i} ,v_{h} } \right) \) denotes the shortest paths from \( v_{i} \) to \( v_{h} \), \( \alpha = 0 \) if \( v_{i} \) and \( v_{j} \) belong to the same subway line, else \( \alpha = 1 \).

From (1), for a given \( t_{D} \) and \( t \), MDTDC is defined as \( \sum {P\left( {v_{i} ,v_{h} } \right)} \), and LDTDSP is defined as \( P_{max} \left( {v_{i} ,v_{h} } \right) \). In Fig. 1 (left) is an example of the MDTDC on a simple network. In this example, the MDTDC of the network starts from the red (center) node, and all the orange nodes represent the visiting range for a given maximal edge-weight of three. In Fig. 1 (right) is an example of the LDTDSP on the same simple network. Here, the LDTDSP of the network starts from the red (center) node, and all the orange nodes represent the visiting path for a given maximal edge-weight of three.

Fig. 1.
figure 1

A simplified version of the application for a given maximal edge-weight of three without considering subway lines or train frequencies. MDTDC is exemplified on a simple network to the left. LDTDSP is exemplified on a simple network to the right.

Full size image

2.2 Algorithm

Input: An input file containing the adjacency list of the subway network for one schedule with multiple weights, and an array of the travel time limits. The input file has the following information on each column: col_1 = station from, col_2 = station to; col_3 to col_26 = train frequency on that edge by hour from 00 h to 23 h (24 columns); col_27 = subway line; col_28 = travel time on edge in min. The array has the following elements: 5 min, 10 min, 15 min, 20 min.

Output: The results for MDTDC and LDTDSP for each travel time limit.

figure a

3 Data Collection

The analysis described in the previous section was applied to the Munich subway network. The network ridership in average is above typical, with more than 398 million passengers per year [17] for a network with only 100 stations [17]. The train frequency of this network varies along the subway lines, and sometimes is different along the same line but in the opposite direction. Namely, the number of trains of a subway line entering a station in a day is not the same from both directions, because sometimes trains are redirected on other lines sharing the same destination station. This makes the Munich subway network a very good candidate for our analysis.

For this paper, the train frequency data for year 2017 was collected for every station of the network. This data is publicly available and it can be accessed from the website of the Munich’s association of public transport authorities (MVV) [18].

The subway network has four main schedules, corresponding to Monday-Thursday, Friday, Saturday, and Sunday/Holiday. The latter one is the most relaxed schedule in terms of train frequency, while Friday schedule is the busiest. MVV provides few side schedules with a more relaxed train frequency during the children’s vacation, or more intense during the carnival days, Christmas Eve and New Year’s Eve [18]. In this paper, only the regular schedules are considered. This network has eight subway lines (U1–U8), but only six (U1–U6) have a daily schedule. The other two (U7–U8) reuse stations of other lines, with a limited train frequency, because these lines were created only to avoid overcrowding the central stations by supplementing the number of trains, e.g. during peak hours. Therefore, the train frequency of U7–U8 is assimilated by the lines having a regular schedule at the stations reused by these lines [19]. E.g. the line U7 only reuses stations of U1, U2, and U5, therefore in our analysis we do not treat this particularity, and the train frequency of U7 is attributed to the other three lines whose stations have been used.

For each edge, the train frequency starting or ending in one of the two corresponding stations is saved for each hour of the day. Along with the frequency on each edge, the travel time and the subway line are also stored. The train number handled by a station in an hour varies between 0–30 trains. The travel time between every two adjacent stations varies between 1–4 min. The lines are numbered between 1–6 for the stations corresponding to one line and 9 for shared stations by multiple subway lines. Figure 2 presents an example of cleaned input data for the analysis.

Fig. 2.
figure 2

Example of cleaned input data for the analysis of the Munich subway network.

Full size image

4 Results and Discussion

In this section, we present and discuss the results obtained after the data set was cleaned and we applied the analysis method from Sect. 2. MDTDC and LDTDSP are computed for the Munich subway network during the week days and weekend days. For the week days, two related schedules are analyzed: Monday-Thursday and Friday. For the weekend days, the other two schedules are analyzed: Saturday and Sunday/Holiday.

For our analysis, MDTDC and LDTDSP are calculated for a maximal given travel time corresponding to 5 min, 10 min, 15 min, and 20 min, in order to have a more diversified range of travel windows. For MDTDC, the results below 5 min travel time limit are flat, while for a travel time limit above 20 min, MDTDC covers more than half of the stations.

In Tables 1 and 2, the results show a linear growth of MDTDC from one travel time limit to another. One can observe that as the travel time limit increases, MDTDC varies from one hour to another. The results in Table 1 are more diversified than in Table 2 because the week days have a higher train frequency variation on the subway lines. For example, taking the 20 min travel limit, the difference between 4 am and 7 am on a Monday-Thursday schedule is more than double, while on a Sunday/Holiday schedule the difference is very small.

Table 1. MDTDC of the Munich subway network during week days, Monday-Thursday (M-T) and Friday (Fr) schedules, for a maximal given travel time of 5/10/15/20 min
Full size table
Table 2. MDTDC of the Munich subway network during weekend and holidays, Saturday (Sa) and Sunday/Holiday (S&H) schedules, for a given maximal travel time of 5/10/15/20 min.
Full size table

Notice that MDTDC formed in a 5 min travel time window is quite large for all train schedules except 2 am to 4 am. That is, if one finds the starting station that generated the size of this component, in only 5 min one can reach at any time of the week a range of up to 12 stations. This represents 12% of the size of the network. Furthermore, in up to 20 min time, one can reach up to 47 stations during the peak hours of the week days, which is almost half the size of the network.

This variation can be better explored in the two charts of Fig. 3. The left side chart corresponds to the MDTDC results from Table 1, while the right side chart corresponds to the MDTDC results from Table 2.

Fig. 3.
figure 3

Variation of MDTDC of the Munich subway network. The left side chart corresponds to week days (Table 1), and the right side chart corresponds to weekend and holidays (Table 2). The numbers along the radial axis represent the number of stations in the maximal component.

Full size image

Notice that, since the network has about 100 stations, 47 stations in the maximal component means about 47% of the network. Thus, the maximal component is between 12% for 5 min and 47% for 20 min., see Fig. 3.

LDTDSP of the Munich subway network for each schedule is presented in Table 3. The results are the same for all the schedules. LDTDSP changes only from one time travel limit to another, but not from one schedule to another.

Table 3. LDTDSP of the Munich subway network of each schedule for a given maximal travel time of 5/10/15/20 min.
Full size table

As mentioned before, there is a connection between LDTDSP and MDTDC. Thus, Table 3 can be read together with Tables 1 and 2. For example, if on Friday 8 o’clock MDTDC for a 20 min travel time is 47, then 13 (~28%) is given only by LDTDSP. The latter can be seen visual represented in Fig. 4.

Fig. 4.
figure 4

The Munich subway network with the stations part of LDTDSP highlighted in red during the Friday schedule at 8 am for a 20 min travel time.

Full size image

5 Conclusions

We analyzed the scenario where a human threat propagates through the network and we applied it on a subway system. We analyzed the properties of the system with propagation constrains in the attempt to find the maximal day-time dependent component and the longest day-time dependent shortest path for various schedules. The maximal component at the rush hours of the day, during the weekdays is very large, for a travel duration of 30 min; in fact, the maximal component is roughly half the total network. Even for 15 min, the maximal component is almost 40%. This raises serious concerns and consequences for the security of people in the network. The application to the Munich subway system shows that the selected data samples and analysis criteria were sufficient for this application. The names of the starting stations creating the maximal components and the longest paths were removed on purpose, the results should be used only in scientific terms.

This paper is yet another example suggesting that the activity of a subway system is fragile and justifies its presence in the critical urban infrastructures category. Here, we established a well-defined analysis method that can be applied to other type of transportation systems or to other systems with similar properties.