MRGRP: Empowering Courier Route Prediction in Food Delivery Service with Multi-Relational Graph

Chang Liu, Huan Yan, Hongjie Sui, Haomin Wen, Yuan Yuan, Yuyang Han, Hongsen Liao, Xuetao Ding, Jinghua Hao, Yong Li

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.
The multi-relational graph structure explicitly models spatial, temporal, and logical dependencies between tasks.

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.

The complete MRGRP architecture, illustrating the flow from the GraphFormer encoder to the reference-guided decoder.

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

Abstract

Instant food delivery has become one of the most popular web services worldwide due to its convenience in daily life. A fundamental challenge is accurately predicting courier routes to optimize task dispatch and improve delivery efficiency. This enhances satisfaction for couriers and users and increases platform profitability. The current heuristic prediction method uses only limited human-selected task features and ignores couriers preferences, causing suboptimal results. Additionally, existing learning-based methods do not fully capture the diverse factors influencing courier decisions or the complex relationships among them. To address this, we propose a Multi-Relational Graph-based Route Prediction (MRGRP) method that models fine-grained correlations among tasks affecting courier decisions for accurate prediction. We encode spatial and temporal proximity, along with pickup-delivery relationships, into a multi-relational graph and design a GraphFormer architecture to capture these complex connections. We also introduce a route decoder that leverages courier information and dynamic distance and time contexts for prediction, using existing route solutions as references to improve outcomes. Experiments show our model achieves state-of-the-art route prediction on offline data from cities of various sizes. Deployed on the Meituan Turing platform, it surpasses the current heuristic algorithm, reaching a high route prediction accuracy of 0.819, essential for courier and user satisfaction in instant food delivery.
BibTeX
@inproceedings{liu2025mrgrp,
  author = {Chang Liu and Huan Yan and Hongjie Sui and Haomin Wen and Yuan Yuan and Yuyang Han and Hongsen Liao and Xuetao Ding and Jinghua Hao and Yong Li},
  title = {{MRGRP: Empowering Courier Route Prediction in Food Delivery Service with Multi-Relational Graph}},
  booktitle = {The Web Conference},
  year = {2025},
}
Figure