Trajectory based Routing using Frequented Paths

Abstract

A McKinsey Digital report estimates that personal location data could help save consumers about $600 billion by 2020, by providing alternate routes to vehicles that avoid traffic congestion by using next-generation routing algorithms. The variety of spatial big data means that a single “One-size-fits-all” algorithm will not be able to answer all our queries. We would rather need a number of specialized algorithms that can work together to answer these questions. The Trajectory Based Routing problem aims to find the frequented path with the lowest cost between a given origin and destination. Cost estimation models that make use of trajectory data to estimate costs in a path-centric manner were recently introduced. However in the path selection phase these algorithms extended paths one edge at a time, in a “path + edge” fashion. In contrast in the path selection process, this work extends the paths in a “path + path” manner, speeding up the path selection process. To do this we make use of a new representation, “Maximal Frequented Path Graph(MFPG)”, that combines the spatial graph and trajectory data into one representation.We propose a path selection algorithm , “MFPG Shortest Path Algorithm” that makes use of this representation to find the lowest cost path. We also introduce an admissible heuristic that can be used in the MFPG if an admissible heuristic exists in the spatial graph. The “Informed MFPG Shortest Path Algorithm” makes use of this admissible heuristic to further speed up the algorithm, by guiding the search space towards the destination. We prove both experimentally and theoretically that the proposed method is complete and correct, and computationally faster than the related work.