计算机科学
车辆路径问题
启发式
布线(电子设计自动化)
运筹学
预测(人工智能)
图形
数学优化
人工神经网络
模拟退火
功能(生物学)
订单(交换)
缩小
旅行时间
总成本
迭代局部搜索
最优化问题
流量网络
实时计算
模拟
组合优化
供应链
降低成本
分布式计算
还原(数学)
作者
Niels de Jong,Ilke Bakir,Kees Jan Roodbergen
标识
DOI:10.1287/trsc.2025.0133
摘要
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 .
科研通智能强力驱动
Strongly Powered by AbleSci AI