BusTr: Predicting Bus Travel Times from Real-Time Traffic

We present BusTr, a real-time delay forecasting system for public buses, which is used by Google Maps to expand the availability of real-time data for transit users around the world [9].

Public transit systems are vital to human mobility in our rapidly urbanizing world. World-wide, transit is the most common mode for trips after walking [1]. Public transit investments and availability continue to grow, driven especially by the many societal benefits of public transit over private transportation, from reduced congestion [2], to environmental impacts [36, 17, 24], to social impacts [26, 7].

A modern global-scale mapping and navigation service thus needs to serve the needs of transit users. What are these needs? Broadly, a transit user wants to know (1) what the transit system is supposed to do: the system’s routes, stops, and schedules, and (2) what the transit system is doing right now: the current locations and delays of the transit trips, which often deviate significantly from published schedules [40]. Of these two modalities, the real-time state is disproportionately important for the routine trips that dominate most people’s transportation needs. Most transit users know by heart the routes connecting their home, work, and other frequent destinations, but they have a well-established need for information about real-time changes. Transit variability is a source of rider anxiety and a barrier to increasing ridership [4, 34, 10, 5, 42, 39], and users place significant value on commute time reliability [21].

Google Maps and other public transit apps are typically built on transit data distributed via the GTFS protocol [13] for static data, and its GTFS-Realtime extension [12] for real-time tracking of public transit vehicle locations and delays. Ideally, every public transit agency would instrument its vehicles with networked real-time tracking hardware and provide a fresh, precise, and open feed of the location data. Anecdotally, many agencies are interested in such a system, but, as of 2020, the vast majority of the world’s GTFS feeds with static transit data do not yet come with a matching real-time feed, due to a variety of operational constraints on the transit agencies’ capabilities. Furthermore, even if an agency is able to reliably maintain tracking devices on its entire vehicle fleet, generating a useful real-time transit data feed requires live labeling of vehicles with transit metadata (via algorithmic approaches [25], integration with dispatching solutions, or labor-intensive operator input). Any given agency can certainly overcome these barriers with a sufficient investment of capital and operating expenses, but here we aim for a solution to meet the needs of a global-scale transit tracking product.

An alternative to agency-driven solutions is to crowd-source the real-time location of transit vehicles [33], but this is infeasible to do with global-scale coverage while still fully protecting user privacy: plenty of transit trips will have too few users providing vehicle location data. Other crowd-sensing options hinge on activity recognition on mobile devices: inferring from a device’s sensors what type of vehicle it’s being transported on in real time. Distinguishing buses from other road vehicles via on-device sensors with usably high quality remains an open research question [14].

There is some existing literature on predicting bus travel times based on road traffic speeds, either measured using inductive loop detectors or inferred from bus speeds. We review some of this work here, then conclude by highlighting the differences between this work and our own.

Salvo et al. [29] compare the performance of a multilayer perceptron (MLP) and a radial basis function (RBF) network in predicting the average speed of a bus over a segment of road. They find that the RBF performs better, but come to this conclusion by training on a very small dataset (112 points) drawn from a single bus line; generalization was tested by comparing against a second line. They break the bus’s route into several segments and, for each, generate several features: traffic flow and capacity, whether or not there is a reserved bus lane, number of intersections with and without traffic lights, number of bus stops, whether there is illegal parking or free parking present, the number of inlets and outlets to the segment, the number of pedestrian crossings, and whether or not “commercial activities” are present. Details on the final network structure are omitted. The paper does not describe how traffic data was measured, only that it was provided by the Public Transport Company of Palermo. On unseen data, their RBF had a MAPE of 9% and their MLP had a MAPE of 34%.

