DART: Navigating Last-Mile Heterogeneity in Instant Delivery via Distribution-Adaptive Splines

1 Introduction

The rapid expansion of the Online-to-Offline (O2O) economy has transformed on-demand delivery into a critical urban infrastructure, supporting the livelihoods of millions of gig workers [Dablanc et al., 2017]. In practice, to maximize operational efficiency, platforms typically employ a "batch dispatching" strategy, where a courier receives multiple concurrent orders and must plan a complex sequence of pickups and drop-offs within strict time windows [Wang, 2019]. In this high-concurrency workflow, Delivery Time Estimation

(DTE), a domain-specific specialization of TTE, acts as the central synchronization mechanism. It dictates not only the route planning but also the promised delivery time for each customer. Therefore, precise DTE is not merely an algorithmic metric; it is the fundamental guarantee for couriers to handle high workloads and secure their economic returns safely. This problem directly impacts labor fairness and the sustainability of the gig economy, highlighting its profound social importance.

Delivery Time Estimation is traditionally formulated as a regression problem on road networks, aiming to map trajectories to durations. While existing methods have achieved high accuracy in open outdoor environments by modeling traffic speeds and distances [Wu and Wu, 2019], the "last-mile" delivery in GNSS-denied environments-such as indoor shopping malls and dense commercial complexes-presents a fundamentally different challenge. As conceptually illustrated in Figure 1, different from outdoor scenarios where physical distance is a reliable proxy for time, delivery in these zones is governed by "invisible" stochastic events, such as waiting for elevators, security checks, or locating merchants in complex topologies [Yang et al., 2020]. Current industrial models often ignore these fine-grained environmental heterogeneities, applying uniform estimation standards. This creates a systemic "Fairness Gap": couriers who are willing to take on higher order counts suffer from disproportionate prediction errors. Consequently, they face severe, unmitigated overdue penalties for environmental complexities beyond their control, leading to algorithmic inequality [Ding et al., 2022].

Bridging this fairness gap to restore fair and efficient dispatching is non-trivial due to three critical challenges: i) Distributional Heterogeneity: High-load delivery data exhibits a heavy-tailed distribution driven by stochastic delivery scenarios [Zhu et al., 2020], making it difficult for standard regression models to fit outliers without sacrificing global accuracy [Liu et al., 2024b]; ii) Structural Heterogeneity: Complex delivery zones act as topological "blind zones" lacking physical maps [Guo et al., 2022], where existing models relying on Euclidean distance cannot perceive latent vertical traversal costs, despite recent advances in spatial pattern mining [Yuan et al., 2025; Wang et al., 2025]; iii) Contextual Uncertainty: Couriers engaged in high-concurrency delivery constantly switch between diverse contexts, leading to multipeak delivery time distributions that are hard to disentangle without explicit context signals, similar to dynamic preference shifts in sequential modeling [Qi et al., 2024].

In this paper, we propose a Distribution-Adaptive Robust Timing framework, called DART, to address the above challenges. DART explicitly models the heterogeneities in last-mile logistics through three innovations: i) A Learnable Adaptive Spline (LAS) encoder with gradient-driven knot migration to capture long-tail patterns; ii) A SpatioTemporal Transition Graph (STTG) to reconstruct latent building topologies from crowd-sourced sequences; and iii) A D-Gating Mechanism to adaptively switch prediction strategies based on transit contexts.

In summary, the key contributions of the paper are as follows:

• To the best of our knowledge, we are the first to identify and formulate the "Fairness Gap" in last-mile TTE within GNSS-denied environments. We shift the research focus from pursuing average accuracy to achieving distributional robustness, ensuring equitable performance for high-workload couriers.
• We design a Distribution-Adaptive Robust Timing framework called DART. Specifically, we devise a Learnable Adaptive Spline (LAS) encoder to automatically detect and focus on feature subspaces that trigger long-tail effects by dynamically increasing the knot density. We also develop a Spatio-Temporal Transition Graph (STTG) to reconstruct latent topologies and a DGating Mechanism to disentangle contextual uncertainties.
• Deployed in partnership with one of the largest Ondemand Food Delivery (OFD) platforms in China, which provided delivery data, partial delivery context features, and cloud infrastructure for large-scale A/B testing, we implement DART on a real-world on-demand platform and conduct extensive experiments based on 1.27 million trajectories and a large-scale Online A/B Test. The

evaluation results show that DART outperforms state-ofthe-art baselines by 14% in prediction accuracy. More importantly, it reduces the Order Overdue Rate by 1.7%, decreasing daily fines by approximately $24,000.

