链上镖师 / Chain Biaoshi
TRC|外卖订单与空地线路：骑手—无人机协同分配与滚动调度
用混合整数规划与改进型ALNS联合决定订单交接、配送路线和无人机使用
论文把外卖订单分配、骑手路线、无人机路线与餐品新鲜度放入同一滚动调度框架，并用改进型ALNS求解10至200单实例。
- 01：骑手可在同一路线中完成直送订单和无人机交接订单。
- 02：模型同时计入骑手报酬、无人机固定成本、电费与餐品新鲜度损失。
- 03：改进型ALNS面向40至200单实例提升了解质量、速度与稳定性。
- 04：无人机使用量增加可能降低运营费用，也可能扩大餐品新鲜度损失。
- 05：距离型骑手补偿方案在成本、服务质量与骑手工作量之间表现更均衡。
骑手与无人机如何协同履约
论文面向午餐和晚餐高峰下的即时外卖配送，将多名骑手、多个无人机站点和多架无人机放入同一调度系统。每个订单可以由骑手从餐厅直接送到顾客，也可以由骑手取餐并运至站点，再由无人机送往顾客附近的交付点。骑手可在一次路线中同时处理直送和交接任务，订单分配与两类路线由此形成紧密的时空耦合。
骑手直送与骑手—无人机协同配送流程（来源：Fig. 1）
系统需要同步决定订单交给哪类资源、骑手按什么顺序取送餐、订单在哪个站点交接以及无人机采用哪条飞行路线。任何一项决策变化都会影响其他路线的时间可行性、资源占用、配送成本和餐品新鲜度。
订单分配与空地路线怎样进入同一模型
研究建立多骑手—多无人机即时取送货混合整数线性规划模型。目标函数由骑手直送报酬、骑手处理无人机订单的补偿、无人机启用成本、飞行电费和餐品新鲜度损失五部分组成。决策变量描述骑手与无人机经过的弧、无人机是否启用以及订单在站点的交接关系，到达时间和载荷状态用于约束履约过程。
01每个订单遵守先取餐、后送达的配对与先后顺序。
02骑手受同时携带订单数和载荷上限约束。
03无人机受电池能量、载荷、单次携单量和站点归属约束。
04骑手路线采用曼哈顿距离，无人机路线采用欧氏距离。
05餐品新鲜度按备餐完成至顾客收餐之间的时间计算。
1读取订单、骑手位置、无人机站点和可用机队
2联合生成骑手直送与站点交接候选方案
3校验时间窗、载荷、电池和取送先后约束
4计算骑手报酬、无人机费用与新鲜度损失
5输出订单分工及相互匹配的空地配送路线
这一建模方式允许骑手把直送任务和无人机交接任务编入同一条工作路线，使平台能够在统一成本与服务质量口径下选择配送方式。
改进型ALNS怎样搜索协同路线
大规模即时取送货问题难以依靠精确求解器在有限时间内完成。论文采用双序列编码表达骑手和无人机方案，以贪心插入构造初始解，再通过自适应移除与修复算子反复重组订单。算法使用模拟退火规则接受候选解并动态更新算子权重，同时加入路径解码缓存、并行插入评估和时间窗引导的位置筛选，以降低重复计算。
改进型自适应大邻域搜索框架（来源：Algorithm 1）
移除算子与修复算子的贡献比例（来源：Fig. 2）
定制修复算子分别处理无人机优先、骑手与无人机同优先、邻近骑手插入和邻近站点插入等情形。贡献分析显示，多样化算子共同参与搜索，为大规模实例中的解质量和搜索稳定性提供支撑。
Grubhub实例与滚动调度场景
实验基于公开的Grubhub日度外卖订单数据构造60个实例，订单规模覆盖10、20、30、40、50、100和200单。骑手起点与无人机站点通过聚类生成，不同规模配置3至50名骑手、2至12个站点及相应无人机。静态实验用于比较精确求解器和多种启发式算法，动态实验把规划期划分为连续调度区间并重复求解新到订单。
七组实验实例的订单与配送资源配置（来源：Table 2）
Grubhub实验实例的节点与配送资源空间分布（来源：Fig. 4）
动态订单到达下的滚动时域调度结果（来源：Table 8）
从40单扩展到200单的算法表现
在40至200单实例中，改进型ALNS相对经典版本的平均解质量提升分别为3.91%、3.64%、3.42%和2.74%，各规模平均求解时间降低20%至50%。实例2005的计算时间由580.04秒降至327.83秒。与精简算子版本相比，完整算子池带来更低目标值；与HVNS相比，100单实例的优势为4.57%至7.87%，200单实例的优势最高达到8.18%。
经典ALNS与改进型ALNS的性能比较（来源：Table 6）
改进型ALNS、精简型ALNS与HVNS对比（来源：Table 7）
40单平均解质量提升
3.91%
2005实例节省时间
252.21秒
无人机投入与站点容量怎样配置
敏感性实验考察无人机固定成本、电价、每站机队规模和单次携单能力对订单分工与系统目标值的影响。固定成本上升会改变无人机启用数量和订单配置。每站无人机数量从0架增加到2架时收益较明显，继续增加到3至4架后边际收益趋缓。平台需要把设备投入、订单密度和站点覆盖条件共同纳入容量决策。
无人机固定成本敏感性分析（来源：Fig. 6）
每站无人机数量对成本与订单分配的影响（来源：Fig. 8）
无人机配置存在规模效应与边际收益递减。站点机队规模应随订单量、空间分布和成本参数调整，固定增加设备数量无法持续获得同等幅度的运营改善。
补偿机制的适用条件与研究边界
论文发现，无人机承担的订单数与总体目标值和餐品新鲜度均呈负相关。无人机能够减少平台运营费用，更多交接和配送安排也可能扩大服务质量损失。骑手处理无人机订单的分成比例会同步改变骑手报酬、系统成本和无人机订单量，距离型补偿方案在运营效率、服务质量与骑手工作量之间取得了更均衡的实验结果。
骑手补偿分成比例的运营影响（来源：Fig. 10）
无人机订单补偿机制的综合运营影响（来源：Fig. 12）
✓模型假设无人机同质、匀速飞行，并从指定站点起飞后返回同一站点。
✓每个调度周期内的订单、骑手和无人机信息均被视为预先已知。
✓旅行时间按平均速度给定，骑手与无人机分别采用曼哈顿距离和欧氏距离。
✓实验订单取自Grubhub公开数据，骑手位置和无人机站点由聚类生成。
✓论文未报告恶劣天气、实时交通扰动和真实平台长期上线验证结果。
研究结论适用于信息可获得、站点与机队容量明确且飞行条件稳定的滚动调度场景。平台采用相关补偿和容量规律时，需要结合本地订单密度、站点布局、骑手收入制度与服务质量目标重新标定参数。
论文：Integrated order assignment and routing for on-demand food delivery with courier-drone coordination
作者：Xuting Sun，Kai Xue，Jiage Huo，Huan Zhang
期刊：Transportation Research Part C
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
