  Trip destination prediction is an area of increasing importance in many
applications such as trip planning, autonomous driving and electric vehicles.
Even though this problem could be naturally addressed in an online learning
paradigm where data is arriving in a sequential fashion, the majority of
research has rather considered the offline setting. In this paper, we present a
unified framework for trip destination prediction in an online setting, which
is suitable for both online training and online prediction. For this purpose,
we develop two clustering algorithms and integrate them within two online
prediction models for this problem.
  We investigate the different configurations of clustering algorithms and
prediction models on a real-world dataset. By using traditional clustering
metrics and accuracy, we demonstrate that both the clustering and the entire
framework yield consistent results compared to the offline setting. Finally, we
propose a novel regret metric for evaluating the entire online framework in
comparison to its offline counterpart. This metric makes it possible to relate
the source of erroneous predictions to either the clustering or the prediction
model. Using this metric, we show that the proposed methods converge to a
probability distribution resembling the true underlying distribution and enjoy
a lower regret than all of the baselines.
