A Data-driven Route Segmentation Framework for Time-of-Arrival Estimation Service

Abstract

Estimated Time of Arrival (ETA) is a core service for ride-hailing, public transit, and map-based navigation platforms. While prior studies have extensively explored model architectures and learning algorithms, route segmentation remains largely underexplored. Predefined spatial markers in existing approaches often obscure fine-grained traffic variations by aggregating route data. Consequently, distinct local patterns are mapped to similar features, introducing ambiguity that limits ETA accuracy. Leveraging large-scale, fine-grained vehicle trajectories, we reformulate route segmentation as a function approximation problem. By projecting trajectories into a distance–time space, we model route-level traffic evolution as an underlying piecewise linear function, where segment boundaries correspond to stable traffic regimes. We propose RouteSeg, a dynamic programming–based segmentation algorithm that optimizes this formulation using uniformly sampled spatial points and a trajectory repair module to handle anomalous trajectories. Experiments on real-world datasets spanning multiple cities and millions of trajectories show that our method consistently outperforms ad-hoc and adapted state-of-the-art segmentation strategies. Moreover, online evaluation of our system on the Chelaile Bus ETA service across two cities demonstrates a 90% reduction in storage and a 25% decrease in CPU utilization while maintaining equivalent performance. These results support an anticipated nationwide deployment across over 460 cities, expected to reduce operational costs by approximately 5,000 USD per month.