2 Motivation

2.1 ProblemFormulation

We consider a set of historical delivery orders D = {(xi, yi)}Ni=1 in GNSS-denied urban environments, where yi ∈ R+ is the ground-truth delivery time. The input xi is a composite feature vector derived from multi-source sensed sequences, including crowd-sourced Wi-Fi sensed arrival merchant time sequence Si and delivery specific attributes Ai [Ding et al., 2022]:

Given the heteroscedastic nature of urban delivery, we treat this as a conditional density estimation task. Our goal is to learn a probability density function P(y|x;Θ) that maximizes the likelihood of observed delivery time, rather than fitting a deterministic regressor.

Observations

Opportunity. We analyzed real-world delivery trajectories that have ground truth labels by Bluetooth beacon sensing (deployed only at specific partner merchants) to identify the roots of estimation bias (Fig. 2), revealing two phenomena distinguishing GNSS-denied environments from outdoor logistics.

The first is feature-dependent non-linear volatility. Fig. 2a shows that the standard deviation of the delivery time fluctuates violently with real-time features such as workload. This implies that high workload scenarios introduce exponentially growing non-linearities. Existing models, assuming uniform distributions, tend to overfit dominant "head" samples while sacrificing accuracy on challenging tail cases.

The second is the inefficacy of physical distance. Unlike outdoor scenarios, Fig. 2b reveals a deceptive correlation between Euclidean distance and time. However, separating samples by walk speed reveals that long-tail instances are not random noise but form distinct topological clusters. This points to a promising avenue: anomalies likely stem from systematic latent constraints (e.g., elevators); thus, by effectively decoupling these latent context distributions, it is possible to rectify distance distortion and achieve high-fidelity estimation.

Challenges. However, realizing this opportunity is nontrivial due to three obstacles rooted in data heterogeneity. Primarily, the task is impeded by distributional heterogeneity, where long-tail variance is latently correlated with specific feature combinations, causing traditional discriminative models to yield unreliable predictions for outliers. Furthermore, the environment exhibits significant structural heterogeneity; in GNSS-denied settings, Euclidean distance fails to characterize spatial dependencies, causing performance degradation in geometric-based GNNs and necessitating adaptive graph construction. Finally, the model must contend with contextual complexity, where diverse events are implicitly entangled. Without explicit supervision, capturing this multimodal distribution requires generative modeling capabilities that surpass standard regression approaches.

3 Design

The overall framework of DART is illustrated in Figure 3. To tackle the intrinsic heterogeneity in GNSS-denied delivery, DART operates in three distinct stages: (1) A LAS Encoder that mitigates distributional heterogeneity via gradientdriven spline knots; (2) A STTG module that captures topological constraints from inaccurate physical spatial relations; and (3) A D-Gating Mechanism that manages contextual uncertainty through adaptive expert routing.

3.1 Learnable Adaptive Spline (LAS) Encoder

Standard MLPs suffer from global interference, where updates for long-tail samples distort the manifold for normal data. We propose the LAS Encoder to decouple these patterns using spline-based local activations.

Spline-based Neural Transformation

As depicted in Figure 4, unlike rigid linear weights, LAS computes the activation of the j-th neuron at layer l as an aggregation of learnable B-spline functions ϕi,j(·). For an input vector x(l) ∈ Rdin , the transformation is defined as:

where Bk,d(·) denotes the k-th B-spline basis function of degree d. The learnable coefficients wi,j,k control the function's amplitude, while the adaptive knot vector ti,j dynamically adjusts the resolution density across the input domain.

Gradient-Driven Knot Migration

To robustly fit extreme outliers without sacrificing global stability, we employ a learnable knot mechanism. The gradients of the task loss L flow into knot positions via the chain rule:

This allows knots to migrate adaptively: concentrating in high-error tail regions to increase local plasticity while remaining sparse in normal regions to ensure smoothness. Upon convergence, the activation function becomes a shapeoptimized spline that provides dense support specifically for long-tail intervals identified by gradient descent.

Upon convergence, the knot vectors evolve from a uniform grid to a distribution-adapted constellation, denoted as T∗ = {t∗i,j }. Consequently, the final embedding zfeat captures the heterogeneous patterns through these spatially adaptive basis functions. The j-th dimension of the output is formalized as:

Here, the activation function ϕ(·; t∗i,j ) is no longer a static mapping but a shape-optimized spline that provides dense support specifically for long-tail intervals identified by the gradient descent.

