=Paper=
{{Paper
|id=Vol-1392/paper-13
|storemode=property
|title=On Predicting Traveling Times in Scheduled Transportation (Extended Abstract)
|pdfUrl=https://ceur-ws.org/Vol-1392/paper-13.pdf
|volume=Vol-1392
|dblpUrl=https://dblp.org/rec/conf/icml/GalMSSW15
}}
==On Predicting Traveling Times in Scheduled Transportation (Extended Abstract)==
https://ceur-ws.org/Vol-1392/paper-13.pdf
On Predicting Traveling Times in Scheduled Transportation (Abstract)
Avigdor Gal AVIGAL @ IE . TECHNION . AC . IL
Avishai Mandelbaum AVIM @ IE . TECHNION . AC . IL
Francois Schnitzler FRANCOIS @ EE . TECHNION . AC . IL
Arik Senderovich SARIKS @ TX . TECHNION . AC . IL
Technion - Israel Institute of Technology, Haifa, Israel
Matthias Weidlich WEIDLIMA @ INFORMATIK . HU - BERLIN . DE
Humboldt-Universität zu Berlin, Berlin, Germany
Traveling time prediction queues. We propose a model that uses natural segmentation
of the data according to bus stops and a set of predictors,
Urban mobility impacts urban life to a great extent. People, some use learning while others are learning-free, to estimate
living in cities, plan their daily schedule around anticipated traveling time.
traffic patterns. Some wake-up early to “beat” rush hour.
Others stay at home and work during days when a conven- The model of journey segments. As the foundation of our
tion comes to town. approach, we propose to model each bus trip by using a
segmentation model as follows. A trip between two stops
To enhance urban mobility, much research was invested
consists of segments, with each segment being represented
in traveling time prediction, see (Wu et al., 2004). That
by a ‘start’ stop and an ‘end’ stop, see Figure 1. Given the
is, given an origin and destination, provide a passenger
first stop of a trip ω1 and the last stop of a trip ωn , the inter-
with an accurate estimation of how long a journey lasts. In
mediate stops are known in advance since each bus follows
particular, the ability to predict traveling time in scheduled
a predefined journey pattern. Therefore, a trip can be de-
transportation, e.g., buses, was shown to be feasible (Chien
scribed by segments that are characterized by a pair of stops
et al., 2002).
of the form hωi , ωi+1 i (Figure 1). This segmented model,
In this work, we address the problem of online travel time in turn, allows for fine-granular grounding of the prediction
prediction in the context of a bus journey. That is, a journey of traveling time T (hω1 , . . . , ωn i, tω1 ) for a sequence of
may be ongoing in the sense that journey events already stops hω1 , . . . , ωn i when departing at time tω1 : instead of
indicated the progress of the bus on its route. For such an considering only journeys that follow the same sequence of
ongoing journey, we are interested in the current prediction stops hω1 , . . . , ωn i, all journeys that share some segments
of the traveling time from the current bus stop to some des- can be used for prediction.
tination via a particular sequence of stops, which is defined
by the respective journey pattern.
Prediction Approach ʘͺϭ ʘͺŝ ʘͺŝнϭ ʘͺŶ
To address the problem of online travel time prediction, we
Figure 1. A segmented model of traveling times
investigate a novel use of methods from Queueing Theory
and Machine Learning in the prediction process. We pro- Using information on bus stops, the prediction of the journey
pose a prediction engine that, given a scheduled bus journey traveling time T (hω1 , . . . , ωn i, tω1 ) is traced back to the
(route) and a ‘source/destination’ pair, provides an estimate sum of traveling times per segment. The traveling time per
for the traveling time, while considering both historical data segment is assumed to be independent of a specific journey
and real-time streams of information that are transmitted by pattern and, thus, also independent of a specific journey:
buses. To do so, we model buses as clients that go through X
n−1
a journey of segments that are interpreted as a network of T (hω1 , . . . , ωn i, tω1 ) = T (hωi , ωi+1 i, tωi ),
i=1
where tωn−1 = tω1 + T (hω1 , ωn−1 i, tω1 ).
Proceedings of the 2 nd International Workshop on Mining Urban
Data, Lille, France, 2015. Copyright c 2015 for this paper by its Prediction based on the snapshot principle. A first set
authors. Copying permitted for private and academic purposes.
of predictors is grounded in heavy-traffic approximations
33
On Predicting Traveling Times in Scheduled Transportation
in Queueing Theory. It is non-learning, in the sense that it accuracy of the presented methods. The main results of our
does not generalize prediction from historical events, but experiments have been:
rather uses recent events to predict future traveling times.
• Prediction methods that combine the snapshot princi-
Applied to our context, the main idea is that a bus that passes
ple and Machine Learning techniques are superior in
through a segment, will experience the same traveling time
quality of prediction to both snapshot predictors and
as another bus that has just passed through that segment
Machine Learning methods (that do not include the
(not necessarily of the same type, line, etc). Following this
snapshot predictor).
line, we define a single-segment snapshot predictor, called
• The prediction error increases with the number of bus
Last-Bus-to-Travel-Segment (LBTS).
stops per journey. However, when considering the
To use this predictor to address the online travel time predic- relative error, it is stable for all trip lengths, i.e. the pre-
tion problem, it needs to be lifted to a network setting. To dictors do not deteriorate proportionally to the length
this end, we exploit the fact that the snapshot principle holds of the journey (in stops).
for networks of queues, when the routing through this net- • Surprisingly, the snapshot predictor does not deteri-
work is known in advance (Reiman & Simon, 1990). Clearly, orate for longer trips, therefore contradicting the hy-
in scheduled transportation, this is the case, so that we de- pothesis that the snapshot predictor would be more
fine a multi-segment (network) snapshot predictor, called precise for journeys with higher temporal proximity to
Last-Bus-to-Travel-Network. It is derived by summing up the current journey.
the LBTS predictions for the segments of the respective
journey pattern of the bus for which the prediction is made.
Conclusion
In this work, we presented a novel approach towards predict-
Prediction using Machine Learning methods. A second
ing travel time in urban public transportation. It is grounded
set of predictors comes from Machine Learning and is based
in a partitioning of the travel time into stop-based segments,
on regression trees. They exploit past journey logs to learn
and combines the use of Machine Learning and Queueing
a prediction model, and then use this model to make a
Theory predictors to model traveling time in each segment.
prediction on new instances of the problem, in our case,
Our empirical evaluations confirmed that the combination
traveling times as part of current journeys.
of methods indeed improves performance. Moreover, we
As a first step, we formalize the traveling times prediction observed that the snapshot predictor is, counter-intuitively,
problem as a regression problem. Features considered for unaffected by the length of a journey. This leads to positive
the regression include the travel time of the last bus that evidence in favor of applying mixed Queue and Machine
used that segment (LBTS, as introduced above); the interval Learning predictors in similar settings.
between the time the last bus left the segment and the esti-
This work was supported by the EU INSIGHT project (FP7-
mated time to enter the segment; the day of the week; and
ICT 318225).
the time of the day. For the resulting regression model, vari-
ous generic algorithms are applied to derive an ensemble of
regression trees that is then used to solve the prediction prob- References
lem. Specifically, random forests, extremely randomized Chien, Steven I-Jy, Ding, Yuqing, and Wei, Chienhung.
forests, AdaBoost, and gradient tree boosting are leveraged. Dynamic bus arrival time prediction with artificial neural
In a final step, the above methods originating from Queueing networks. Journal of Transportation Engineering, 128
Theory and Machine Learning are combined. That is, we (5):429–438, 2002.
rely on the boosting algorithms and modify them such that
Reiman, Martin I and Simon, Burton. A network of priority
the first model considered in the boosting is the snapshot
queues in heavy traffic: One bottleneck station. Queueing
predictor model.
Systems, 6(1):33–57, 1990.
Evaluation
Wu, Chun-Hsin, Ho, Jan-Ming, and Lee, Der-Tsai. Travel-
To demonstrate the value of our approach, we tested the time prediction with support vector regression. Intelligent
proposed predictors using bus data that comes from the bus Transportation Systems, IEEE Transactions on, 5(4):276–
network in the city of Dublin.1 The data includes location 281, 2004.
of buses that is sampled in intervals of 5 to 300 seconds,
depending on the current location of the bus.
Using this data, we empirically evaluated the prediction
1
See also http://www.dublinked.ie/ and http://
www.insight-ict.eu/
3N