I We introduce a HMM for future locations prediction that naturally sup-
ports imprecise data and eciently predicts both future locations (i.e., nal
destinations) and their corresponding trajectories (i.e., travel routes).
II A direct implementation of the HMM leads to unacceptable execution times
in a real-world application. We therefore present a rened version with loss-
less optimization and a faster one with approximate solutions.
III We conduct an experimental study on the models and compare them with
a state-of-the-art solution in simulated and real environments. For the syn-
thetic scenarios, we introduce a tool to generate routes for moving objects.
In the following, Section 2 discusses related work and Section 3 formally
introduces the problem. Sections 4 and 5 present our algorithm and its opti-
mization, respectively. Finally, Section 6 validates the proposed approach with
extensive experiments and Section 7 discusses future directions of research.