Deriving network-constrained trajectories from sporadic tracking points collected in location-based services

The paper proposes an economical and fast algorithm for deriving trajectories from sporadic tracking points collected in location-based services (LBS). Although many traffic studies or applications can benefit from the derived trajectories, the sporadic tracking points are always implicitly overlooked by most of existing map-matching algorithms. The algorithm proposed in this paper finds network paths or trajectories traveled by vehicles through augmenting GPS data with odometer data. An odometer can provide data of traveled distance which are compared with the lengths of candidate network paths in order to find the most approximate network path approaching the trajectory of a vehicle. Tracking points are classified into anchor points and non-anchor points. The former are used to divide trajectories, and the latter screen candidate network paths. An elliptic selection zone and a reduction process are applied to the selection of possible road segments composing candidate network paths. A brute-force searching algorithm is developed to find candidate network paths and calculate their lengths. A two-step screening process is designed to select the final result from candidate network paths. Finally, a series of experiments are conducted to validate the proposed algorithm.