October 06, 2016

Data mining digs deep for punctuality improvements

Written by  Hideyuki Yabuki, Keisuke Uchikoshi andNorio Tomii
  • Print
  • Email

A team from Tokyo Metro and Chiba Institute of Technology have used data mining techniques to develop an algorithm to identify primary delays which occur frequently and have a big impact on the punctuality of succeeding trains. Hideyuki Yabuki, Keisuke Uchikoshi, and Norio Tomii* explain how the algorithm can be used.

WE can now obtain various types as well as large volumes of train operation data which can be analysed to improve punctuality and timetable robustness. But, because the amount of the data is huge, it is necessary to establish an efficient approach in order to obtain useful insights.

TokyoRush hour4To detect the causes of delays from train traffic records, we have developed an approach based on the association rule, which is a very popular technique in the data mining community. We consider events such as a delay or an increase in dwell time and analyse the relationships between them. This enables us to identify the causes of delays which occur frequently and have far-reaching consequences and suggest the most effective countermeasures to reduce them. This approach also enables us to assess the effectiveness of some existing countermeasures.

One of the recent problems on Japanese railways in urban areas is that small delays often happen during rush hours. Trains operate at headways of around two minutes, so even a delay of less than one minute easily propagates to other trains and the delay tends to expand. Railway companies are therefore keen to reduce the occurrence and propagation of such small delays, and in particular introduce effective delay reduction measures to reduce the primary delays which happen very often and cause secondary delays in a wider area.

Various countermeasures already exist to reduce primary delays such as timetable revisions, signalling improvements, and deployment of sufficient staff on a platform. Due to the density of the traffic and because small delays happen everywhere, it is difficult to determine which countermeasure is the most effective in reducing delay. In addition, due to the high train density and because a number of countermeasures are introduced simultaneously, it is not easy to ascertain whether the countermeasures already introduced have been effective or not.

We consider an event such as a delay or an increase in dwell time, as an item and try to analyse the relationship between them. As outputs of our algorithm, we can get association rules such as: “if there is a delay longer than one minute at Station X, it is quite probable that the delay will propagate to more than five succeeding trains causing delays longer than three minutes at Station Y.”

This approach makes it possible to identify the cause of delays which happen frequently and suggest the most effective countermeasures to reduce them. We can also apply this approach to ascertain the effectiveness of existing countermeasures by comparing the association rules obtained from the train traffic records before some countermeasures were introduced and those obtained from the records after the countermeasures were introduced.

When we apply the association rules (see panel), we must ensure that they do not assure the existence of causality. The process also produces more rules than we can manage. So, we designed our algorithm to sort out only the rules which are both useful and explain causality.
For the algorithm, we consider the following events as an item:

  • an arrival delay at a station
  • a departure delay from a station
  • an increase in dwell time at a station.
  • an increase in running time between one station and the next, and
  • an increase of the interval between two consecutive trains at a station.

We try to obtain association rules from these data. We expect to find an association rule such as “if a delay to train X at Station A is longer than a seconds, then the delay propagates to more than b trains at Station B, which we assume is a large, important station on the line, and cause delays longer than y seconds.”

As we are only interested in detecting the events which cause delays, only a delay longer than a certain threshold appears as an event on the right hand side of the association rule, whereas other types of events might appear on the left hand side.

The overall structure of our algorithm is shown in Figure 1. We input train traffic records containing actual and planned arrival or departure times of all the trains for a certain period of time into the algorithm. From this data, we construct a binary matrix in preparation for obtaining association rules.

Tokyofig1Let us assume that there are three trains (1 to 3) and four stations (A to D). Small circles signify delays. In this example, we start to trace the propagation of delays from the delay of Train 1 at Station A (Figure 2). We assume the delay to Train 1 at Station A is longer than a threshold. If there is a delay longer than a threshold for Train 1 at Station B, we consider the delay has been caused by propagation. In this example, we trace the delay propagation toward the delay of Train 3 at Station D. After this process, we get a binary matrix (Figure 3) which corresponds to the train graph of Figure 2, meaning “1” is stored only in the cells which correspond to the delay of Train 1 at Station A and the delay of Train 3 at Station D and “0” is stored in other cells. From this binary matrix, we extract association rules using the a priori algorithm.

We have applied our algorithm to actual data in order to confirm whether it works well. We used train traffic records of Tokyo Metro’s Hanzomon Line, which connects Shibuya (Station Shi) and Oshiage (Station Oshi). The line is 16.8km long, has 14 stations and is operated with 200m-long trains. During peak periods, 28 trains per hour per direction are operated with services running through to the suburban lines of other railways at both ends. All trains stop at every station. In our numerical experiments, we analysed the trains operating between Station Shi and Station Oshi.

