链上镖师 / Chain Biaoshi
EJOR|顺序拣选站货箱调度：订单-货箱-机器人联合优化
用集成 MILP 与 DRL-HALNS 协调电商仓内订单分配、货箱流转和 ACR 取送节奏
这篇 EJOR 论文把顺序拣选站 MTS/RS 中的订单分配、货箱进站和 ACR 取送放进同一个调度问题，并用 DRL-HALNS 在大规模算例上把 makespan 最高降低 71.46%。
- 01：研究对象是带顺序拣选站和输送线复用货箱的多货箱存取系统，核心瓶颈来自订单、货箱和机器人之间的时间耦合。
- 02：论文建立集成 MILP，覆盖订单分配与排序、货箱分配与排序、ACR 任务分配与调度，目标是最小化订单最大完成时间。
- 03：求解方法用 PPO 训练的策略网络选择 ALNS 破坏-修复算子，在保证可行性的邻域搜索中提升解质量和计算效率。
- 04：敏感性结果显示，系统效率对货箱数量更敏感，机器人增加有明显边际递减，拣选站数量增加不稳定改善 makespan。
研究背景
电商仓库同时面对用工成本上升、交付时限收紧和小批量高频订单增加。订单拣选和物料搬运中的行走、取放、等待时间会直接推高履约周期，因此移动机器人与自动化输送线逐渐成为大型履约中心的基础设施。
顺序拣选站 MTS/RS 的系统形态，展示 ACR、货箱与输送线连接的物理场景。来源：Fig. 1
多货箱存取系统允许机器人一次搬运多个货箱。论文关注的顺序拣选站配置把多个拣选站接在同一条分拣输送线上，货箱被送入输送线后可以依次服务多个站点，减少重复回库和重复取箱。
顺序拣选站与离散拣选站的 MTS/RS 对比，突出输送线共享货箱带来的协同调度问题。来源：Fig. 2
核心问题
在这种系统中，订单先被分配到拣选站，ACR 从存储区取出相关货箱并送到输送线入口，货箱沿输送线依次经过各站。若该站订单需要货箱中的 SKU，货箱进入站点拣选；若没有需求，货箱直接通过。
01订单层：决定订单分配到哪个拣选站，以及同一站内的执行顺序。
02货箱层：决定哪些货箱进入输送线、何时释放，以及在哪些站点停靠拣选。
03机器人层：决定 ACR 的取箱、投放、出站回收和回库任务，满足载重、先后关系和时间约束。
论文把问题界定为订单、货箱、ACR 三类资源的联合调度，目标是最小化订单最大完成时间，也就是让一波订单尽快全部完成。
方法框架
论文先用集成 MILP 描述系统。模型把货箱生命周期拆成五段流程：订单入站、ACR 取送到入口、输送线通过各拣选站、出口回收并回库、订单完成离站。五段流程共同约束时间、服务、排队和机器人路径。
顺序拣选站 MTS/RS 的货箱流转流程，覆盖订单分配、ACR 投放、输送线拣选与回库。来源：Fig. 3
1Flow 1：订单分配到拣选站，并受站点同时处理订单数约束。
2Flow 2：ACR 从存储区取货箱，送到输送线入口并决定释放时间。
3Flow 3：货箱沿顺序站点流动，只在存在订单需求的站点停靠。
4Flow 4：ACR 在出口取回货箱并送回存储区。
5Flow 5：订单在所需货箱全部完成拣选后离站。
精确模型规模随订单数、站点数、货箱数和机器人数量快速增长。论文因此设计 DRL-HALNS，把可行解拆成 ACR 路径部分和订单-站点分配部分，再用破坏-修复邻域搜索持续改进。
DRL-HALNS 调度框架，连接初始解、邻域搜索、强化学习选算子和模拟退火接受机制。来源：Fig. 4
案例或实验设置
数值实验按小、中、大三类实例生成，每个实例由仓库长宽块数、所需货箱数、待处理订单数、ACR 数量和拣选站数量定义。MILP 用 Gurobi 10.0.1 求解，DRL-HALNS 在 Windows、2.90 GHz CPU、16 GB 内存环境下测试。
小、中、大规模实验实例设置，列出仓库尺寸、货箱数、订单数、机器人数和站点数。来源：Table 3
小规模实例从 2 到 18 个货箱、3 到 9 个订单展开，中等规模实例扩展到 20 到 60 个货箱、10 到 50 个订单，大规模实例达到 60 到 220 个货箱、50 到 130 个订单，用来检验模型和算法的可扩展性。
结果分析
在小规模实例上，Gurobi 可作为精确求解参照。表 4 显示，DRL-HALNS 在全部 90 次运行中都返回可行解，平均用时 22.69 秒；Gurobi 平均用时 1370.04 秒，且只在 29 次运行中取得最优解。
小规模实例中 Gurobi 与 DRL-HALNS 的目标值、求解时间和最优次数对比。来源：Table 4
大规模相对规则法最高改善
71.46%
III-1 实例中，DRL-HALNS 相对三阶段规则法的 makespan 改善幅度。
大规模相对贪心法最高改善
66.97%
III-1 实例中，DRL-HALNS 相对三阶段贪心法的 makespan 改善幅度。
大规模实例中 DRL-HALNS、规则法和贪心法的对比结果，平均改善幅度分别为 54.53% 和 44.85%。来源：Table 7
ALNS 与 DRL-HALNS 的性能对比，显示强化学习选算子带来的搜索效率提升。来源：Fig. 6
管理启示
敏感性分析显示，仓库长度和宽度存在交互影响。长度增加会提高平均完工时间，因为 Flow 2 和 Flow 4 中 ACR 取送与回库周期被拉长；在固定长度下，宽度对 makespan 的影响呈非单调变化。
不同仓库宽度和长度下的平均完工时间，用于解释布局参数对系统绩效的影响。来源：Fig. 7
论文还发现，系统效率对货箱数量比对订单数量更敏感。货箱增加会带来更多 SKU、更多取送任务、更多站点处理和等待；在货箱集合固定时，订单数量变化主要重新分配完成时间，对最后完成时刻影响有限。
订单、货箱、机器人和站点数量变化下的平均完工时间，支撑货箱量、机器人边际收益和站点配置建议。来源：Fig. 8
对仓库执行系统来说，顺序拣选站的优化重点应放在货箱释放节奏、ACR 取送衔接和站点停靠顺序上。增加机器人在小车队阶段收益明显，达到一定规模后，剩余延迟更多来自货箱复用和输送线时序。
论文：Deep reinforcement learning for order-tote-robot coordination in multi-tote storage and retrieval systems with sequential picking stations
作者：Yuexin Kang，Jie Shao，Mingzhe Li，Peng Yang，Rui Chen
期刊：European Journal of Operational Research
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
