清华美团INFORMS TSL挑战赛冠军论文：RL+超启发式算法破解动态调度难题

本届挑战赛自2024年3月启动以来，吸引了全球范围内的广泛关注。来自9个国家共31所顶尖高校与科研机构的68名学者提交了21篇高质量研究论文，覆盖了强化学习、动态调度、路径规划等方向。

为确保评审的专业性与严谨性，赛事设立了学术委员会与工业委员会。清华大学工业工程系赵磊教授和新加坡管理大学王海教授担任学术委员会联合主席。经过两个委员会的严格评审与筛选，九篇入围论文的团队在2025 INFORMS年度会议上进行了现场展示与答辩，最终评选出一篇最佳论文和两篇最佳论文第二名。

本文介绍的是本届挑战赛的最佳论文《Data-Driven Optimization for Meal Delivery: A Reinforcement Learning Approach for Order-Courier Assignment and Routing at Meituan》。论文由三位学者合作完成：来自亚马逊公司的Ramon Auad、智利阿道夫·伊瓦涅斯大学的Felipe Lagos和澳大利亚悉尼大学的Tomás Lagos。论文提出了一种基于强化学习的订单-骑手分配与路径规划框架，通过N-step SARSA算法与超启发式优化相结合，有效解决了动态调度中的多目标权衡与长期效应问题，为行业提供了可落地的算法范式。

1. 核心研究问题

即时配送面临的问题远非简单的静态VRP，而是一个高度动态、不确定的序贯决策问题。其核心挑战在于：

• 动态性：订单持续生成，骑手随时上线/下线，系统状态瞬息万变。 

• 不确定性：通行时间、餐品准备时间、以及最关键骑手对订单的接受或拒绝行为（Courier Autonomy）都是随机的。平台发出订单后需等待骑手的反馈，这极大地增加了决策的复杂性。 

• 多目标权衡：需同时优化多个时常冲突的目标，包括：

• 最小化总行驶距离

• 最小化订单交付延迟

• 最小化订单丢失率（即避免订单因长时间未分配而取消，影响客户满意度与收入） 

• 长期效应：当前的一个分配决策（例如将一个订单分配给一个看似更近但即将满负荷的骑手）可能会对系统未来的状态产生深远影响（例如导致该骑手后续无法承接顺路的新订单）。传统的贪心或短视算法无法捕捉这种长期效应。

论文主要解决如何在高度动态和不确定的环境中，实现订单与骑手的高效匹配和路径优化，同时平衡即时效率和长期价值。论文将这一问题建模为一个序贯决策过程，其中每个决策点都涉及状态评估、行动选择和奖励计算，通过强化学习来捕捉决策的长期影响。

2. 研究方法 

论文提出了一种创新的混合框架，结合强化学习和超启发式优化。简单来说，系统像“智能大脑”一样学习从经验中改进决策。

• 强化学习组件：论文采用n-step SARSA（State-Action-Reward-State-Action）强化学习算法与值函数近似相结合的策略。其中n-step SARSA算法预测决策的长期影响，值函数近似允许系统泛化到新状态，避免重复计算。

与Q-learning相比，SARSA是一种on-policy算法，能更好地处理骑手行为不确定性。n-step更新则平衡了即时奖励和长期回报的考量，比单步更新拥有更低的方差和更好的性能。

由于状态空间巨大（涉及所有骑手、订单的位置、时间等信息），采用线性值函数近似来估计动作值函数，以处理高维状态空间并保持计算可行性。特征包括订单-骑手比率、未分配订单的数量与紧急度（按交付截止时间分桶统计）、未被指派任何订单的骑手数量、新增订单的平均取送距离等14类指标，捕捉系统拥堵和工作负载平衡。

• 超启发式组件：为解决动作空间（可能的分配方案）巨大的问题，论文没有直接学习每个动作的价值，而是引入一个超启发式组件来智能地生成高质量的动作（即分配方案）。

该超启发式组件维护了一个包含7种底层启发式规则 的工具箱。这些规则是各种简单的插入、删除、交换等局部搜索操作。超启发式的作用就像一个“元调度器”，通过一个基于多臂老虎机的算法来动态地选择、排序和组合这些底层启发式，以在当前状态下构造出新的、更好的解。

底层启发式示例：

• 移除地理上临近的订单，优化其路径后重新插入。 

• 随机移除并重新插入订单（促进探索）。 

• 移除截止时间最晚的订单，优化路径后按紧急度重新插入。

• 协同机制：强化学习负责评估和学习哪个“方向”（由超启发式生成的行动）更有长期价值。超启发式则负责在这个价值方向的指引下，高效地探索解空间。两者不断交互，共同进化。

3. 研究结果 

通过大量计算实验，对比了多种策略（包括最快策略、简单策略、超启发式策略、n-step SARSA和n-step超启发策略）后，研究结果显示：

| 3.1  性能表现

• 本论文提出的 n-step 超启发式策略在所有策略中表现最佳，实现了 12% 的总成本降低。

• 成本降低主要来源于 74% 的延迟成本和 73% 的订单丢失成本的下降。运输距离成本与最快策略相比仅增加13-14%，这说明算法成功地将优化重心从单纯的“省里程”转移到了“保时效、防丢单”上，实现了更好的多目标平衡。

算法优势在高需求、骑手短缺的时段（如午高峰）最为显著。

| 3.2  管理洞察

• 订单推迟的战略价值：算法学会了在高峰期主动推迟分配一些订单，而不是强行分配给不合适的骑手。这避免了因骑手超载而导致的后续大规模延迟，是一种以退为进的智能策略。

• 接纳不确定性：明确建模并学习骑手的自主拒绝行为，这会让算法策略更加鲁棒和实用。

4. 未来展望 

研究不仅推动了餐饮配送物流的优化理论，还为实际平台运营提供了可部署的解决方案。通过强化学习和超启发式的结合，论文展示了在不确定环境中实现智能决策的潜力，未来工作可扩展至更大规模数据集、集成深度学习模型，并探索多平台协同优化。对于即时配送平台，这项研究有助于提升服务质量和运营效率，最终惠及消费者和骑手群体，推动整个行业向更智能化、可持续的方向发展。

更多详情，请阅读论文原文：Auad, R., Lagos, F., & Lagos, T. Data-Driven Optimization for Meal Delivery: A Reinforcement Learning Approach（under review）

欢迎大家使用TSL-Meituan 2024进行更多研究。

本次数据驱动研究挑战赛得到了清华大学工业工程系和清华大学-美团数字生活联合研究院的重要支持。

 美团科研合作 

美团科研合作致力于搭建美团技术团队与高校、科研机构、智库的合作桥梁和平台，依托美团丰富的业务场景、数据资源和真实的产业问题，开放创新，汇聚向上的力量，围绕机器人、人工智能、大数据、物联网、无人驾驶、运筹优化等领域，共同探索前沿科技和产业焦点宏观问题，促进产学研合作交流和成果转化，推动优秀人才培养。面向未来，我们期待能与更多高校和科研院所的老师和同学们进行合作。欢迎老师和同学们发送邮件至：[email protected]。