Theoretical Guarantee: Local Plasticity

The mathematical foundations of spline-based networks, particularly their universal approximation capabilities and numerical stability, have been rigorously established in classical approximation theory [De Boor, 2001] and recent advances in spline-based networks [Liu et al., 2024a; Liu et al., 2024c]. Building upon these theoretical guarantees, we focus on the Local Lipschitz Continuity to explicitly quantify the robustness of our LAS Encoder against outliers.

Proposition 1 (Local Lipschitz Bound). For a cubic Bspline function ϕ(x), the local Lipschitz constant Lϕ over an interval [tj, tj+1) is bounded by:

This bound demonstrates that gradient updates from outliers are strictly confined to the local interval Ij, preventing catastrophic interference with the global representation.

3.2 Spatio-Temporal Transition Graph (STTG)

To capture topological constraints from inaccurate physical spatial relations, we design a dual-primal semantic graph GS = {VOD,ES} where nodes represent merchant pairs rather than static locations (see Figure 5).

We formulate the semantic structure of the dual-primal graph GS by defining node attributes and edge connectivity. First, regarding node attributes, we adopt Wi-Fi arrival detection technology [Guo et al., 2022] to accurately track the courier's status. Unlike static physical distance, we compute a dynamic semantic distance dWi-Fi by accumulating the horizontal and vertical displacements derived from the sequence of Wi-Fi fingerprints as follows:

This metric serves as a robust proxy for the actual traversal cost (e.g., incorporating vertical detours), effectively compensating for the limitations of Euclidean distance. Second, for edge construction, we define the adjacency matrix A to capture the latent connectivity between tasks. Instead of relying on physical proximity, we establish edges between merchant pairs that exhibit high temporal proximity. Specifically, we link pairs whose historical delivery time ¯ tOD are within a connectivity threshold derived from the global aver-

This ensures that the subsequent GAT aggregates features from tasks that are temporally correlated and share similar transit patterns.

Structure Propagation. We employ a multi-head Graph Attention Network (GAT) to encode these dependencies. Initial embeddings ei (comprising GPS and arrival time) are updated by aggregating semantic neighbors:

where αk ij denotes the attention coefficient for head k. This explicitly injects latent topological friction into the final representation zstruct.

3.3 D-GatingMechanism

The final stage explicitly addresses Contextual Uncertainty (e.g., waiting vs. transit contexts) by adaptively switching prediction strategies.

We first fuse the distributional features zfeat and structural context zstruct via Cross-Attention to obtain h. We then employ a Mixture of Gaussians output, where mixing coefficients πk are determined by a Gumbel-Softmax gating network:

Here, τ anneals from 1.0 to 0.1, enabling a transition from soft mixture learning to hard, interpretable mode selection.

The model is trained to maximize the likelihood of the ground truth y. To prevent mode collapse and ensure stability, we augment the Negative Log-Likelihood (NLL) with orthogonality and dispersion constraints.

4 Experiments

4.1 Experimental Setup

Datasets and Heterogeneity Analysis

We utilized a large-scale industrial dataset fromMeituan, one of the biggest OFD platforms in China, spanning four months (April-August 2023) across major Chinese cities (Beijing, Shanghai, Jiangsu). The dataset comprises 1.27 million orders, 20,000 active couriers, and ground truth collected via Bluetooth beacons. To rigorously evaluate DART under varying environmental heterogeneities, we partitioned the test data into four subsets of distinct complexity:

• D1 & D2 (High Complexity): Large-scale multi-story shopping malls with complex indoor topologies and high order density, representing the most challenging "longtail" scenarios.
• D3 (Data Scarce): Small-scale buildings with extreme data sparsity (0.7% of total volume), testing few-shot generalization.
• D4 (Medium Complexity): Semi-indoor pedestrian streets representing balanced complexity.

Implementation

To ensure data reliability, ground truth arrival times were captured via Bluetooth beacons at partner merchants, mitigating GPS drift and manual reporting errors. The dataset is partitioned chronologically: the first two months for training, followed by one month each for validation and testing. All baselines and U-STAR utilize identical splits for rigorous comparison. Offline training was conducted on an NVIDIA A100 GPU (PyTorch 1.13), while real-time performance was evaluated on a standard Meituan Cloud production node (Intel Xeon Gold 6240, single-core) to assess operational viability. Key hyperparameters include dmodel = 64, cubic B-splines (d = 3) with initial grid G = 15 for the DA-Spline Encoder, and K = 5 mixture components for ADisAM (τ annealed 1.0 to 0.1). Optimization employs Adam (LR = 1e - 4, Batch=64) with early stopping.

