The Meal Delivery Routing Problem with Courier Behavior and Graph Neural Networks

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 [Formula: see text] to [Formula: see text] 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 .

Authors

Institutions

Publication Details

Journal
Transportation Science
Published
2026-11-18
DOI
https://doi.org/10.1287/trsc.2025.0133
Primary Topic
Vehicle Routing Optimization Methods
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

The Meal Delivery Routing Problem with Courier Behavior and Graph Neural Networks

Kees Jan Roodbergen, Ilke Bakir, Niels de Jong
3 links
Transportation Science
Vehicle Routing Optimization Methods
article

The Meal Delivery Routing Problem with Courier Behavior and Graph Neural Networks

Kees Jan Roodbergen, Ilke Bakir, Niels de Jong
article en

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 [Formula: see text] to [Formula: see text] 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 .

Transportation Science
University of Groningen (NL), Dialyse Centrum Groningen (NL)
Vehicle Routing Optimization Methods
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon