配送算法12 Courier routing and assignment for food delivery service using reinforcement learning

Courier routing and assignment for food delivery service using reinforcement learning论文学习

Conclusion

    这篇论文构建了一个逼近真实外卖场景的马尔可夫决策模型，目标是在有限骑手数量下最大化一段时间内的总收益。模型显式记录骑手位置及订单起讫点，骑手需完成接单-配送闭环。比较了三类方法：
单骑手简化模型 + Q-Learning，其策略直接复用到多骑手场景；
单骑手简化模型 + Double Deep Q-Network（DDQN），同样复用策略；
完整模型（系统状态含全部骑手与订单位置）+ DDQN。

规则基策略作基准。实验显示：单骑手 Q-Learning 已优于规则基；单骑手 DDQN 再提升，但对超参数敏感；完整模型 DDQN 尚未给出结果。

方法创新
• 建立网格化 MDP：状态含全部骑手/订单位置；动作集除四向移动外，新增“拒单”与“空闲时预移向热门餐厅”。
• 首次在餐饮配送中系统比较 Q-Learning 与 Double Deep Q-Network（DDQN），并探索超参数、网格规模、餐厅数量对性能的影响。
• 为大规模实例提出“单骑手策略复用”简化方案，显著缩短训练时间且效果优于规则基线。

Background

    随着通信技术与位置服务的快速发展，Doordash、Uber Eats 等外卖平台需求激增。平台需在有限运力与限时配送内，实时完成订单-骑手匹配及路径规划，直接影响收益与长期竞争力。该问题可视为动态车辆路径问题（DVRP）的特例，其难点在于订单、骑手及配送时间的不确定性，并需兼顾餐食保鲜、备餐等待等运营细节。
    文献中多采用动态规划、启发式、图匹配或近似动态规划等方法，强化学习（RL）应用仍有限。本文以 RL 框架建立外卖配送 MDP：状态含全部骑手与订单位置；动作除常规接单-配送外，新增“闲置时主动移向热门餐厅”和“拒单”选项，以平衡即时与未来收益，并缩短整体配送时长。目标为在订单到达未知的情况下最大化累计收益。
    分别用 Q-Learning 与 Double Deep Q-Network（DDQN）求解，并针对大规模场景提出“先训练单骑手、后复用策略”的简化方案，显著加快策略生成且优于规则基线。实验还揭示了 DDQN 对超参数的高度敏感性，并给出配置建议。

问题设定

在 G×G 网格中，K 名骑手需在有限时间内完成“餐厅取餐→送达客户”流程。
关键假设：
• 订单动态到达，含起点、终点、最长等待时长、被拒次数。
• 骑手可拒单；被拒订单回列表，逾期自动消失。
• 网格各格点成为订单起/终点的概率异质（餐厅、客户聚集）。

订单起点空间：订单起点位置除了属于m*m个网格点位置空间外，新增了两个状态：1）取餐/送餐的路上；2）空闲无订单状态

订单目的地空间:订单起点位置除了属于m*m个网格点位置空间外，新增了一个状态，外卖员处于空闲无订单配送状态无目的地。

此外，外卖订单包括五个属性：订单起点、订单目的地、订单持续时间、被拒次数、配送该订单外卖员ID

外卖员在接受订单之后每移动一步的reward是-1，空闲状态移动一步-0.1；
每次成功提取和交付订单得到正的reward为m^2；
没有成功提取和交付订单（提错货、送错货）得到负的reward/penalty为-m^2；
原地空闲等待无reward；分配订单选择原地等待不移动得到负的reward/penalty为-m^2；
订单一经分配就拒绝-m/3； 在配送订单过程中拒绝该订单得到负的reward/penalty为-m^2；

除此之外，如果订单在服务时间内未被有效分配给外卖员离开系统，额外增加惩罚。现实生活中，每个客户通常都有耐心等级，如果他/她没有在一定的时间内得到服务，他/她就会离开系统。

MDP 建模

• 状态 s = ⟨所有骑手位置 | 所有订单起点 | 所有订单终点⟩，维度随骑手与网格规模指数增长。
• 动作：四方向移动、取餐、送达、拒单、停留 7 类。
• 奖励：
– 成功取/送：+R（与网格大小成正比）；
– 每一步移动：如已派单 −0.1，否则 0；
– 非法取/送、拒单、停留却持有订单、订单超时：均按网格大小惩罚。

求解算法

a) Q-Learning
用 Bellman 更新，但大状态空间易爆炸。因此提出“单骑手训练→多骑手复用”的近似策略。

b) DQN / DDQN
• DQN：经验回放 + 神经网络拟合 Q 值。
• DDQN：双网络（在线/目标）抑制过估计；小场景硬更新，大场景软更新防梯度爆炸；梯度裁剪归一化。

c) Rule-based 基准
最短路径接单、永不拒单、无单即停留。

仿真评估流程

(1) 初始化骑手与订单位置；
(2) 按策略选动作；
(3) 更新环境（订单时长、超时剔除、新订单到达）；
(4) 计算即时奖励；
(5) 为空闲骑手派单（最短距离优先）；
(6) 记录下一状态，迭代至时钟结束；
(7) 输出总订单量与累计奖励。

问题规模

不同问题规模（网格大小、外卖员数量、状态空间和动作空间大小）下进行实验

餐馆及订单目的地分布热力图

实验结果

三种方法对比：

1.Q-learning :训练单agent的Policy，将应用到所有外卖员；
2.DDQN:训练单agent的Policy，应用到所有外卖员；
3.DDQN:直接训练多agent的Policy；

平均收获报酬对比结果

平均交付订单数对比结果

可视化展示

场景一 外卖员空闲一段时间后接到订单

场景二 允许外卖员拒绝订单

展望

状态空间只考虑订单和外卖员位置信息，可以加入外卖员工作时间、订单准备时间等等属性改进模型。
本文考虑的外卖员数量太少，每增加一个外卖员，状态空间呈指数式增长；可以对外卖员和订单的属性特征进行聚合降维，缩减状态空间