The Meal Delivery Routing Problem with Courier Behavior and Graph Neural Networks
Abstract
We consider the meal delivery routing problem (MDRP) faced by online food delivery platforms. In the MDRP, customers’ food orders arrive dynamically throughout the day and must be assigned to autonomous couriers. Each order is prepared at a merchant and must be delivered to a customer by a courier. The platform faces several challenges in finding good courier-to-order assignments. First, couriers differ in their behavior. Couriers make different decisions on routing, rejection, and idling. Second, courier-to-order assignment decisions should consider the trade-off between direct and uncertain future costs of assignment. Third, decisions must be made in seconds—often for thousands of couriers and orders—to ensure the responsiveness of the platform. Fourth, multiple orders can be assigned to one courier as a bundle, providing better routing opportunities. Fifth, assignments may be postponed in anticipation of better future assignment opportunities. Sixth, uncertainty arises from food preparation times, travel speed, the spatiotemporal distribution of orders and courier shifts. To address these challenges, we develop a polynomial-time heuristic using a graph neural network (GNN) that estimates future assignment costs in a cost function approximation (CFA) framework. To test the performance of our CFA/GNN heuristic, we create an open-source discrete-event simulator for the MDRP that simulates the delivery of thousands of orders within seconds. We validate our discrete-event simulator on real-world data from Meituan. We train our GNN with the twin delayed deep deterministic policy gradient algorithm. The CFA/GNN heuristic achieves an average click-to-door time reduction of to compared with a myopic benchmark. Our heuristic handles courier behavior and uncertainty, using bundling and postponement mechanisms, enabling real-time decision making for online food delivery platforms.
History: This manuscript was accepted to the Transportation Science Special Issue, The First INFORMS TSL Data-Driven Research Challenge.
Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2025.0133.

