Abstract
Predicting the exact routes of food delivery couriers is a complex challenge involving spatial, temporal, and human factors. This paper introduces MRGRP (Multi-Relational Graph-based Route Prediction), a novel deep learning framework that models courier tasks as a multi-relational graph. By combining a "GraphFormer" architecture with a reference-guided decoder, MRGRP effectively captures multifaceted task relationships and narrows the routing search space. Deployed on Meituan, the model achieved a 31.85% reduction in route deviation during live production.
Introduction
In the high-pressure environment of instant food delivery, couriers often manage multiple orders simultaneously. For platforms like Meituan, predicting the sequence of pickups and deliveries is crucial for efficient dispatching and accurate Estimated Time of Arrival (ETA) calculations. However, this is a massive combinatorial problem. A courier's choice is driven by spatial proximity, temporal urgency, logical constraints (e.g., pickup must precede delivery), and personal preference. Traditional rule-based heuristics and standard machine learning models often fail to capture these dynamic, complex interactions.
The MRGRP Framework
MRGRP addresses these complexities through a specialized encoder-decoder architecture designed to handle relational data and dynamic environmental changes.
Multi-Relational Graph Modeling
Instead of a generic fully-connected graph, MRGRP constructs a fine-grained multi-relational graph. Nodes represent tasks (pickups or deliveries), while edges represent specific relationship types:
- Logical Constraints: Pickup-then-delivery requirements.
- Spatial Proximity: Physical distance between task locations.
- Temporal Proximity: Urgency based on delivery deadlines.
GraphFormer Encoder
To process this graph, the authors developed the GraphFormer module. It integrates Multi-Relational Graph Convolution (MRGC) layers with Transformer layers. The MRGC layers extract local structural features based on specific edge types, while the Transformers capture global, long-range interactions between all tasks. This dual approach ensures the model understands both immediate constraints and the overall route context.
Reference-Based Dynamic Decoder
Predicting a sequence from a vast search space is computationally expensive and prone to error. MRGRP simplifies this by using a fast heuristic algorithm (TSFH) to generate a "reference route." The neural decoder uses this reference as a guide, effectively pruning the search space.
Furthermore, the decoder performs dynamic context updates. At each step, it recalculates the courier's distance to remaining tasks and the time left until deadlines. An auxiliary task—predicting the ETA—is used during training to enhance the model's ability to learn these temporal features.
Experimental Evaluation
The model was rigorously tested using real-world datasets from Meituan, covering three major Chinese cities: Beijing, Chengdu, and Guiyang. The dataset comprised approximately 2.5 million samples, reflecting diverse urban layouts and development levels.
Key Results
- Offline Performance: MRGRP consistently outperformed state-of-the-art baselines like Graph2Route and FDNet. In Beijing, it improved Location Square Deviation (LSD) by 19.77% and the Same Rate (SR) of predicted sequences by 5.96%.
- Online Deployment: Following deployment on the Meituan Turing Platform, live A/B testing showed a 31.85% reduction in LSD and a 7.46% increase in SR compared to the platform's existing heuristic.
- Robustness: The framework proved effective for both simple short routes (<5 tasks) and complex long routes (≥5 tasks), showing significant LSD improvements in both scenarios.
Conclusion
MRGRP demonstrates the power of combining graph-based relational modeling with heuristic-guided deep learning. By explicitly separating different types of task relationships and dynamically updating environmental context, the framework provides a robust and scalable solution for real-world courier route prediction. Future work may involve integrating real-time environmental factors like weather and traffic to further refine predictions.
Summary updated