Baselines

We benchmark DART against 12 baselines across three categories. Note that foundation models (e.g., [Li et al., 2024; Wang et al., 2024]) are excluded as their high latency is incompatible with the millisecond-level constraints of real-time dispatching.

Industrial Heuristics & Statistical Models. We first establish performance lower bounds using fundamental non-learning approaches: AVG (historical averages) and GPS/Wi-Fi (physical sensing without semantic understanding). To evaluate signal processing limits, we include TransLoc [Yang et al., 2020], which utilizes HMM and Kalman Filtering for trajectory smoothing. Additionally, KDE-Reg combines kernel density estimation with regression to test whether DART's complex mixture density assumption yields significant gains over simple statistical fitting.

Spatio-Temporal Deep Learning. To assess the capability of capturing non-linear correlations and noise, we compare against EDCN [Chen et al., 2021] (temporal gating for sequence dependencies), P2Loc- [Ding et al., 2022] (modeling courier-merchant interactions), and MWSL-TTE [Wang et al., 2023] (weakly supervised learning for label noise). We also include the recent SOTA NAO [Guo et al., 2024], which optimizes dynamic noise distributions via MLE, serving as a direct competitor to our D-Gating mechanism in modeling aleatoric uncertainty.

State-of-the-Art Graph Models. Finally, we benchmark against frontier graph learning methods to validate our structural modeling. GSL-QR [Zhang et al., 2023] employs implicit graph structure learning with quantile regression, providing a contrast to our explicit STTG topology reconstruction. Furthermore, we compare DART with IGT [Zhou et al., 2023] (Inductive Graph Transformer), the current SOTA in structural modeling, to verify the superiority of our splinebased LAS encoder over Transformers in handling long-tail distribution heterogeneity.

Metric

In terms of metrics, beyond standard MAE and RMSE, we explicitly report Tail-MAE and Tail-RMSE calculated on the top 15% of samples with the longest travel times among identical Origin-Destination pairs. These metrics serve as a rigorous robustness check for structural anomalies and unexpected delays, distinguishing our approach from scenarios where conventional global thresholds are sufficient.

4.2 Overall Performance Comparison

Table 1 presents the comprehensive results across datasets with varying complexities, where DART consistently achieves superior performance. In high-complexity scenarios (D1 & D2), DART reduces MAE by 19.8% (in D1) compared to the state-of-the-art Graph Transformer (IGT). This validates that our LAS Encoder effectively captures highfrequency fluctuations in long-tail samples, overcoming the "oversmoothing" limitation of global attention mechanisms used in IGT. Furthermore, DART demonstrates robust fewshot generalization in data-scarce environments (D3). Compared to the Deep Learning baseline P2Loc-, DART reduces MAE by 21.3%, confirming that the STTG module successfully extracts transferable semantic topology rather than overfitting structural priors like standard sequence models. Finally, regarding multimodal uncertainty (D4), the D-Gating Mechanism enables DART to outperform deterministic baselines (e.g., P2Loc-) with a 7.5% reduction in RMSE. By explicitly disentangling latent delivery modes, DART prevents large deviations caused by unimodal assumptions. These significant improvements in accuracy, particularly in long-tail and data-scarce areas, provide a solid foundation for fair and efficient dispatching in real-world deployment, as detailed in the following section.

4.3 Online Deployment

To validate industrial feasibility, we first analyzed the computational cost (Figure 6). DART achieves a substantial reduction in the Overdue Rate across all datasets while maintaining an inference throughput (×103 samples/sec) comparable to a lightweight MLP baseline. This confirms that the local support property of B-splines ensures the high efficiency required for real-time dispatching.

We subsequently deployed DART in a large-scale Online A/B Test on the Meituan OFD platform, covering 16 major cities with a 50/50 traffic split. Over the course of one month, the model demonstrated a significant operational impact. The Overdue Rate decreased by 1.7%, effectively mitigating customer complaints and reducing penalties for couriers, thereby directly addressing labor fairness challenges. Furthermore, the improved accuracy optimized the dispatching "buffer time," yielding estimated operational savings of $24,000 per day. These metrics definitively validate the realworld business impact of our proposed method.

Finally, we examined the model's robustness against increasing consecutive order counts (Figure 7). While the baseline suffers from exponential growth in cumulative delivery MAE error (CMAE) under high concurrency, DART maintains a stable error curve even as the courier workload increases to 7 consecutive orders. This demonstrates DART's ability to capture the non-linear physics of congestion, ensuring reliability and stability when the system is under maximum stress.

