MixTTE: Multi-Level Mixture-of-Experts for Scalable and Adaptive Travel Time Estimation

AI summary

Overview

Research area: Spatio-temporal machine learning for urban transportation, specifically travel time estimation (TTE) on large-scale road networks, combining link-level graph modeling with industrial route-level systems.

Technical level: Advanced. The paper assumes familiarity with graph neural networks, attention mechanisms, mixture-of-experts routing, and incremental learning in production systems.

Scope: The paper proposes MixTTE, a framework that plugs link-level spatio-temporal modeling (spatio-temporal external attention, a stabilized graph mixture-of-experts, and asynchronous incremental learning) into DiDi's existing route-centric TTE system and reports offline experiments on three Chinese cities plus deployment experience.

What This Paper Is About

Ride-hailing platforms like DiDi answer billions of travel time queries per day, and their production systems predict the total duration of a whole route rather than modeling individual road links. This route-centric design misses broader city-scale traffic dynamics that spill into a route and underperforms on rare, long-tail situations such as event traffic or construction zones. MixTTE aims to add link-level awareness of traffic context to the existing route-centric model without refactoring the data pipeline or retraining the deployed system from scratch.

Key Contributions

1. A multi-level TTE framework. MixTTE synergistically integrates link-level and route-level model advances into DiDi's existing route-centric TTE system, requiring no refactoring of the data pipeline or route-centric model, so it can be plugged in seamlessly.

2. Spatio-temporal external attention (STEA). A module that uses a small set of external memory units to capture global spatio-temporal dependencies across million-scale road networks at linear cost, rather than the quadratic cost of pairwise link correlation modeling.

3. Externally stabilized graph mixture-of-experts (ESGMoE). A layer that handles heterogeneous, long-tailed traffic patterns through sparse expert activation, an entropy-based hierarchical routing gate guided by external knowledge, and zero-computation experts that amortize activations for common patterns.

4. Asynchronous incremental learning (ASIL). A strategy that detects distribution shifts via Mahalanobis distance statistics and selectively updates route-side and link-side parameters at different triggers, enabling real-time adaptation at sustainable cost, plus reported insights from real-world deployment.

Main Findings

• Overall accuracy: In the full retraining setting, MixTTE achieves up to 2.01%, 2.41%, and 8.81% relative improvements in MAE, MAPE, and BCR respectively over the second-best result. In the incremental learning setting, it achieves up to 2.39%, 3.70%, and 10.32% relative improvements over iETA.

• Absolute incremental-learning results: MixTTE reaches MAE 130.84 sec, MAPE 11.75%, BCR 5.25% in Beijing; MAE 75.26 sec, MAPE 10.14%, BCR 1.39% in Nanjing; and MAE 77.18 sec, MAPE 10.48%, BCR 1.36% in Suzhou.

• Long-tail generalization: Dividing Suzhou test queries into 5 groups by trip duration, en-route condition deviation degree, and en-route condition non-recurrence degree, the MAE gains of MixTTE over DiDi's current TTE model increase from head to tail samples across all three measurements.

• Baseline comparisons: Deep learning methods surpass the rule-based RouteETA baseline; link-centric baselines mostly underperform the industrial route-centric WDR system; integrating BigST outperforms WDR on MAPE and BCR in Beijing but does not uniformly beat WDR, indicating that integrating link-level modeling into a highly optimized route-centric system is non-trivial.

• Incremental learning helps, but iETA only marginally: IL methods consistently outperform full retraining methods, though iETA's improvement over WDR is marginal, which the authors attribute to iETA's lack of modularity in its IL strategy.

• Efficiency: MixTTE-WoIL consistently outperforms CompactETA and ConSTGAT across training throughput and inference latency in all three cities, and achieves comparable efficiency with BigST while possessing a larger model capacity. Reported inference latencies are 88.97 msec (Beijing), 30.45 msec (Nanjing), and 75.11 msec (Suzhou), with training throughputs of 21.17, 32.02, and 25.38 K/min respectively.

• Deployment: MixTTE has been deployed on DiDi's ride-hailing platform since April 2025, improving the accuracy and stability of the TTE service. Link representations are updated every 5 minutes and cached in a Redis server, while the route-centric model is re-implemented in C++ on distributed CPU servers.

• Not reported in the provided content: The efficiency comparison of MixTTE against the -WoPU variant in the incremental learning setting is cut off mid-sentence, so its results are not available here. The paper does not state absolute online A/B production metrics beyond qualitative statements of improvement.

Methodology in Plain English

