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

• URL: http://arxiv.org/abs/2505.11999v1
• Date: Sat, 17 May 2025 13:19:34 GMT
• Title: MRGRP: Empowering Courier Route Prediction in Food Delivery Service with Multi-Relational Graph
• Authors: Chang Liu, Huan Yan, Hongjie Sui, Haomin Wen, Yuan Yuan, Yuyang Han, Hongsen Liao, Xuetao Ding, Jinghua Hao, Yong Li,
• Abstract summary: Instant food delivery has become one of the most popular web services worldwide due to its convenience in daily life.<n>A fundamental challenge is accurately predicting courier routes to optimize task dispatch and improve delivery efficiency.<n>We propose a Multi-Relational Graph-based Route Prediction (MRGRP) method that models fine-grained correlations among tasks affecting courier decisions for accurate prediction.
• Score: 13.815669295898136
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Generalizable Trajectory Prediction via Inverse Reinforcement Learning with Mamba-Graph Architecture [6.590896800137733]
  This paper presents a novel Inverse Reinforcement Learning framework that captures human-like decision-making.<n>The learned reward function is utilized to maximize the likelihood of output by the encoder-decoder architecture.
  arXiv  Detail & Related papers  (2025-06-14T12:18:19Z)
• SemanticFormer: Holistic and Semantic Traffic Scene Representation for Trajectory Prediction using Knowledge Graphs [3.733790302392792]
  Tray prediction in autonomous driving relies on accurate representation of all relevant contexts of the driving scene. We present SemanticFormer, an approach for predicting multimodal trajectories by reasoning over a traffic scene graph.
  arXiv  Detail & Related papers  (2024-04-30T09:11:04Z)
• Deep Prompt Tuning for Graph Transformers [55.2480439325792]
  Fine-tuning is resource-intensive and requires storing multiple copies of large models. We propose a novel approach called deep graph prompt tuning as an alternative to fine-tuning. By freezing the pre-trained parameters and only updating the added tokens, our approach reduces the number of free parameters and eliminates the need for multiple model copies.
  arXiv  Detail & Related papers  (2023-09-18T20:12:17Z)
• GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
  We propose an efficient shared encoding for all agents and the map without sacrificing accuracy or generalization. We leverage pair-wise relative positional encodings to represent geometric relationships between the agents and the map elements in a heterogeneous spatial graph. Our decoder is also viewpoint agnostic, predicting agent goals on the lane graph to enable diverse and context-aware multimodal prediction.
  arXiv  Detail & Related papers  (2022-11-04T16:10:50Z)
• SGCN:Sparse Graph Convolution Network for Pedestrian Trajectory Prediction [64.16212996247943]
  We present a Sparse Graph Convolution Network(SGCN) for pedestrian trajectory prediction. Specifically, the SGCN explicitly models the sparse directed interaction with a sparse directed spatial graph to capture adaptive interaction pedestrians. visualizations indicate that our method can capture adaptive interactions between pedestrians and their effective motion tendencies.
  arXiv  Detail & Related papers  (2021-04-04T03:17:42Z)
• Injecting Knowledge in Data-driven Vehicle Trajectory Predictors [82.91398970736391]
  Vehicle trajectory prediction tasks have been commonly tackled from two perspectives: knowledge-driven or data-driven. In this paper, we propose to learn a "Realistic Residual Block" (RRB) which effectively connects these two perspectives. Our proposed method outputs realistic predictions by confining the residual range and taking into account its uncertainty.
  arXiv  Detail & Related papers  (2021-03-08T16:03:09Z)
• LaneRCNN: Distributed Representations for Graph-Centric Motion Forecasting [104.8466438967385]
  LaneRCNN is a graph-centric motion forecasting model. We learn a local lane graph representation per actor to encode its past motions and the local map topology. We parameterize the output trajectories based on lane graphs, a more amenable prediction parameterization.
  arXiv  Detail & Related papers  (2021-01-17T11:54:49Z)
• Boosting Algorithms for Delivery Time Prediction in Transportation Logistics [2.147325264113341]
  We show that travel time prediction can help mitigate high delays in postal services. Some boosting algorithms, such as light gradient boosting and catboost, have a higher performance in terms of accuracy and runtime efficiency.
  arXiv  Detail & Related papers  (2020-09-24T11:01:22Z)
• End-to-End Prediction of Parcel Delivery Time with Deep Learning for Smart-City Applications [19.442685015494316]
  We study the use of deep learning for solving a real-world case of last-mile parcel delivery time prediction. We focus on a large-scale parcel dataset provided by Canada Post, covering the Greater Toronto Area. We utilize an origin-destination (OD) formulation, in which routes are not available, but only the start and end delivery points.
  arXiv  Detail & Related papers  (2020-09-23T21:35:25Z)
• CARPe Posterum: A Convolutional Approach for Real-time Pedestrian Path Prediction [3.883460584034766]
  We propose a convolutional approach for real-time pedestrian path prediction, CARPe. It utilizes a variation of Graph Isomorphism Networks in combination with an agile convolutional neural network design to form a fast and accurate path prediction approach. Results in both inference speed and prediction accuracy are achieved, improving FPS considerably in comparison to current state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-05-26T01:10:01Z)
• Constructing Geographic and Long-term Temporal Graph for Traffic Forecasting [88.5550074808201]
  We propose Geographic and Long term Temporal Graph Convolutional Recurrent Neural Network (GLT-GCRNN) for traffic forecasting. In this work, we propose a novel framework for traffic forecasting that learns the rich interactions between roads sharing similar geographic or longterm temporal patterns.
  arXiv  Detail & Related papers  (2020-04-23T03:50:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.