4.4 In-depth Analysis

Unlike opaque deep learning black boxes, DART demonstrates clear interpretability in handling data heterogeneity.

Feature Level: Gradient-Driven Adaptation

We visualized the knot density distribution in Figure 8 to reveal the model's resource allocation strategy. Unlike the Fixed Grid baseline, which maintains a rigid uniform density, DART evolves into a distinct "U-shaped" distribution. It strategically reduces knot density in the data-rich central region, effectively identifying frequent patterns as "easy samples" that require less model capacity. These freed resources are then migrated to the sparse tail regions, where density is significantly amplified. This confirms that DART's topology adaptation is driven by task difficulty (gradients) rather than mere data quantity, allowing it to suppress error divergence in outlier regions without sacrificing performance in the dominant central distribution.

Mode Level: Hierarchical Functional Specialization

We further elucidated the latent structure learned by the DGating mechanism by analyzing Expert Selection Frequency against sample difficulty (Figure 9). The empirical distribution manifests an explicit hierarchical specialization. In the deterministic regime (low deviation, 0-3 min), Experts 2, 3, and 4 exhibit sequential dominance, indicating that the model has successfully disentangled the latent factors of predictable transit into orthogonal functional subspaces. Conversely, in the stochastic tail (> 5 min), the routing shifts towards Expert 5 with significantly higher entropy. This suggests that for extreme outliers, DART automatically adopts an ensemble-like approach to handle irreducible uncertainty, rather than relying on a single deterministic mapping.

Ablation Study

To quantify the contribution of each module, we evaluated variants of DART (Table 2).

• w/o LAS Encoder: Reverting to a standard MLP causes Tail RMSE to deteriorate by 29.4%, confirming that global activation functions fail to model heavy-tailed distributions.

• w/o STTG: Removing the graph module degrades Overall MAE by 29.1%, highlighting the necessity of modeling non-Euclidean semantic topology.
• w/o D-Gating: Using a single Gaussian head increases MAE by 58.9%, proving that capturing multimodal uncertainty is critical for accuracy.

5 RelatedWork

Spatio-Temporal Prediction and Uncertainty. Travel Time Estimation is fundamental to logistics efficiency [Lyu et al., 2023]. Modern approaches have evolved from simple sequence modeling to capturing complex latent patterns: STAMImputer [Wang et al., 2025] and STPro [Yuan et al., 2025] utilize attention mechanisms and hierarchical prototypes to address data sparsity and spatial heterogeneity, while Cuss-Ctpm [Qi et al., 2024] models continuous temporal dynamics. Despite these advances, real-world delivery faces significant stochasticity. Recent works, such as ST-nFBST [Liu et al., 2024b], introduce Bayesian significance testing to quantify uncertainty. However, existing methods suffer from two limitations in our context: 1) They predominantly rely on explicit road network graphs, which are unavailable in GNSSdenied environments; 2) They often assume unimodal distributions, failing to disentangle the multimodal conditional heteroskedasticity inherent in heavy-tailed delivery data.

Spline-basedNeural Networks. Kolmogorov-Arnold Networks (KANs) [Liu et al., 2024c] have emerged as interpretable alternatives to MLPs by parameterizing edges with learnable splines. While promising, current implementations rely on fixed grid points. This rigid discretization induces spectral bias [Rahaman et al., 2019], where the model captures low-frequency trends but underfits the high-frequency fluctuations of tail outliers. To address this, we propose a distribution-adaptive mechanism that dynamically allocates resolution to capture high-frequency details in the long tail.

6 Conclusion

In this work, we address the "Last-Mile Gap" in GNSSdenied logistics, where conventional models fail due to environmental complexity. We propose DART, a framework targeting distributional and structural heterogeneity. By synergizing the LAS Encoder and STTG, DART effectively captures long-tail outliers and latent topological constraints. Experiments on massive industrial datasets show that DART outperforms SOTA baselines by reducing MAE by 14.0%. Furthermore, online A/B testing confirms significant reductions in overdue rates and operational costs. Crucially, DART promotes algorithmic fairness by accurately identifying longtail delivery trip samples to mitigate unfair penalties, fostering a more equitable gig economy. Future work will focus on cross-region generalization.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant 62261042, the Beijing Natural Science Foundation under Grant 4232035 and 4254084, the Yibin high-level Introduction talents project under Grant 2024YG01 and the China Postdoctoral Science Foundation under Grant 2024M750200.