Mazloumi et al. [22] note that while previous approaches focus on predicting average bus travel times, the variability in travel time is often neglected. Accordingly, they train two fully-connected neural networks—one to predict average time and the other its variance—each with a single hidden layer on an 1,800 point dataset for a four segment (five stop) route. Traffic variance is assumed to be normal about the mean, though they note that there can be long tails in delays. Training features include: traffic speed within each segment, measured using inductive loop detectors and averaged over a variable time window; schedule adherence (delay relative to the timetable); and temporal variables (day of week, time of day, month of year). They find that weather does not influence their predictive accuracy, possibly due to the lower number of training examples, so they omit this from their model. A neural network with a single hidden layer is used. After training networks of various sizes with Bayesian regularization, networks with 2–3 nodes turn out to provide the best accuracy. They find that traffic information adds little additional value beyond temporal variables alone.

Sun et al. [31] predict arrival times at various bus stops by calculating the delay versus a scheduled time. They distinguish between cases where the predicted time of arrival is in the near versus far future. Far future delays are found by dividing the data into seven groups by day of week, then within each group using k-means to cluster delay data according to the delay and the time of day to produce between 2 and 5 clusters. For arrival times in the near future, a two-stage Kalman filter is used. The first stage uses the bus’s reported location to develop an estimate of its true position. The second stage uses the position to estimate the delay of the bus on its current segment. While the first stage of the filter is updated on a per-bus basis, the second stage updates each segment using information from possibly many buses whose routes overlap. Information is drawn from GTFS static and real-time data as well as historical bus timing data; using traffic flow is listed as future work. The model was deployed in Nashville, TN, USA and reduced hour-ahead arrival prediction errors by an average of 25% and 15-minute errors by 47%.

Julio et al. [19] compare the performance of multi-layer perceptrons, SVMs, and Bayes Nets on predicting bus travel speeds from traffic conditions (the bus’s real-time location is used as a proxy for traffic), finding that MLPs performed best. To do so, they discretize each bus’s trajectory into a space-time grid where each cell represents about 400 m distance and 15–30 minutes of time. It is unclear whether these cells aggregate statistics from multiple bus lines or only multiple buses on a single line. From this information they extract eight potential features: real-time and historic speeds for the incoming, current, and outgoing cell over the previous ten minutes, historical speeds for the current cell at the moment to be predicted, and a binary variable indicating whether the cell contains a bus-only lane. Forward selection narrows the features to only the real-time speeds of the downstream and current cell, as well as the historic speed of the current cell. This information was fed to an MLP with two hidden layers of size 6 and 5 (structure obtained via trial-and-error). Predictive accuracy declined for times with high congestion, so k-means was used to multiplex models across possible traffic conditions. MAPE ranged from 14–22%.

Dhivyabharathi et al. [8] use real-time bus location information as a proxy for traffic with the aim of predicting travel times over each segment of a trip. They note that their data has a log-normal distribution and build two predictors around this: a seasonal AR model with possibly non-stationary effects and a linear non-stationary AR model. The seasonal model performs better with a MAPE of 17–19%, as tested on a single bus route. They compare this against an MLP of unspecified structure, trained on the travel times of recent trips through a segment, with a MAPE of 20–24% on the same route. Notably, the MLP has less feature diversity than in other works and is trained with Levenberg–Marquardt back propagation rather than the Bayesian regularization approach preferred by other authors.

Jeong and Rilett [18] and Zheng et al. [43] also use bus location traces as a proxy for traffic data when modelling bus travel times.

The DeepTTE system presented in Wang et al. [38] predicts transit times between locations. Their deep neural model first converts raw latitude-longitude pairs from GPS trackers to 16-dimensional vectors. A convolution is run across each time series and the results concatenated with embedded metadata features (such as the day of the week and the weather). This is then passed through a two-high stacked LSTM. Two things now happen. (1) The LSTM time series outputs are passed through densely connected layers to give per-segment timing predictions. (2) The LSTM time series outputs are combined with the metadata again in an attention layer. The result is again concatenated and passed through a series of residual fully-connected layers to give a prediction for the travel time across all segments. The per-segment and overall predictions are jointly used to train the model for which they report a MAPE of 11.89% in Chengdu and 10.92% in Beijing. In Sec. 6.2 we use this model as a baseline for its state-of-the-art performance and its deep network structure, comparably modern to BusTr.

