链上镖师 / Chain Biaoshi
CIE|上门服务实时加单：多技能队伍排班路径优化
面向时间窗、同步作业和实时新任务的 ALNS 调度框架
这篇论文研究上门服务场景中多技能队伍面对实时新增任务时，如何在时间窗、同步服务和既有承诺约束下持续重排线路，并用预期任务为未来需求预留调度空间。
- 01：问题来自动态上门服务：新请求实时到达，队伍计划需要持续更新。
- 02：模型同时处理技能匹配、任务优先级、时间窗、冻结期和多队同步服务。
- 03：方法用 MIP 定义问题，并用 ALNS 在滚动重优化框架中快速改进方案。
- 04：预期任务以低优先级 ghost task 进入模型，用来测试预测质量对调度收益的影响。
研究背景
论文关注按需上门服务行业，例如家庭医疗、家电维修和家庭维护。该场景下，服务请求会在运营过程中随机出现，平台需要把不同技能的服务队伍派往分散地点，同时兼顾客户时间窗和任务优先级。
作者指出，美国按需上门服务市场已有 2240 万年度消费者，年支出达到 576 亿美元。移动平台扩大了实时下单比例，也让原先静态排班方案需要在当天运行中不断被更新。
这类问题的难点集中在现场承诺已经形成：队伍可能正在路上或正在服务，新增订单到达后，系统只能在可调整的计划段内重排线路。
核心问题
论文将问题定义为带时间窗和同步约束的动态劳动力排程与路径问题 DWSRP-TW-SC。每个任务有到达时间、处理时间、优先级和服务时间窗，每支队伍有固定技能组合，部分任务需要多支队伍同时开始服务。
来源：Fig. 1。冻结期用于保护已承诺任务，重优化从各队伍完成冻结任务后的地点和时间继续展开。
01已完成任务从后续优化中移除。
02冻结期内即将开始的非预期任务保持原安排。
03新增任务进入当前重优化集合。
04预期未来任务以低优先级 ghost task 形式进入模型。
目标函数是最小化所有任务的总加权吞吐时间，吞吐时间从任务到达到任务完成计算。无法在工作日内完成的任务会被外包，并被视为在当天结束时完成。
方法框架
框架在新任务数量达到阈值 βtask，或距离上次重优化经过 βtime 后触发。每次触发时，系统固定冻结期内任务，重新设计剩余队伍路径，并把预测得到的短期未来请求纳入同一优化过程。
1读取上一轮未服务任务、新到达任务和预期任务。
2识别冻结期内需要保留的任务安排。
3用构造启发式生成初始队伍线路。
4用 ALNS 反复移除和修复任务分配。
5输出当前轮队伍任务计划并等待下一次触发。
来源：Algorithm 2。ALNS 通过破坏算子、修复算子、模拟退火接受准则和权重更新持续改进当前解。
ALNS 的破坏算子包括随机任务移除、最差任务移除、随机队伍移除、最差队伍移除和 Shaw 移除。同步任务一旦被选中移除，会从所有已分配队伍线路中同时移除，避免留下不完整的同步安排。
案例或实验设置
论文用一个两支队伍、8 个任务和 3 类技能的示例说明同步约束。任务 4 需要多支队伍配合，较早到达的队伍必须等待另一支队伍到达后才能同时开始服务。
来源：Fig. 2。示例展示了技能需求、队伍路径、任务处理时间和同步服务之间的关系。
来源：Fig. 3。任务 4 的同步安排让 crew 2 在时间 25 到达后等待至时间 40，等待时间为 15 个时间单位。
来源：Table 3。实验生成 20 个超实例，覆盖不同任务规模、队伍数量、动态程度、有效时间窗动态程度和同步任务数量。
计算实验使用随机生成实例，参数校准来自与一家国家级公用事业服务商的合作。任务位置位于 25 公里乘 25 公里的矩形空间内，队伍行驶速度设为 30 公里每小时，技能集合包含 5 类技能。
结果分析
实验先比较 MIP、构造启发式和 ALNS，再扩展到大规模滚动重优化场景。MIP 使用 CPLEX 22.1.0，每次运行限时 15 分钟；ALNS 框架用 Java 实现，并通过独立调参实例做网格搜索。
来源：Table 5。小中规模实例对比了 MIP、构造启发式和 ALNS 的 TWTT、计算时间和改进幅度。
来源：Table 6。大规模滚动重优化实验报告了 CH 与 ALNS 的 TWTT、改进比例和重优化次数。
来源：Fig. 4。动态程度 δ 的变化会改变不同规模实例下的总加权吞吐时间走势。
来源：Fig. 5。有效动态程度和同步任务数量共同解释了系统难度来源，二者都会影响 TWTT。
管理启示
对上门服务平台来说，冻结期是一项运营稳定性工具。冻结期能保护已派出队伍和即将开始服务的任务，过长的冻结期会减少可调整空间，过短的冻结期会增加现场计划切换压力。
同步任务需要被单独纳入调度规则。多技能协同服务会带来等待时间，一支队伍的提前到达未必形成服务产出，线路重排需要同时考虑技能覆盖、到达时刻和共同开始时间。
来源：Table 13。预期任务准确性实验显示，预测模块质量会影响紧时间窗场景下的调度结果。
论文给出的管理含义是：动态上门服务的核心能力在于把实时重排、技能协同、冻结承诺和需求预判放进同一个滚动决策框架。
✓订单到达频率高时，需要设置明确的重优化触发规则。
✓同步任务多时，需要把等待成本纳入队伍线路评估。
✓预测模块上线前，可以用不同准确性水平做压力测试。
✓运营系统应保留冻结期机制，避免每次重排影响正在执行的现场任务。
论文：An optimization framework for a dynamic multi-skill workforce scheduling and routing problem with time windows, synchronization constraints, and anticipated tasks
作者：Onur Demiray，Doruk Tolga，Eda Yücel
期刊：Computers & Industrial Engineering
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
