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

Instant food delivery has become one of the most popular web services worldwide due to its convenience in our daily lives. A fundamental problem in this service scenario is the accurate prediction of courier routes, which is essential for optimizing task dispatch and thereby improving delivery efficiency. It not only increases the satisfaction of both couriers and users but also drives higher profitability for the platform. The deployed heuristic prediction approach of the platform accounts for only limited human-selected task features and neglects couriers' preferences, resulting in sub-optimal performances. Moreover, existing learning-based methods fail to adequately explore the diverse factors influencing couriers' decision-making behaviors and intricate relationships among factors. To meet the urgent need for a powerful route prediction approach that benefits millions of couriers, users, and the platform itself, we propose a M ulti- R elational G raph-based R oute P rediction (MRGRP) method, which enables fine-grained modeling of the correlations among tasks influencing couriers' decision-making and achieves accurate prediction. We encode spatial and temporal proximity, along with the pickup-delivery relationships of tasks, into a multi-relational graph, then design a GraphFormer architecture to capture these complex correlations. Furthermore, we introduce a route decoder that leverages information about couriers as well as dynamic distance and time contexts for dynamic prediction. It also utilizes existing route solutions as a reference to find better outcomes. Experimental results demonstrate that our proposed model attains state-of-the-art performance in route prediction on offline data from cities of diverse scales. We then deploy our model on the Meituan Turing online platform, where it significantly surpasses the existing deployed heuristic algorithm and achieves a high route prediction accuracy of 0.819, which is required for the quality and satisfaction of couriers and users in the instant food delivery service. We have open-sourced our code at https://github.com/tsinghua-fib-lab/MGRoute.