A Meta Heuristic Approach for Trajectory Segmentation of Moving Objects

Segmentation plays an important role in discovering knowledge from trajectory data of moving objects. The size as well as the input rate of trajectory data have been drastically increased as a result of extended capability of location-aware devices. Although the existing methods can meet the challenge to some extent utilizing heuristic methods, more effective methods are still needed. Considering the capabilities of genetic algorithm, in this paper we introduce the description of trajectory segmentation problem in the context of genetic algorithm. A segment of points is regarded as a chromosome while the points are considered as genes. We represent trajectory segmentation as an optimization problem and then introduce heuristic methods to solve it using genetic algorithm. The objective function is defined in the context of trajectory segmentation of moving objects where the proposed algorithms provide optimal solutions fulfilling the efficiency as well as the quality requirements in terms of a summarized (compact) trajectory representation. The results of experimental evaluations on the two data sets-Geolife and Hurricane - show that our proposed algorithms, SEGA, not only outperform existing baseline methods in terms of efficiency but they also result in a more summarized description of trajectories while keeping the quality of the segments.