Route planning for locations based on trajectory segments
Jinsheng Jiang, Chong Xu, Jian Xu, Ming Xu, Ning Zheng, Kaiwei Kong · 2016
Route planning for a set of locations based on trajectory searching is a hot topic. To obtain previous drivers' knowledge on route selection, some existing works search trajectories which are spatially close to the query locations. However, these trajectories may be only close to partial query locations or go to other locations beyond the query location set, which lead the algorithm to a poor performance. In this paper, we study a new model called Route Planning for Locations Based on Trajectory Segment (RPBTS). Given a set of ordered query locations, in order to pass as close as to the query locations, we plan a route by combining some intersecting trajectory segments. A greedy algorithm is employed to retrieve the optimal combinations which doesn't contain the two undesirable conditions mentioned above. To enhance the performance of the algorithm, we construct a regional landmark graph, where a regional landmark is a road segment frequently traversed by drivers in a certain region. Based on this graph, it's very likely a query location can be converted to a regional landmark. Finally, we propose a Random Selection strategy to further improve the efficiency. The effectiveness of our method is verified by empirical study based on a real trajectory data set.