Georgia Tech×Grubhub 70页重磅论文：定义"外卖配送路由问题"（MDRP）的开山之作 在学术界，有些论文不是在解决问题，而是在定义问题。Georgia Institute of Technology的Alan Erera教授团队（Damian Reyes、Martin Savelsbergh）与美国外卖平台Grubhub的决策工程团队（Sagar Sahasrabudhe、Ryan O'Neil）合著的这篇70页论文，就属于此类。它首次系统提出并形式化了"Meal Delivery Routing Problem"（MDRP，外卖配送路由问题）——将外卖配送从一个模糊的工程实践，提升为一个严格定义的运筹学研究对象。 这不仅仅是学术上的概念创新。在这篇论文之前，外卖配送的优化研究散落在Vehicle Routing Problem（VRP）、Pickup and Delivery Problem（PDP）、Dynamic Fleet Management等多个传统领域中，缺乏统一的问题定义和标准化的实验方法。MDRP的提出，为整个领域建立了共同语言和评价标准。 为什么外卖配送是"最后一公里物流的终极挑战" 论文开篇直接亮出了一个大胆的论断：外卖配送是最后一公里物流的终极挑战（the ultimate challenge in last mile logistics）。这个论断并非夸张，而是基于对外卖配送独特特征的精确分析： 极端时间压力。传统快递的配送窗口是"今天"或"几小时内"，外卖的期望是30-60分钟，理想状态下甚至更短。从食物制作完成到送达，骑手可能只有15-20分钟——这意味着几乎没有合并优化的时间余地。任何算法的计算时间都必须在秒级完成。 极端动态性。快递可以提前规划路线（因为包裹已经在仓库中等待），外卖订单是实时涌入的。在Grubhub的运营中，高峰时段每分钟有数十个新订单到达，每个订单都可能改变最优的全局分配方案。系统必须在持续变化中做出决策，而不是等所有信息到齐后一次性规划。 供给侧的根本不确定性。外卖骑手不是企业员工，而是独立承包商（gig workers）。他们有自主决策权——可以选择何时上线、接受或拒绝哪些订单、甚至中途下线。这与传统车辆路由问题中"车队完全服从调度"的假设根本不同。平台只能通过经济激励间接管理运力，而非直接指挥。 需求的时空剧烈波动。外卖需求在时间维度上呈现极端的峰谷差异（午高峰可能是下午3点的10倍），在空间维度上高度集中于商业区而非均匀分布。这种"脉冲式"需求模式对运力调度提出了独特挑战。 MDRP的形式化定义：从混沌到秩序 论文最重要的贡献是将外卖配送的复杂现实抽象为一个可计算的数学模型。MDRP的核心要素包括： 订单（Order）：包含取餐地点、送餐地点、下单时间、预计出餐时间、承诺送达时间 骑手（Courier）：包含当前位置、在线时段、载货容量、移动速度 两阶段决策：(1) 派单——将订单分配给骑手；(2) 路由——确定骑手的取餐和送餐顺序 动态到达：订单随时间持续到达，信息不完全 多目标：最小化配送时间、最大化服务率、控制成本 看似简单的定义背后，隐藏着巨大的计算复杂性。即使只有20个订单和5个骑手，可能的分配方案也是天文数字。加上动态到达和时间约束，问题的在线版本比离线版本难度高出数个量级。 算法框架：两阶段承诺与优先级调度 论文的算法贡献同样深厚。研究者提出了一个"两阶段承诺"（Two-Stage Commitment）框架，这是对传统"单阶段承诺"方法的重大改进： 单阶段承诺：订单到达时立即分配给骑手，并同时确定路线。简单但存在根本缺陷——过早锁定分配，无法利用后续到达的信息进行优化。 两阶段承诺：第一阶段将订单"软分配"给骑手（可调整），第二阶段在骑手即将出发时才"硬确认"路线。这个延迟确认机制为后续订单的合并和重新优化留出了窗口。 论文通过大规模计算实验证明：在几乎所有场景中，两阶段承诺都显著优于单阶段承诺。尤其在低动态性（订单到达速度较慢）、低取餐灵活性（餐厅出餐时间固定）和高订单/运力比（骑手不够用）的场景中，单阶段承诺的劣势更为明显——导致更多订单无法送达和更长的配送时间。 此外，论文还引入了优先级调度方案：在每个优化周期内，不是一次性求解所有订单的最优匹配，而是分三轮进行——优先处理已经接近超时的紧急订单，再处理普通订单，最后处理新到达的订单。这种优先级机制在骑手短缺时尤为关键，能显著降低订单未送达率。 运力管理：从算法到班次调度的闭环 论文不仅关注实时派单（在线决策），还深入研究了运力预规划（离线决策）——如何提前安排骑手的班次以匹配预期需求。这在学术上是一个"两阶段随机规划"问题，在工业上是外卖平台运营的核心难题： 班次排太多：骑手闲置，平台承担不必要的人力成本（如果有保底工资或排班激励）。班次排太少：高峰时段骑手不够，大量订单超时，用户体验崩溃。最优解是让运力曲线尽可能贴合需求曲线——但需求本身是不确定的。 论文提出了基于需求预测的班次调度优化方法，并通过实验展示了运力水平对系统性能的非线性影响：在某个临界点以下，增加少量运力能带来巨大的服务改善；超过临界点后，边际收益急剧递减。找到这个"最优运力水位"是平台运营的关键。 标准化实验体系的建立 论文的隐性贡献在于建立了MDRP研究的标准化实验方法论。作者设计了一套参数化的实例生成器，可以控制以下维度来生成测试场景： 动态性（Dynamism）：订单到达的集中/分散程度 紧急性（Urgency）：从下单到期望送达的时间窗口 地理特征：餐厅和配送地点的空间分布 规模：订单数和骑手数 供需比：骑手运力相对于订单量的充裕程度 通过这套体系，后续研究者可以在标准化条件下比较不同算法的性能——这正是一个成熟研究领域所必需的基础设施。在MDRP论文之后，大量后续研究（包括前面介绍的美团、清华等团队的工作）都在这个框架下展开。 对物流行业的战略启示 1. "延迟承诺"是动态物流的通用原则。两阶段承诺的核心理念——尽可能延迟不可逆决策，为后续信息的到来保留调整空间——不仅适用于外卖。快递分拣的路线确认、网约车的拼车匹配、仓库拣选的批次划分，都可以应用类似的延迟承诺策略。在信息不完全的动态环境中，"慢一步"往往比"快一步"更优。 2. 独立承包商模式重新定义了优化的边界。当"车队"不受直接控制时，传统VRP的所有假设都需要修正。平台的优化对象不仅是路线和分配，还包括激励设计——如何通过奖金、热区加价、完成率奖励等机制，引导骑手的行为趋近系统最优。激励设计本质上是一个机制设计问题，与算法优化同等重要。 3. 运力规划比实时算法更值得投资。论文的实验清楚显示：在骑手严重不足的场景下，任何实时算法都无法挽救服务质量。运力的"量"决定了系统的上限，算法的"质"决定了在这个上限内能达到的水平。对于外卖平台和即时物流企业，运力预测和班次调度系统的投资优先级应高于派单算法。 4. 问题定义的价值常常超过问题求解。MDRP论文的最大贡献不是某个具体算法，而是一个清晰的问题定义和评价体系。对于企业内部的运筹团队，花时间准确定义"我们到底在解什么问题"——包括目标函数、约束条件、信息结构——往往比急于编写优化代码更有价值。 信息来源：Reyes, D., Erera, A., Savelsbergh, M., Sahasrabudhe, S., & O'Neil, R. (2018). "The Meal Delivery Routing Problem." Georgia Institute of Technology & Grubhub. | H. Milton Stewart School of Industrial Engineering, Georgia Tech | Grubhub Decision Engineering
