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

arXiv: https://arxiv.org/abs/2505.11999 · HTML: https://mlsanity.com/paper/2505.11999/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 42 references that are in the map.
- First posted on arXiv 17 May 2025.

## Builds on (most cited first, 13 of 13)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [A Review of Relational Machine Learning for Knowledge Graphs](https://mlsanity.com/paper/1503.00759/) (2015)
- [Encoding Sentences with Graph Convolutional Networks for Semantic Role Labeling](https://mlsanity.com/paper/1703.04826/) (2017)
- [More Than Routing: Joint GPS and Route Modeling for Refine Trajectory Representation Learning](https://mlsanity.com/paper/2402.16915/) (2024)
- [How do you go where? Improving next location prediction by learning travel mode information using transformers](https://mlsanity.com/paper/2210.04095/) (2022)
- [DRL4Route: A Deep Reinforcement Learning Framework for Pick-up and Delivery Route Prediction](https://mlsanity.com/paper/2307.16246/) (2023)
- [End-to-End Prediction of Parcel Delivery Time with Deep Learning for Smart-City Applications](https://mlsanity.com/paper/2009.12197/) (2020)
- [Learning to Estimate Package Delivery Time in Mixed Imbalanced Delivery and Pickup Logistics Services](https://mlsanity.com/paper/2505.00375/) (2025)

## Built on by (most cited first, 4 of 4)

- [LocalSearchBench: Benchmarking Agentic Search in Real-World Local Life Services](https://mlsanity.com/paper/2512.07436/) (2025)
- [LocalGPT: Benchmarking and Advancing Large Language Models for Local Life Services in Meituan](https://mlsanity.com/paper/2506.02720/) (2025)
- [Open-Set Living Need Prediction with Large Language Models](https://mlsanity.com/paper/2506.02713/) (2025)
- [ORBITER: Conflict-Aware Decision-Making for Agentic Last-Mile Delivery](https://mlsanity.com/paper/2608.18846/) (2026)

## Abstract (arXiv)

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.