Abstract
Accurate destination prediction is vital for Location-Based Services (LBS). Traditional models often rely on geometric path-matching or memory-less Markov chains, failing to capture the complex human behaviors driving movement. This paper introduces the Semantic Transfer and Time-Limited (STTL) algorithm. STTL integrates time-constrained trajectory clustering with a semantic transfer model that predicts destination categories based on starting point semantics. Evaluated on a real-world Shanghai taxi dataset, STTL demonstrates superior accuracy by incorporating temporal constraints and semantic intent, outperforming traditional approaches.
Introduction
Predicting a vehicle's destination from a partial trajectory is a foundational challenge in urban mobility and targeted advertising. Most existing solutions treat trajectories as simple geometric patterns. However, human movement is inherently structured by time and purpose. For instance, a trip at 8:00 AM from a residential area is likely bound for a workplace, whereas an evening trip might target a leisure spot. This paper addresses the gap between raw GPS data and underlying human intent by proposing the STTL algorithm, which leverages temporal properties and semantic transfer probabilities.
Methodology
The STTL algorithm is built upon three core components designed to model the "when" and "why" of urban travel.
Time-Constrained Similarity (ALCSS)
To filter historical data effectively, the model employs an Asymmetric Longest Common Subsequence (ALCSS) measure. This approach ensures that current trajectories are compared only with historical paths occurring within similar time windows (e.g., morning rush hour vs. late night), reducing noise from irrelevant patterns.
Enhanced Trajectory Clustering
Building on the DESTPRE framework, the authors group historical trajectories based on their completion ratio. By splitting journeys into early (0-50%) and late (50-100%) stages, the search space for potential destinations is refined, allowing for more precise matching as the trip progresses.
Semantic Transfer Probability Model
The primary innovation is the semantic layer. Using the Baidu Map API, GPS coordinates are mapped to a 21-dimensional "semantic vector" representing location types (e.g., food, finance, education). A transfer matrix calculates the probability of moving between these categories. The final destination is predicted by selecting the point within a cluster that best aligns with the predicted semantic intent.
Experimental Evaluation
The model was tested using a dataset of 4,000 Shanghai taxis over 24 hours. Raw GPS pings were segmented into distinct trips based on occupancy status to ensure data quality.
Key Results
The STTL model was compared against a Naive baseline and an E-cluster model. Results indicated that STTL consistently maintains a lower Average Minimum Error (AvgMinErr). The integration of semantic data proved particularly effective as a "tie-breaker" when geometric data alone was ambiguous. Sensitivity analysis identified a distance threshold ($\epsilon$) of 500 meters as optimal for trajectory matching.
Discussion and Conclusion
The STTL model demonstrates that incorporating semantic intent and temporal filters significantly enhances destination prediction. By treating urban movement as a series of semantic transitions rather than just coordinate sequences, the model achieves higher robustness.
However, limitations remain. The current model is "universal," assuming all users follow average urban patterns, which may overlook individual routines. Future work will explore incorporating anonymized user identities to personalize predictions while maintaining privacy. Additionally, the reliance on external map APIs for semantic data necessitates periodic retraining to account for urban development.
Summary updated