The authors keep DiDi's existing route-centric model (a Wide-Deep-Recurrent architecture whose recurrent part has been upgraded to a Transformer) and add a link-level branch beside it. The link branch produces an enriched representation for each road link, which is concatenated with the original in-route link features and fed downstream to the route model.

To make this scalable, the link branch first encodes each link's recent traffic history and then retrieves knowledge from a small set of learned external memory units through cross-attention. Because the memory is much smaller than the number of links, each traffic slice indirectly interacts with all other slices in linear time rather than quadratic time. The authors also perform this retrieval at a semantic level after soft-clustering links into tokens, reinforcing same-time-step city-wide correlation.

To handle diverse and rare traffic patterns, the link branch uses a mixture-of-experts layer with a pool of graph experts and a sparse top-k gate. The gate blends two sources of routing logits: one from locally observed traffic context and one from the externally enhanced representation, with an adaptive weight derived from the entropy of the local routing distribution, so the router leans on external guidance when local information is ambiguous. Alongside the graph experts, three zero-computation experts (identity, constant, and null) absorb frequent, low-value patterns without consuming graph-expert capacity. A load balancing loss with type-dependent weights prevents expert collapse.

For adaptation, the model tracks per-link representation statistics over past weeks and computes a Mahalanobis distance for each link at update time. If the share of anomalous links exceeds one historical quantile, a link-side update is triggered; only if it exceeds a stricter quantile are route-side parameters also updated. Drift detection uses a frozen copy of the link model to keep the latent space consistent. Offline training uses time-specific batching, where each batch contains trips starting at the same time step, which stabilizes gradients and aligns with streaming inference.

Why This Matters

Impact on research. The paper shows a concrete path for combining scalable global attention, stabilized mixture-of-experts, and selective incremental learning in a single industrial spatio-temporal system. It also documents a negative result that matters: link-centric academic baselines did not uniformly beat a well-engineered production route-centric model, framing integration rather than replacement as the real problem.

Real-world applications:

• Route planning that reflects congestion propagating from nearby roads rather than only the queried route.
• Order dispatching, where small accuracy gains compound across billions of daily queries.
• Dynamic pricing that depends on reliable duration forecasts.
• Robustness in rare scenarios such as stadium events, construction zones, and unusual weather.

Industry relevance. The system was deployed at DiDi starting April 2025 and required no changes to the existing data pipeline. The reported offline training hardware (4 Intel Xeon E5-2630 v4 CPUs with 90 GB and 1 NVIDIA Tesla P40 GPU with 24 GB) and the asynchronous serving design and 5-minute representation caching are directly informative for teams operating similar latency- and throughput-constrained services.

Future Directions

1. Completing the incremental-learning efficiency comparison. The provided content cuts off during the comparison against a variant without parameter-selective updates, so the cost benefit of ASIL's selective updating remains unquantified here.

2. Tuning and generalizing the drift thresholds. The ASIL design depends on a link anomaly threshold, a link-update quantile, and a stricter route-update quantile, and the paper presents them as presets rather than studying their sensitivity across cities.

3. Extending the memory-unit design. The external memory units accumulate prototypical traffic patterns across the dataset; whether these memories transfer across cities or generalize to unseen cities is not addressed in the provided content.

4. Deploying more capable expert pools. The zero-computation experts exist to avoid overcapacity and undertraining as expert counts grow, raising the open question of how far the expert pool and top-k selection can be scaled before that tradeoff returns.

Target Audience

This paper is most valuable to industrial machine learning engineers and applied researchers working on large-scale spatio-temporal forecasting, ride-hailing or logistics platforms, and production model update pipelines. It also suits academic readers interested in mixture-of-experts stabilization, linear-complexity global attention, or incremental learning evaluated on real deployment data rather than only public benchmarks.

Authors’ abstract

Accurate Travel Time Estimation (TTE) is critical for ride-hailing platforms, where errors directly impact user experience and operational efficiency. While existing production systems excel at holistic route-level dependency modeling, they struggle to capture city-scale traffic dynamics and long-tail scenarios, leading to unreliable predictions in large urban networks. In this paper, we propose \model, a scalable and adaptive framework that synergistically integrates link-level modeling with industrial route-level TTE systems. Specifically, we propose a spatio-temporal external attention module to capture global traffic dynamic dependencies across million-scale road networks efficiently. Moreover, we construct a stabilized graph mixture-of-experts network to handle heterogeneous traffic patterns while maintaining inference efficiency. Furthermore, an asynchronous incremental learning strategy is tailored to enable real-time and stable adaptation to dynamic traffic distribution shifts. Experiments on real-world datasets validate MixTTE significantly reduces prediction errors compared to seven baselines. MixTTE has been deployed in DiDi, substantially improving the accuracy and stability of the TTE service.