Including the broader literature of predicting bus arrival times, non-neural methods are the dominant approach and perform well [27], but shallow perceptrons of only 1–3 layers show similar or better performance while potentially providing superior generalization versus deeper nets [6, 22]. Despite this, more recent work has shown good performance with deep nets [35, 15], recurrent nets [16], and attention (MAPE 14.8%) [32]. Several authors have found it advantageous to cluster historical travel information and use this as part of a multiplexed prediction approach [19, 41, 31]. This may offer advantages over MLPs because MLPs may have difficulty accounting for disruptions or out-of-band events [27]. Reich et al. [27] note that the lack of standard benchmarks and open source code make inter-comparison difficult.

Our approach differs from previous work in several key respects. (a) Our model is developed with generalization in mind. Our model should provide reasonable estimates of traffic-bus relations both for new routes in cities for which we have training data, as well as for cities in which we have no training data. The existing literature (with the exception of [29]) focuses on improving predictions for known bus routes without regard to generalization. (b) Our model uses a restricted feature set. Salvo et al. [29] notes that features noting “bus only” lanes, commercial activities, and illegal parking all add significant predictive power to their model; however, acquiring such information globally is difficult. Instead, the spatial elements of our model allow it to infer the existence of these features when they are present by learning both local and regional characteristics of the space a bus route passes through. (c) Our model is trained with a much larger amount of data. While previous authors have performed their analysis around single bus routes, we consider our model’s performance on a planet-scale dataset. This allows us to avoid having to incorporate strong priors such as log-normality [8]. (d) Our model makes inferences from real-time traffic data. Previous work used real-time bus locations as a proxy for traffic information, thus limiting generalization, or traffic loop sensors, which are sparse and usually confined to major roadways.

To forecast a travel time, BusTr needs two points on a bus route to delimit the trip; road traffic speed info for the relevant streets and times; and contextual data for the trip: the identity of the bus route, the roads involved, and time-of-week.

At training time, we need golden data: a clean, validated, integrated dataset with durations of specific bus trip segments, aligned with road traffic speeds at the relevant time. Here, we focus on training on data provided by GTFS-Realtime feeds via “Vehicle Position” reports, which specify the live locations of transit vehicles. Inference in this setting can actually add a delay forecast to a fresh Vehicle Position to provide an absolute ETA estimate, but this is not our primary focus. Instead, we aim to build and evaluate a model that can estimate delays for bus lines where there is no GTFS-realtime data, just a sporadic flow of offline observations of bus timings from a variety of sources, which will likely not have full coverage of bus lines, roads, and/or timings, and may also substantially vary in frequency, regularity, and precision of bus location observations.

To work in such a setting, we first represent our input data as training examples that are just pairs of timed trip endpoints, without finer-grained information on the timing at points in-between. Similarly to text mining, we shingle an input trajectory, here a sequence of GTFS-RT vehicle positions, into possibly-overlapping examples with several heuristic constraints:

• •

  We avoid shingle endpoints at or near stops. Although user queries will typically pertain to bus delays between pairs of stops, there is extra uncertainty inherent in a vehicle position reported at a stop: we cannot tell whether the bus just arrived at the stop or is just departing. These two states represent a noticeable difference in a bus’s progress through a trip. Since vehicle positions may be reported imprecisely, we also exclude reports that are near to a stop. Instead, we use vehicle positions reported at other points along the bus trip polyline, which various data sources including GTFS will often have.

• •

  For each input bus trajectory, we sample a minimum shingle length uniformly from $[1,5]$ km, and pick shingles of at least this length. This approximates a common range of user trip lengths, avoids shingles that are short enough that their observed duration is likely subsumed by noise in the endpoint location, and, by sampling from a wide range, forces the model to not overfit on typical shingle length.

