Relevant path planning using public transportation is limited by reliability of the transportation network. In some cases it turns out that we can plan paths with respect to expected delays and hereby improve reliability of the resulting path. In our work we focus on prediction of the delays in public transportation systems. For this purpose we use data from vehicle tracking systems used by transit operators - known as the AVL data. We compare statistic methods to methods of artificial intelligence using data from Prague trams tracking system. We discovered that in some cases the neural networks show better results than the statistic methods. In contrast, sometimes even simple statistical methods give as good results as those provided by the neural networks.
Many people need to travel almost every day. When they do so, they usually have two options - to use individual transportation means (e.g. a car) or to use public transportation. When making this decision, many aspects are taken into account. One of the important aspects besides price and duration of the journey is reliability.
Especially in larger cities, lot of money is often spent to support public transportation systems, including reliability improvements - mostly by building underground lines and by segregation of trams and buses from individual traffic.
An alternative way of improving reliability is by providing useful information. Given that we will never be able to ensure that the system is 100% reliable, we can soften the consequences of traffic irregularities by warning the passengers. In more advanced case we can improve path-planning systems in such way that they prefer more reliable paths. The main advantage of this approach to dealing with irregularities is that it is relatively simple and cheap. Transit operators usually already collect tracking data from vehicles. These data are known as Automatic vehicle location (AVL) data. AVL data give us information about positions of vehicles, typically in real-time.
In this article we find and compare approaches how to interpret the information from AVL data and how to predict future development of delays of the public transportation vehicles in real-time. We assume that the resulting information can be transmitted to passengers for instance via a mobile application. Since the number of people who possess a smart mobile device is increasing every year, this also means an increase of potential users of this kind of application. Additionally, transit operators can equip stops by information systems presenting this information to passengers.
We compare three methods: statistical, regression and neural networks. The statistical methods are expected to be computationally the least complex while the neural networks should provide the best results.
We also define and compare static and dynamic prediction. By static prediction we mean models that use only past data and do not have access to the information in realtime. Therefore, they can predict only expectable deviations that happen repeatedly.
Unlike static prediction, dynamic prediction does not use only past data, but takes real-time information into account as well. This allows recognition of unexpected problems in the transit network. On the other hand, realtime data have only short-term validity and passengers can use information from dynamic prediction system only when they are about to travel somewhere or while they are already travelling.
The structure of the article is as follows: The first section introduces the problem and the goal. The second section shows previous and related work. In the third section we analyse the problem in detail and in the fourth section we evaluate the selected methods. In the fifth section we compare and discuss the results. The sixth section offers some ideas about practical usage of the results. And the seventh section concludes the article and offers future focus. 2
There is a lot of work related to reliability of public
transport. Common public transport unreliability issues are
discussed by Rietveld et al. in [
An example of a dynamic approach is described by Tien
et al. in [
A dynamic prediction using statistical methods was
used by Wall and Dailey in [
Bohmova and Mihalak [
We focus mostly on transportation networks in larger cities. These networks usually have more complex structure without clear hierarchy and there are several options of getting from one location to another.
According to Rietveld at al. [
Rietveld at al. also mention an obvious trade-off. Faster
transport or shorter halting times will improve the
scheduled travel times, but will have an adverse effect on the
reliability of the service [
We were able to locate the effect described above in the data from Prague trams tracking system we have available. Let a be a stop somewhere near the middle of a specific line and let z be the final stop of the same line. We would like to express the relationship between D(a) being the delay at the stop a and D+(a, z) = D(z) − D(a) which is the additional delay at the stop z. We divided the past observations into clusters by D(a) value; each cluster contains connections with delay from k to k + 1 minutes at the stop a. Then we expressed the average additional delay for each of these clusters. If the delays on the way were independent, these values should be similar. But figure 1 shows there most probably is a relationship. While on the line 9b the drivers are usually capable of reducing the delay, the line 22a shows that the more delayed a vehicle is, the even more delayed it usually is on the rest of its way to the final stop. We have data from Prague trams tracking system from March and April 2008. When a tram serves a stop, it also sends a message to the tracking system where this information is stored. Therefore we don’t know the exact position of the tram in every moment; we have only information about the last stop the tram stopped at together with the associated time.
For objective evaluation of the methods we divided the data into learning set and test set. The learning set is about two times larger and is used as input when creating a model. The test set is then used to evaluate the model. The learning set contains data from March and the beginning of April, while the test set contains the rest of the data until the end of April. This way we simulate the real situation - that we create the model on the past data and use the model for predictions.
For evaluation of the methods we calculate the following metrics. In these metrics, an error is the difference between the predicted and real arrival.
• The average absolute error • Median absolute error • Mean absolute percentage error (the absolute error divided by the actual travel time) • 95% confidence interval of the absolute error • Percent of connections with absolute error under 60 seconds
For a particular tram currently located at a certain stop that we call the initial stop, our task is to predict the times of arrival to the following stops on its path. For simplification we have chosen three lines (parts of the lines, respectively) with different characteristics. We also chose for each line one initial stop a and one target stop b instead of predicting arrivals to all remaining stops on the line. The line parts we have chosen as the test subjects are described in the following paragraphs.
Line 9b in the selected part is completely segregated from the individual transport and there are no traffic lights on its track. Therefore it is rarely delayed and if so, the drivers are usually capable of decreasing the delay on the way (see figure 1).
Line 22a in the selected part has some intersections equipped with traffic lights on its way. This makes the vehicle movement more unpredictable, but does not cause major delays.
Line 22b in the selected part is not segregated from individual transport and sometimes it suffers from recurrent and non-recurrent congestions much more than the previous two lines.
For all the three lines, the travel time from the stop a to the stop b is approx. 12–15 minutes.
We used three methods of prediction on these lines in Matlab. Simple statistical method, neural networks and regression.
In the following sections we use this notation: L: The learning set of past observations on a particular line. An observation is a set of times and delays for each stop on the line. An observation corresponds to a single connection performed by a tram vehicle in the past. a: The initial stop. b: The target stop.
D(c, s): The delay of a specific tram connection c at the stop s.
D+(c, a, b): The additional delay of a specific tram connection c between stops a and b. This value is equal to D(c, b) − D(c, a). 4.1
The most straightforward solution is to calculate the average additional delay D+(a, b) between stops a and b in the following way:
D+(a, b) := 1
∑ D+(c, a, b) |L| c∈L (1)
Now in the present situation we have a vehicle v currently located at the stop a, Therefore we know D(v, a). We want to predict D(v, b). In the following formula, let De(v, b) be the prediction of D(v, b).
De(v, b) := D(v, a) + D+(a, b)
Since we use the current delay to predict the future
delay, this is a dynamic prediction algorithm. We can
compare it with a static version, which corresponds to the
approach provided by Martínek and Žemlicˇka in [
De(b) := 1
∑ D(c, b) |L| c∈L (2) (3)
In the formula above we use average delay at the target stop instead of the average additional delay. Note that since this is a static calculation, it does not depend on the concrete vehicle v. Finally, we compare the static and dynamic calculations using our dataset. The table 1 shows the average absolute errors for both static and dynamic prediction algorithms.
Clustering Similarly as in [
9b 22a 22b
64.8 s 90.8 s 170.5 s
62.6 s 90.5 s 150.1 s
37.1 s 51.2 s 113.7 s
32.5 s 47.0 s 97.2 s
Neural networks are commonly used in transportation
research (see [
We learned the neural networks on the past data using
the Levenberg-Marquardt method with 10 neurons in one
hidden layer, which showed the best performance and
accuracy in our tests. More information about structure and
learning process of the neural networks can be found in
literature [
For each past connection observation from the learning set c ∈ L we created an input vector. The input vectors consisted of the time, day of week and delays at each stop from the starting point of the line to the initial stop a. The network had only one output value - the prediction of the delay at the stop b1. The first results are shown in the table 2.
Average absolute error Median absolute error Mean percentage error As the results are very similar to those provided by the simple statistical methods (see table 1), we decided to make some improvements to the neural network. Input When changing the structure of the input vectors, we found that the network does not use delays from the previous stations before the station a. Additionally, the weekday information could be simplified to a boolean value “is-workday”.
As a result, only three-element vectors were used as the input: The time, workday boolean, and the delay at the stop a, while the results did not change.
Topology We have tested many different topologies of the network. It turns out that a neural network with approx. 10 neurons in one hidden layer is sufficient. In rare cases the neural network failed to learn, which can be improved by adding one more layer. Adding more neurons and layers only slowed down the learning process, but did not improve the results. Changing the learning method did not bring any improvements as well.
Clustering Similarly as in statistical methods we tried to
divide the data, at first only into two groups - workday and
weekends. Then we learned two neural network models
and for each input we used the appropriate model. We
found that this approach only worsens the previous results.
Later, we found that Jeong and Rillet in [
Current situation Until now we used only data about the particular connection when constructing a single input 1Actually, the output could be easily widened to produce one prediction value for each stop; we use only one-dimensional output for clarity. vector. The neural network treats the input vectors independently and therefore when it is asked for an output, it can use only the data specified in the input vector. That means the network did not use any other information, for instance about status of the previous vehicles on the same line.
However, we would like the network to use more information about current situation. In order to do that we need to extend the input vector and encode the information into it.
We have decided that we try to improve the results by adding information about a few previous vehicles on the same line. Question is, how to express this information in a form of a vector that a neural network would be able to understand. The fact that we do not know the exact positions of the trams, but only the last served stop, also needs to be taken into account.
Given the limitations above we extended the input vector by two values: number of trams of the given line currently located between stops a and b, and travel time from a to b of the last tram on the given line that has reached the stop b. This improved the results for line 22b by approx. 25 %, but did not bring any significant changes of the results for lines 9b and 22a. Table 3 shows how the absolute prediction error has changed.
Average absolute error Median absolute error Mean percentage error
9b 32.7 s 26.1 s 5.91 % 22a 45.8 s 37.0 s 8.76 % 22b 72.6 s 49.1 s 11.41 %
We explain these results by the differences between the lines. As the lines 9b and 22a are not directly influenced by other types of transport, their delays are more random. On the contrary, the line 22b is highly influenced by current traffic situation in the area, which usually does not dramatically change within just a few minutes. Therefore if a tram on the line 22b is delayed, it is probably caused by the traffic congestions and it is also probable that the next tram on this line will be delayed too.
Further improvements The input vectors now contain more information about current situation, yet the data presented are still very limited. The network uses the information about the last tram that has passed the stop b. This might still not be optimal.
If the distance between stops a and b is for example 15 minutes, we use information about a tram which is 15 minutes ahead. And this 15 minutes is a time long enough for the situation to change and therefore the prediction may be based on obsolete information.
Moreover, as the trams send their location to the system only at stops, this can cause problems in case of an accident. If a tram is extremely delayed or stopped on its way, we are not informed about that. The only way how to assume this is by the fact that the tram has not arrived to the stop b for a long time. This, again, slows the reaction of the network, since it takes some time before a tram becomes late enough to be suspicious.
What could improve the results is the knowledge of the exact position of the tram in real-time (or in reasonable intervals). But given the nature of the system used in Prague this is rather unrealistic.
The only option left is a better usage of the data presented. For instance the input vector could contain information about delays of trams at stops between a and b, which it does not now. Or it could contain information about trams from other lines that share a part of their path with the current line. Nevertheless, it is necessary to present the values in such way that the neural network will be able to interpret the data. We believe there may be a chance of further improvements regarding to this matter, though we were not able to devise an input form that would prove that. 4.3
The similarities between the results of statistical processing and neural networks encouraged us to try one more method – regression. Regression should provide better results than simple statistics, which in some cases gave as good results as the neural networks.
Inspired by the input of the neural networks, we used the following linear equation for the regression: D(v, b) = k1T (v) + k2W (v) + k3D(v, a) + k4NP + k5D(w, b) + k6 where: D(v, b) is the delay of the vehicle in the target stop, T (v) is the time of departure of the vehicle, W (v) is 1 for workdays, or 0 for weekends, D(v, a) is the delay of the vehicle in the initial stop, NP is the number of vehicles on the same line currently located between stops a and b, D(w, b) is the delay of the last vehicle on the same line that has passed the stop b, ki are coefficients we want to solve by the regression.
Note that the inputs to this equation are the same we used for the neural networks in section 4.2.
The results are summarized in the following table:
Average absolute error Median absolute error Mean percentage error
9b 32.0 s 25.6 s 5.76 % 22a 48.0 s 38.2 s 9.11 % Similarly as we did with the previous methods we tried to apply some improvements. First, adding higher degrees of the time and delay input variables did not change results significantly. Neither did clustering of the results. It may be possible that there is some combination of the input variables that could lead to better results, but we believe it is unlikely. 5
In this section we would like to compare the results from the previous sections. 5.1
First we compare the used methods. The table 5 shows the final results.
9b 22a 22b 32.5 s 47.0 s 97.2 s 29.8 s 45.6 s 72.6 s 32.0 s 48.0 s 73.9 s
The results indicate that on lines 9b and 22a all the methods present similar predictions. We think that this is caused by relatively good punctuality rate of these two lines. Average delay of the line 9b at the target stop is 38 seconds, for the line 22a it’s 94 seconds. The average delay for the line 22a is higher, but the delays on this line are probably caused mostly by the three intersections equipped with traffic lights, which generate unpredictable deviations. Together they can hold a tram for approx. 180 seconds in the worst case.
The results on lines 9b and 22a suggest that in the traffic network where there are only small delays, or the delays are caused mostly by unpredictable factors, simple statistical methods are most suitable. Implementation of linear regression or even neural networks is far more complex and most probably does not bring any improvements in these situations.
Regarding the line 23b, neural networks, together with linear regression outperformed the statistical prediction. This is mostly given by the fact that the statistical methods we used were not able to process many-dimensional input. The neural networks and regression have become more precise by adding information about previous vehicles to the input, which we cannot as simply add to statistical methods too. Before we added this data to the input of the neural networks and regression, the results were similar for the line 23b too.
The results show no significant difference between the precision of neural networks and linear regression. This is a little surprising as we expected the neural networks to be capable of discovering more complex non-linear relationships between the input and output data. 5.2
In this article we also wanted to compare the static and dynamic methods. It is clear that the dynamic methods should provide more accurate predictions; the purpose of this comparison is more to express the improvement that the dynamic prediction methods can offer.
To simulate the static environment we used the same methods: statistics, neural networks, and regression. The only difference is that static methods do not know the actual timetable deviations and therefore do not have the D(v, a) value on the input. The result is that the static methods must predict the delay D(v, b) using only the time and the day of week (based on the past observations).
First we compared the static versions of the used methods to each other. The result is that in the static environment all the three methods give almost the same results.
Then we compared the static and dynamic methods. The table 6 compares the best static method with the best dynamic method results.
Dyn Stat Dyn
The results that the algorithms present could be used in public transport information systems. The simplest usage of the data is a direct presentation of the results to passengers via mobile phones or information systems at stops. These systems already exist in many cities, they normally list departures from a particular stop, ordered by the departure time. These systems typically show only static timetable data, sometimes together with current delays.
But the passengers are not actually interested in the current delay; the information is provided to them so that they can infer the real departure time, which is inherently predicted as the timetable departure + the delay. However, we could provide the users with the predicted departure, which should be more accurate.
We decided to compare those values. In the table 7, “Inherent prediction” is a simple algorithm that always predicts the future delay as the same value, as the current delay - formally De(v, b) := D(v, a). In fact, this is the simplest possible dynamic prediction algorithm. For reference we also added “No prediction” algorithm which simply uses the value from timetable and assumes zero delay. This represents the simplest possible static prediction algorithm.
The numbers show that using the prediction algorithms, we can reduce the departure prediction errors. With usage of more advanced methods like neural networks or regression, the improvement can be even greater. The prediction data can be also used in public transport connection search engines. These applications typically search only in timetables and do not reflect current situation. If the systems used predicted departures and arrivals, they could possibly be able to find faster and more reliable connections. Especially when the user is searching for the fastest connection “right now”, we could use the benefits of the dynamic predictions.
The most complex systems are public transport
navigation systems. These applications are often capable of
dealing with delays at least in a simple way. Such a system was
already implemented in Boston [
We have shown that by using even simple prediction algorithms, it is possible to predict movement of the public transportation vehicles much more precisely than just by using the timetables given by the transit operator. It also turned out that for lines with only small or unpredictable delays, more complex methods like regression or neural networks are not more accurate than the basic statistical methods. Therefore, usage of regression or neural networks is reasonable only in environments with significant delays. As the neural networks are more complex, and most probably harder to implement, linear regression seems to be a good solution.
We also compared static and dynamic algorithms. The results indicate that when we have information about current situations, the predictions are up to twice as much accurate. Of course the results of the dynamic algorithms are valid only for a short period of time, as the situation changes. 7.1
From the data we have available it turned out that trams in Prague are quite precise, with only a few exceptions. We believe this is the major cause of why the more complex prediction methods did not outperform the simple ones greatly. We think it would be interesting to test the algorithms on a network with more significant deviations too, for example on the Prague bus operation data, as the buses tend to be less precise because of lower level of segregation from individual transport. However, we do not have access to this data, so we could not test it.
We would also like to focus on further improvements in accuracy. We believe that the neural networks and maybe the regression too, have potential to give better results if they had more information on the input. The problem is how to encode all the information about the current situation into a vector of real values of a reasonable length.
In the future work we would also like to focus on the usage of the data from the prediction algorithms. We believe that presentation of this data to passengers in a userfriendly form is a relatively simple yet modern way how to make public transportation more attractive.
This work was supported by project GAUK 472313.