链上镖师 / Chain Biaoshi
EJOR|分散存储下订单拣选：异质拣选员与订单行拆分的批次—库位—路径联合优化
把订单批处理、拣选员选择、库位分配和路线规划放进同一个多目标模型
论文将订单批处理、批次排序、拣选员选择、库位选择、订单行拆分和路径规划整合为一个联合优化问题，在总拣选时间、完工时间和订单延迟之间进行协调。
- 01：研究对象是采用分散存储的人工拣选仓库，SKU可分布在多个库位，单个订单行可按需求拆分到多个库位。
- 02：模型同时处理订单分批、批次分配、批次排序、拣选员选择、库位选择和拣选路线。
- 03：ALNS-VNS-DP结合自适应大邻域搜索、变邻域搜索和动态规划求解大规模实例。
- 04：单位需求场景中，联合优化相对顺序优化使四项目标改善1.05%至20.4%。
- 05：实验显示，存储分散度、拣选员速度组合和批次规模都会改变仓库绩效。
仓库里需要同时决定哪些拣选动作？
在电商仓库中，订单往往带有交付时限，SKU又可能分散在多个存储位置。管理者需要决定哪些订单组成同一批次、批次交给哪名拣选员、批次按照什么顺序执行、每个SKU从哪些库位取货，以及拣选员如何往返仓库。拣选员的行走速度和取货速度存在差异，订单行拆分也会改变库位访问和路线长度。
订单拣选联合决策的小规模数值示例（来源：Fig. 1）
论文把上述决策定义为JOSPLRP，即订单批处理、批次排序、拣选员选择、库位选择、订单行拆分与路线规划的联合问题。
从订单批次到库位路线的联合模型
JOSPLRP以混合整数规划表达。订单必须分配到批次，批次需要分配给拣选员及其执行位置，SKU需求由可用库位共同满足，库位库存不能被超额使用，路线需要从仓库出发点经过被选库位后返回。模型允许订单行在多个库位之间拆分，能够描述分散存储和有限库位库存共同作用的场景。
01订单层：将具有交付时限的订单组合为容量受限的批次。
02人员层：依据拣选员的行走速度与取货速度分配批次并排序。
03库存层：从多个SKU库位中选择取货位置，满足批次需求与库位库存约束。
04路径层：为每个批次规划访问库位的路线并计算处理时间。
优化目标
3项
单位需求改进
1.05%–20.4%
联合模型的价值体现在决策之间的联动：批次组合会改变SKU需求，库位选择会改变路线，拣选员速度会改变批次完成时刻，交付时限会影响批次排序。
ALNS-VNS-DP如何搜索高质量方案
论文提出ALNS-VNS-DP求解大规模JOSPLRP。算法先用改进种子算法生成初始解，再通过破坏与修复操作持续调整订单批次、批次排序、拣选员分配和库位选择。每经过一段迭代，算子权重与选择概率依据历史表现更新；动态规划用于计算候选方案的最短路线，变邻域搜索用于进一步扰动和改进当前最优解。
ALNS-VNS-DP整体求解框架（来源：Fig. 2）
1改进种子算法：生成初始批次、拣选员分配和路线。
2自适应大邻域搜索：选择破坏算子移除部分决策，再用修复算子重建方案。
3变邻域搜索：围绕批处理、排序、拣选员和库位选择改进当前解。
4动态规划：计算每个候选批次路线的最短路径并评价目标值。
5终止输出：返回满足终止条件时的最佳方案。
算法复杂度被表述为O(iter²·(n⁵+rn⁴))，其中n是所有批次需要 traversed 的最大库位数，r是巷道数量，iter是最大迭代次数。
四类搜索算子怎样改动拣选方案
搜索过程围绕四类决策设计算子。订单批处理算子交换不同批次中的订单，排序算子调整同一拣选员或不同拣选员之间的批次位置，拣选员选择算子移除并重新插入批次对应的拣选员，库位选择算子依据随机规则、距离、仓库出发点和服务加权距离移除或补充访问库位。
破坏与修复算子汇总（来源：Table 3）
✓订单批处理：在容量约束内交换订单，改变批次构成。
✓拣选员选择：随机插入或按速度规则插入被移除的批次。
✓库位选择：跟踪未完成SKU需求和库位库存，逐步补足可行取货位置。
✓路线评价：使用动态规划计算访问选定库位的最短路线。
实例覆盖哪些仓储条件
实验实例覆盖小、中、大三类规模。订单数量取10至60，SKU数量取10、60、80或180，存储位置数量取5、10、20或30，拣选员数量取3至6，批次数量取3至30，购物车容量取2至12个订单。单位需求场景中每条订单行需求为1，一般需求场景采用来自Instacart订单的多种需求量，SKU分散水平取1至6。
实验实例生成参数（来源：Table 4）
合作仓库实际布局示意（来源：Fig. A.1）
仓库空间采用矩形布局和足够宽的巷道，允许拣选员相互通过。实验同时设置不同的行走速度与拣选速度，旅行速度范围为0.4至1.2米每秒，单件SKU取货时间范围为5至12秒。
分散存储、速度与批次规模的敏感性
敏感性实验分别改变SKU的存储分散程度、拣选员行走与取货速度组合、订单批次规模。结果图显示，存储结构、人员能力和批次组织会同步影响总拣选时间、完工时间、订单延迟和综合目标。分散存储提供了库位选择空间，拣选员速度差异会放大批次分配与排序的重要性，批次规模需要在路线效率和交付时限之间取得匹配。
存储分散程度对JOSPLRP目标值的影响（来源：Fig. 3）
拣选员速度组合对拣选效率的影响（来源：Fig. 4）
批次规模对订单延迟和完工时间的影响（来源：Fig. 5）
在低速与高速拣选员场景之间比较时，ALNS-VNS-DP的订单延迟目标降幅为96.01%；顺序优化方法对应降幅为76.05%。
拣选员选择与复杂需求下的结果
算法对照实验将ALNS-VNS-DP与Gurobi、顺序优化方法以及简化问题的先进方法比较。ALNS-VNS-DP在解质量和计算时间上保持竞争力，在总拣选时间、完工时间、订单延迟和综合目标的小规模对照中分别取得11/16、10/16、6/16和5/16个实例的最优解。Gurobi在订单延迟或综合目标下的部分大规模场景中未找到可行解。
不同拣选员选择策略的拣选效率比较（来源：Fig. 6）
每个SKU的存储位置数量对拣选效率的影响（来源：Fig. 7）
一般需求场景下总拣选时间的算法对比（来源：Table K.1）
一般需求和订单行拆分实验把有限库位库存、多单位需求与订单行拆分纳入评价，补充检验了方法在复杂订单结构下的总拣选时间表现。
模型适用条件与研究边界
论文假设仓库为矩形布局，巷道足够宽，拣选员可以相互通过；每个SKU的总库存足以满足全部订单需求；所有拣选员的购物车准备时间相同且为常数；拣选员具有不同的行走速度和取货速度；订单行可在单个库位完成，也可拆分到多个库位；模型设置一个仓库出发点。
- 模型未覆盖库存不足导致的缺货决策。
- 模型未报告多出发点、巷道拥堵、拣选员相互阻塞等情形。
- 模型未报告订单取消、动态到达、设备故障和实时人力变动条件。
- 涉及个体拣选员数据时，论文讨论了数据掩码与隐私合规背景，具体合规实施方案未在模型中展开。
该方法适合具有分散存储、异质拣选员、交付时限和批次拣选流程的人工仓库。应用到库存不足、动态订单、拥堵或多出发点场景时，需要重新检验模型约束、路线计算和实验参数。
论文：Multi-objective performance optimization for picker-to-parts order picking with heterogeneous pickers, scattered storage, and order line splitting
作者：Zhongqiang Ma，René de Koster，Debjit Roy，Guohua Wu
期刊：European Journal of Operational Research
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