• •

  The start times of shingles extracted from the same input trajectory are spaced at least 30 seconds apart, to limit data redundancy from very densely reported trajectories

• •

  We remove outlier shingles during which a gap between consecutive trajectory reports exceeded corpus-specific values ($5$ min or $3$ km). Shingles with unlikely reported average speeds (outside $[0.7,140]$ km/h) are also excluded.

Our shingling intentionally does not attempt to resample or interpolate between the points in raw location reports because we expect relevant bus motion to be non-uniform, especially when a pair of location reports spans a stop, a long red light, or a localized traffic snarl.

Shingling can confound simple protocols for holding out data, since adjacent shingles from one trajectory are not independent. In our experiments, we separate training, validation, and test sets by calendar weeks, using a separate 7-day span of data for each. This also gives us a way to measure generalization of the model as the world evolves over time, addressed further in Sec. 6.4.

Road traffic forecasts are obtained from Google Maps, on a per road segment basis. A single road segment is, roughly, a stretch of road between two adjacent turns. Since we train offline, we train using the traffic speed estimates that were available at the time the bus traversed a segment, estimated by the underlying road traffic system from the best available combination of aggregate real-time data and historical inferences. At inference time, the model can rely on the underlying system to provide forward forecasts of traffic per road segment, with the expectation that training on ”cleaner” data without forecasting errors will not bias the model.

The job of the model is to predict how long a bus will take to travel along a given interval of its route, based on traffic conditions and the current time.

The model separately predicts the time taken to traverse each road segment and service each stop, both denoted $t_{q}$ where $q$ is a road segment or stop. These predictions are summed to produce a prediction $\hat{T}$ of the total trip duration $T$ as the final output:

where $Q$ is the set of road segments and stops in the trip interval, and $\hat{t}_{q}$ is the model’s prediction of $t_{q}$.

We adopt per-shingle MAPE (mean absolute percentage error) as the target metric. A review of the ETA prediction literature [27] notes that inconsistencies in reporting standards prevent the inter-comparison of approaches. MAPE, they report, is the most common metric used by the studies reviewed (13 of 40 studies), and is thus our choice here, too.

Except where otherwise stated, all the experiments train a model 20 times and evaluate its performance on 100,000 examples sampled from the test data set. The test data comes from a week of calendar data that is not used during training or validation.

We show the mean and standard deviation of per-run test MAPEs. Statistical significance of improvements are evaluated with one-tailed t-tests, with the p-values shown.

We have described a new model, BusTr, for predicting how long it will take public transit buses to travel between points on their routes based on contextual features such as location and time as well as estimates of current traffic conditions. Our model demonstrates excellent generalization to test data that differs both spatially and temporally from the training examples we use, allowing our model to cope gracefully with the ever-changing world.

Our model outperforms not only simple predictors, but also DeepTTE, the previous state of the art. This is remarkable given the relative simplicity of our design. Our work shows that judicious feature selection and design choices, coupled with sufficient training data, can give superior results, in terms of both prediction accuracy and training cost, versus more complex designs.

Uncertainty regarding transit times for public transit buses is a barrier to increasing transit ridership; our work is another step in the direction of reducing this uncertainty.

The authors thank Cayden Meyer for directing us toward this problem space; Da-Cheng Juan for his ML modeling insights; and Neha Arora, Anthony Bertuca, Matt Deeds, Julian Gibbons, Reuben Kan, Ivan Kuznetsov, Oliver Lange, David Lattimore, Thierry Le Boulengé, Ramesh Nagarajan, Marc Nunkesser, Anatoli Plotnikov, Ivan Volosyuk, and the greater Google Transit and Road Traffic teams for support, helpful discussions, and assistance with bringing this system to the world at large. We are also indebted to our partner agencies for providing the GTFS transit data feeds the system is trained on.