Optimization of Rider Scheduling for a Food Delivery Service in O2O Business 论文学习

    外卖平台看似只需把餐从A点送到B点，实则背后是一场对“时间-空间-人力”三维耦合的精密博弈：需求随区域和时段剧烈波动，骑手时而空转、时而短缺。论文把这一难题拆成两阶段——先用混合整数规划（MIP）在宏观层面决定“最少需要多少人”，再用大邻域搜索（LNS）把城市网格化、时段切片化，在微观层面快速拼出谁去哪、何时开工、跑哪几条单，既保证承诺时效，又把总成本压到最低。实验显示，只要颗粒度够细，算法能在分钟级给出方案，显著削减闲置里程；进一步灵敏度测试指出，压缩订单时间窗会陡增用工量，而让骑手固定熟悉片区则能用更少人力稳住服务水平，等于告诉平台“ tightened SLA 的代价”和‘熟人经济’的红线在哪。
    一句话总结：把骑手当成可时空重配置的流动仓库，用 MIP+LNS 做联合调度，就能在时效与成本之间找到平台最想要的杠杆。

简介

    过去七年，外卖App把中国人的用餐方式彻底重写：早上睁开眼，68%的年轻人已把早餐交给手机下单，33%的人一周至少六次不与厨房照面。Meituan、饿了么这类平台把餐厅搬到线上，却把“最后三公里”的不确定留给了自己——它们不像麦当劳那样养一支全职骑手军团，而是让数百万众包骑手在时空缝隙里“快闪”接单。于是，午餐12:00-13:00与晚餐17:00-19:00的脉冲式订单洪峰一来，商圈瞬间“缺氧”，郊区却可能同时闲置大批运力；非餐期又反过来，骑手空转、订单稀疏，平台仍要为“随时待命”付出固定成本。需求像潮水，骑手像浮桶，桶跟不上浪，延迟、投诉、餐凉、口碑塌方便接踵而至。本文的出发点正是把这股“潮汐”切成细颗粒——以3 km为半径、两小时为一个时间窗，把城市拆成可重新拼接的乐高积木；再用两阶段混合整数规划先算“最少需要几块积木”，后用大邻域搜索实时拼出“谁去哪块、何时动身、跑哪几单”，让骑手在微观层面像共享仓库一样被时空重配置。实验显示，只要切片够细，算法能在分钟级给出方案，显著削减闲置里程；进一步灵敏度测试指出，压缩订单时间窗会陡增用工量，而让骑手固定熟悉片区则能用更少人力稳住服务水平，等于告诉平台“tightened SLA的代价”和“熟人经济”的红线在哪。

问题描述

把一天切成若干 3 h 的「时段」，再把城市切成若干「子区域」。平台发现：
T1、T3（例如 00:00-03:00、09:00-12:00）：订单少，骑手晒太阳→运力过剩
T2、T4（11:00-13:00、17:00-19:00）：订单暴涨，骑手飞奔→运力不足
传统做法：高峰期拼命招兼职，平峰期白白养人。
本文做法：让闲置子区的骑手“临时出差”到爆单子区，用现存资源填平波峰波谷。

图模型

把「餐厅+顾客」抽象成一张无向图 G=(V,E)
– 虚拟节点 0：骑手的出发点（ depot）
– 订单 i：取餐节点 oi → 送餐节点 di，必须同一骑手完成且先取后送
决策粒度：
– 空间：子区域 s∈S
– 时间：时段 t∈T（每 3 h 一段）
骑手颗粒：独立承包商，自带电动车，容量 cr，熟悉区域 Sr⊆S（陌生街路不去）

两阶段调度框架

Stage-1「路线+数量」

先解决“每块区域、每个时段需要多少骑手、跑什么路线”。
平台会输出两类变量：
xrij：骑手 r 要不要从节点 i 走到节点 j，这决定了取送顺序；
xrst：骑手 r 要不要在时段 t 去子区 s 上班，这决定了人力分布。
这一阶段必须同时满足四条硬规则：
每个订单只能被同一骑手服务一次；
必须先取餐、后送餐，时间不能颠倒；
车上载重不能超过餐箱容量；
顾客收到餐的时刻不能晚于其期望送达时间。
目标只有一个：把“固定人力成本 + 行驶里程成本”压到最低。

Stage-2「跨区借调」

