链上镖师 / Chain Biaoshi
TRA|外卖订单与无人机车队：旅行时间不确定下的混合调度优化
用两阶段随机规划配置传统配送员与无人机配送员，并以定制化ALNS降低路线和时间惩罚成本
论文用两阶段随机规划联合决定传统配送员、无人机配送员、订单分配和服务路线，并通过ALNS-Sto求解旅行时间波动下的混合车队运营方案。
- 01：第一阶段决定车队构成、订单分配及配送员与无人机路线，第二阶段根据旅行时间情景安排到达和离开时间。
- 02：50个随机情景的实验显示，随机模型相对历史平均时间方案取得1.3%至14.9%的VSS。
- 03：单架无人机配置在高不确定性下会收缩至传统车队，双架配置为混合车队保留更多成本优势。
- 04：无人机配送员的路径成本、迟到惩罚和服务时间窗共同决定混合车队的经济适用范围。
两类运力如何组成混合车队
论文研究从集中式餐厅枢纽出发的即时餐食配送。第一类配送员使用较小车辆，固定成本和配送成本较低，行驶速度较快，载重能力较小；第二类配送员驾驶较大车辆并携带专属无人机，承担更高的车辆与设备成本，具备更大载重能力，可在访问节点发射和回收无人机，让地面路线与空中配送并行执行。
两类配送员的运营属性与无人机配置。来源：Table 2。
混合车队的核心决策是为每个订单选择第一类配送员、第二类配送员或无人机，并同步确定车辆数量、地面路线、无人机航段及发射回收节点。
ALNS-Sto如何求解两阶段模型
模型把配送路线和服务时刻分入两个阶段。第一阶段在旅行时间揭示前决定订单归属、配送员路线、无人机航段和载重状态，目标包含地面路线成本、无人机飞行成本及期望时间惩罚。第二阶段面对各个旅行时间情景，安排节点到达与离开时刻，并同时计算顾客迟到等待和运力提前到达等待产生的惩罚。
1输入历史平均旅行时间、标准差、订单节点、运力容量和无人机参数
2第一阶段配置两类配送员，分配订单并生成地面路线与无人机航段
3第二阶段在旅行时间情景中安排到达、服务、离开和发射回收时刻
4以各情景平均成本评价方案，再由ALNS-Sto持续破坏、修复和更新
定制化ALNS-Sto求解流程。来源：Algorithm 1。
ALNS-Sto按算子权重通过轮盘机制选择破坏与修复操作，对当前方案移除部分订单并重新插入。破坏操作关注长距离、最大延误、平均延误和高成本订单；修复操作包括逐单贪心、批量贪心、最佳插入与遗憾插入。候选解经过成本和接受准则判断后更新当前解，算子权重再依据历史表现调整。
爱荷华餐食订单怎样进入实验
数值实验以爱荷华州餐食订单的空间分布构造配送网络，并把原始地理数据处理为餐厅枢纽和订单节点。默认实验设置包含50个订单和50个随机旅行时间情景；第一类配送员、第二类配送员和无人机的平均速度分别为25、20和40公里每小时，载重上限分别为3、6和1个单位，无人机最长飞行时间为1小时。
爱荷华州餐食订单的原始分布与预处理结果。来源：Fig. 1。
01迟到惩罚系数为每分钟0.8美元，提前到达惩罚系数为每分钟0.4美元。
02旅行时间变异系数用于控制地面配送员与无人机旅行时间的波动幅度。
03每次破坏操作移除当前方案中15%的订单，再由修复算子完成重新配置。
算法性能与随机建模价值
论文以Gurobi精确求解、历史平均时间方案和禁忌搜索作为基准。小规模确定性实例用于核对启发式解的质量，大规模实例覆盖50、75和100个节点以及每名第二类配送员携带一架或两架无人机的配置。ALNS-Sto在多数随机实例中取得低于禁忌搜索的期望成本，并保持适用于中大规模问题的计算时间。
ALNS-Sto与精确算法、HA和TS的性能比较。来源：Table 3。
随机ALNS-Sto相对历史平均时间方案的VSS为1.3%至14.9%，说明将旅行时间情景直接纳入车队与路线决策能够降低确定性近似带来的期望成本损失。
一架到两架无人机的车队成本变化
单架无人机配置下，旅行时间变异系数为0.1时，混合车队总成本为386.6美元，低于全第一类车队的417.7美元和全第二类车队的409.7美元。变异系数升至0.5时，模型选择17名第一类配送员和0名第二类配送员，混合方案收缩为全第一类配置，总成本达到451.7美元。
单架无人机配置下不同旅行时间变异系数对应的成本分解。来源：Table 4。
双无人机配置下不同旅行时间变异系数对应的成本分解。来源：Table 5。
单架无人机配置下不同旅行时间变异系数的成本分布。来源：Fig. 2。
双无人机配置下，混合车队在变异系数0.1、0.3和0.5时的总成本分别为351.9、361.3和410.0美元。增加无人机携带数量扩大了并行配送空间，也让混合配置在更高不确定性水平下继续保留成本优势。
路径成本划出无人机车队的经济边界
论文将第二类配送员的单位路径成本从每公里1.0美元提高到1.4美元，并以全第一类车队作为基准计算成本变化。单架无人机的全第二类车队对路径成本较敏感，成本优势在约每公里1.2美元附近消失。双无人机混合车队在较低路径成本区域可取得15%至20%的成本降幅，在每公里1.4美元的测试上限仍保有成本优势。
相对全第一类配送员方案的成本降幅及适用边界。来源：Fig. 3。
车队配置需要同时读取旅行时间变异系数、第二类配送员路径成本和单车无人机数量。无人机数量增加会扩大有成本优势的参数区域，较高的不确定性与设备运营成本会推动方案增加传统配送员。
迟到惩罚与时间窗共同塑造服务成本
迟到惩罚提高后，客户等待形成的时间成本会在总目标中占据更大权重。旅行时间变异系数为0.1、迟到惩罚系数为每分钟0.4美元时，双无人机混合车队相对全第一类车队降低17.8%的成本；惩罚系数升至每分钟0.8美元时，该配置仍取得11%的成本降幅。
不同迟到惩罚系数下各车队方案的平均成本。来源：Fig. 4。
不同服务时间窗下的平均成本与时间惩罚占比。来源：Fig. 5。
✓利用历史旅行时间估计均值、标准差和变异系数。
✓把迟到惩罚与服务时间窗纳入车队配置和路线方案评价。
✓根据第二类配送员成本与无人机携带数量识别混合车队的经济区间。
✓在不确定性升高时提高传统配送运力占比，控制发射回收同步造成的成本波动。
模型适用条件与研究边界
该模型适用于订单从集中式餐厅枢纽出发、所有配送路线最终返回枢纽、无人机由指定的第二类配送员发射和回收的运营体系。旅行时间分布及其参数需要能够从历史数据估计，订单重量、车辆载重、无人机续航、服务时刻和成本参数也需要提前给定，平台据此生成场景并计算期望运营成本。
01实验依据爱荷华州餐食订单及生成的旅行时间情景，论文未报告其他城市和平台网络上的外部验证。
02旅行时间随机变量采用已知分布和限定区间，分布误设对方案的影响论文未报告。
03恶劣天气造成的无人机完全停飞未被单独建模为运营状态，当前模型以无人机旅行时间波动表达天气影响。
04精确算法只用于小规模确定性实例，大规模结果依赖ALNS-Sto等启发式方法。
05论文考察路径成本、迟到惩罚和服务时间窗，长期设备折旧、充电网络和监管限制未在输入材料中报告。
论文支持的结论范围是给定枢纽、容量、续航、成本和旅行时间情景下的混合车队配置与调度。迁移到其他城市或天气制度时，需要重新估计旅行时间分布、运力成本和服务惩罚参数。
论文：UAV-aided mixed fleet management and operations for food delivery under travel time uncertainty
作者：Wentao Huang，Chenyang Wu，Jacqueline Tsz Yin Lo，Ziyi Wang，Sisi Jian
期刊：Transportation Research Part A
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