Counter measures

The Hanzomon Line used to suffer frequent delays of several minutes and Tokyo Metro gradually took several counter measures to improve punctuality. On February 3 2014, the metro began to deploy more staff on the platform of Station N, which is used by passengers transferring between the Hanzomon Line and other metro lines. The front part of the trains tend to be congested because the stairs leading to other lines are at this end of the platform resulting in increased dwell times.

On March 29 2014, signalling at Station Ku was upgraded to reduce the tendency for the intervals between trains to increase because the distance between Station Ku and the next station is rather short and the signalling was not sophisticated enough to prevent this from happening.

An intensive analysis conducted by Tokyo Metro showed that both of these countermeasures were very effective in reducing delays.

We have applied our algorithm to this data to confirm if it produces results similar to those of the experts. If we succeed in obtaining association rules similar to the results of the experts, we will be able to evaluate the countermeasures to reduce delays more quickly and with less work.

We applied our algorithm to three periods: Period A (February 2 2014), Period B (February 3 - March 28 2014) and Period C (after March 29 2014). We selected the data from all the weekdays in January 2014 as the data for Period A, all the weekdays prior to March 28 as Period B and all the weekdays of April as Period C.

Because the countermeasures shown in Table 1 are aimed at reducing an increase in dwell times, we ignored other events such as delays and increases in running times. We are interested in the causes of arrival delays at Station Kiyo (another important station), so we tried to extract rules which have Station Kiyo on the right hand side. We set the threshold as: arrival delay 30 seconds, increase in dwell times 30 seconds for Station Shi, 15 seconds for Station Omo and Station A, 10 seconds for other stations, arrival delay for the right hand side (arrival delay at Station Kiyo) 30 seconds.

If our algorithm works properly, we expect the following outputs:

  • Period A: association rules relating to the increase in dwell times at both Station N and Station Ku will be extracted
  • Period B: association rules relating to the increase in dwell times at Station N will not be extracted while those at Station Ku will still be extracted, and
  • Period C: association rules relating to the increase in dwell times at both Station N and Station Ku will not be extracted.

Table 2 shows the results of our algorithm as we expected. For Period A, association rules which have an increase of dwell times at Station N in LHS were obtained (underlined in red), whereas such rules were not found for Periods B and C. This means that the countermeasure for Station N taken at the beginning of Period B worked well, which is a reasonable result and corresponds with Tokyo Metro’s analysis.

Association rules which have an increase in dwell times at Station Ku were found for Periods A and B (underlined in red) but such rules were not found for Period C, which means that the countermeasure taken for Station K at the beginning of Period C worked well. Again this accords with Tokyo Metro’s observations.

Tokyofig2However, the number of extracted rules is smaller than we expected. This is partly because we differentiated trains and partly because we took propagation of delays into account too strictly. In addition, we focused on an increase in dwell times, which usually ranges from several seconds to 1 minute. Thus, it may be difficult to fix an appropriate threshold.

In the future, we want to identify a method to fix the thresholds appropriately. Although our first intention was to find a primary delay, it might be better to find a secondary delay if it is much easier to find. For example, an increase in dwell time is an event which causes a primary delay (departure delay) and the arrival delay of the succeeding train is a secondary delay. In this case, the increase in dwell time is usually rather small and the arrival delay of the succeeding train is much greater - the train is often compelled to stop before it arrives. We therefore believe it is much easier to find the arrival delay or an increase in headway.

We also want to establish a method to decide the thresholds. At the moment, we decide the thresholds based on our experience but we need a more reasonable approach to fix the thresholds. At the same time, we should conduct a sensitivity analysis for them. We also want to clarify if an idea to find secondary delays works better.

Association rules

Let I = {i1, i2,...,in} be a set of n binary attributes called items. Let T = {t1, t2,...,tm} be a set of transactions. Each transaction in T contains a subset of the items in I. An association rule is defined as an implication of the form X ==> Y where X, Y CI and X nY = Ø. The set of items X and Y are called the left hand side (LHS) and the right hand side (RHS) of the association rule respectively. The support supp(X) of an item (or a set of items) X is defined as the proportion of transactions which contain X in the whole transactions. The confidence of an association rule is defined as conf (X==>Y) = supp (X U Y) / supp(X).

Get the latest rail news

IRJ Rail Brief newsletter covers global railway news