再解决“如何把闲人搬到忙区”。
平台直接把 Stage-1 算出的 xrst 拿来用，把当前时段在低需求区空转的骑手“借”到高需求区救急。
这里有三条红线：
一个骑手在同一时段只能待在一个子区，不能分身；
从原辖区到目标辖区的直线距离不能超过平台设定的 Lmax，防止“海淀骑手被调到通州”；
目标子区必须在该骑手的“熟悉区域”集合 Sr 里，保证他不迷路。
目标也只有一个：让“调度次数”或“总调度时间”最少，从而用最小的代价把波峰波谷抹平。
两阶段环环相扣：先定路线、算缺口，再搬人力、填缺口，既省钱又快速。

ORSFDS 大邻域搜索（LNS）启发式

    骑手调度是 NP-hard 的 dial-a-ride 扩展，城市级实例无法让精确算法在合理时间内收敛。作者采用“大邻域搜索+模拟退火”两板斧：先用插入启发式秒出一条可行路线，再在每次迭代中“拆-修”大扰动，偶尔接受劣解，既快又稳。

主算法 7 步

① 插入启发式生成初始可行解 s_ini；
② 设 s_cur = s_best = s_ini；
③ Remove 算子拆部分订单得残缺路线 s_part；
④ Repair 算子把被拆订单重新插入，得邻域解 s_nei；
⑤ 若 s_nei 优于 s_best 则更新，否则按模拟退火概率接受劣解；
⑥ 连续 N 次迭代无改进即停；
⑦ 输出最终骑手数与路线。

Remove 算子

• Natural Sequence：拔掉骑手空驶的完整子段
• Max Time-Window：拔掉时间窗最宽的订单
• Worst Order：拔掉“移除后成本下降最大”的订单
• Cluster：以随机节点为中心、距离阈值内拔单

Repair 算子

• Optimal Insertion：最小成本增量插入
• Regret-k：优先插入错过前 k 个最佳位置后悔值最大的订单
• Max Waiting Time：插入到骑手等待时间最长的空档

控制策略

模拟退火接受准则（温度指数衰减）+ 全局最优连续 N 次迭代未改进即终止。

实验与结果分析

实验环境

C# 实现 LNS，Gurobi 9.1 做对比；Win10-64bit，i7-2.6 GHz，16 GB。Gurobi 在 10 单以内可求最优，超过即改用 LNS。

基准库验证

采用 Cordeau 标准 DARP 实例，把“双时间窗”改成“单侧时间窗”后测试。24 例中 LNS 16 例命中最优，TS 仅 13 例；LNS 平均 CPU 时间略长，但差距<20 s，可忽略。图 3 显示 LNS 收敛慢而平稳，1000 次迭代后目标波动<0.5%。

大连真实数据

数据源：2017-01-01 至 01-15，日均 5000+ 单。挑出 23 个热门子区域，08:00-20:00 每 2 h 一段，共 6 时段。

微观算例（46 单，10:00-12:00，罗斯福商圈）

LNS 给出最少 13 名骑手即可完工，比原始排班少 1 人；路线见图 8 与表 5，平均载重 82%，无超时单。

宏观对比（23 区×6 时段）

• 骑手总量：LNS 需 300 人·次，现实派 328 人，↓8%。
• 调度总次数：LNS 1800 次，现实 2180 次，↓17%。
• 直接节省调度成本 4200 CNY（约 3%）。
  表8示例骑手最多跨 6 区作业，印证“闲人搬家”有效。
  

敏感性分析

① 时间窗松紧（30/45/60 min）
窗越紧→骑手需求指数上升，人均单量下降 35%；窗放宽到 60 min 可再省 18% 人力。
② 区域熟悉度
定义“熟悉度 = 百度距离／实际距离”；值越小越不熟。图 10 显示熟悉度从 0.7 提到 1.0，骑手需求下降 12%；平台若强制骑手只在熟悉区接单，可显著抑制冗余派工。

LNS 在两阶段模型里同时砍掉“人头”与“调度次数”，对真实外卖网络具有即插即用的经济价值。

总结

• 提出“两阶段”骑手调度框架：
– 阶段一：把城市拆成子区、时段，用改进的 dial-a-ride 模型确定“最少骑手+路线”，LNS 快速求解；
– 阶段二：把闲人跨区借调，Gurobi 求解“最少调度时间”。
• 用大连半月真实数据验证，高峰期单量波动一目了然。

实验结果
• 与当前系统比：骑手总量 ↓8%，调度次数 ↓17%，直接节省 4200 CNY。
• 敏感性：
– 时间窗每收紧 15 min，骑手需求 ↑约 12%；
– 区域熟悉度每提升 0.1，骑手需求 ↓约 6%。

展望
• 动态需求：把历史波动、节假日、天气纳入预测；
• 更优分区：用聚类或 Voronoi 代替人工商圈划分；
• 鲁棒优化：实时堵车、取餐延迟、顾客改址等不确定因素。