移动货架仓库中面向订单拣选的货架选择方法

订单拣选是一种劳动密集型作业，占仓库运作总成本的60%~70%[1]，其效率高低关系到整个电子商务活动的成败。随着电子商务的迅速发展，电商仓库要处理的电商订单越来越多，顾客对送货时间的要求也越来越高。2020年天猫“双十一”物流订单总量超过了20亿，如此巨大的订单量及其快速及时的订单配送要求，对仓库中的订单拣选工作提出了严峻的挑战，提高电商订单拣选效率成为电商企业共同关心的一大难题。在电商高速发展与仓储拣选效率之间的矛盾日益凸显的时代下，移动货架仓库应运而生，它将传统仓库订单拣选的效率提高了2-3倍[2,3]，受到了很多电商物流企业的热烈追捧。

在移动货架仓库中(如图1)，订单的拣选需要由机器人将货架搬运至拣货台(如图2[4])，再由拣货人员将所需商品从货架上取下，放入对应的订单商品筐中。这种拣选方式有助于减少拣货人员行走距离，且提高拣选效率。当某个货架的商品拣选完成后，机器人将该货架搬回至存储区。该种仓库的每个货架可存储多种商品，每种商品又可存放于多个货架上，货架与商品之间具有多对多的复杂关系。因此有多种货架组合满足订单集合的拣货需求，所选择的货架数越多，则机器人需要搬运的货架次数也就越多。因此，如何根据货架与商品之间复杂关系，选择数量最少的货架组合，就是该种仓库订单拣选所不可逾越的一大难题。

通过查阅文献，发现与移动货架仓库中货架选择问题相关的研究包括传统仓库的拣货路径规划、可移动货架仓库的拣选任务分配与机器人路径规划、订单分批与货架调度的研究。下文针对这三方面研究分别展开综述。

在传统仓库订单拣选的相关研究中，拣货货架的选择与访问往往和拣货员的路径规划结合在一起研究，许多学者通过考虑拣选任务、拣选区域、拣选方式以及完成当前拣选任务后行进到下一拣选任务所在区域的过程，以实现整个拣选过程所耗费的时间最短等目标。其代表性的研究成果包括：杨朋[5]设计了两阶段禁忌搜索算法对货位分配和拣选路径的集成优化模型进行求解；Lu[6]介绍了一种优化动态拣货的干预式路径算法；Su[7]提出了一种应用模糊逻辑和模糊聚类算法的订单拣选路径计划程序；Bódis [8]提出一种BMA(Bacterial Memetic Algorithms)算法；Kübler[9]同时考虑储位分配、订单分批、拣选路径规划，提出一种迭代启发式算法。

可移动货架仓库的拣选任务分配与传统仓库有一定相似之处，它们拣选任务分配的对象分别是机器人和拣选人员。可移动货架仓库拣选任务分配的代表性成果有：袁瑞萍[10]对共同进化遗传算法粗粒度模型进行改进来求解AGV调度问题；张新艳[11]结合时间窗及优先级策略实现多AGV的动态无碰撞路径规划；Kuo[12]提出了一种改进的模糊蚁群算法来求解该问题；Lee[13]提出一种解耦方法来找到机器人无冲突的路径；Gharehgozli[14]针对机器人调度的问题设计自适应大邻域搜索算法。

在订单分批或调度方面，李晓杰[15]以减少货架搬运次数为优化目标，针对订单分批问题建立了聚类模型和策略评估模型；李珍萍[16]以人员拣货和AGV搬运货架成本之和极小化为目标建立了订单分批问题的数学模型；Boysen[17]将订单拣选问题拆分成订单履行顺序和货架调度顺序两个子问题，分析了系统机器人的数量配置问题；Xiang[18]以货架调度次数最少为目标提出了订单分析和货架调度的求解算法。这些文献提及了货架选择问题的重要性，但文章的侧重点并不是找到好的货架选择方案，也并未给出具体货架选择的方法。

因此本文对移动货架仓库中的货架选择问题进行研究，以所需的货架数最小化为目标，构建了数学模型，并提出一种启发式算法对大规模问题进行求解，最后，通过算例分析来验证方法的科学性和有效性。

本节通过举例来描述货架选择问题。假设SKU有四种，分别为A、B、C、D，待拣选的订单为，O1={A(2),B(3)}，表示订单1需2个A ，3个B ，O2={A(1),C(1),D(2)}；仓库中有四个货架，分别为：R1={A(5),B(2)}，表示货架1包含5个A，2个B，R2={A(3),C(3)}，R3={B(3),D(2)}，R4={A(3),B(1),C(1),D(1)}。订单O1和O2共需3个A、3个B、1个C、及2个D，针对订单拣货要求，有多种货架选择方案，分别为{R1,R3,R4}、{R2,R3}、{R1,R2,R3}，且第2个方案所需货架数最少，因此选择它为订单O1、O2提供拣货服务；若选择另两个方案，虽能满足订单拣货要求，但需移动三个货架，这样很可能降低订单的拣选效率。

综上，移动货架选择问题可描述为：某移动货架仓库中，商品种类充足，针对某一时间段内产生的一批订单，确定一个最优的货架选择方案，使得完成该批订单拣选任务所需货架数最小。因此，本文以满足给定订单集合中商品的拣选需求为约束，以所需货架数最小化为目标，建立该问题的数学模型。

建模前，对问题做出以下假设：已知待拣选的订单集合，同种SKU可存在多个货架上，且一个货架上有多种SKU；所有货架上的SKU能够满足订单的需求。由于货架在仓库中的位置并不固定，本文不考虑机器人将货架搬运到拣货台的时间，只考虑货架搬运次数。

参数描述：

O: 订单集合

S: 货架集合

P: 商品种类集合

bik: 第i个货架上第k种商品的数量，i∈S,k∈P

djk: 第j个订单对第k种商品的需求量，j∈O,k∈P

M:一个无穷大的正数

决策变量：

xijk：货架i为第j个订单中第k种商品提供拣货的商品数量，i∈S,j∈O,k∈P

yi：0-1变量：0表示货架i未被选中提供拣货服务，1表示货架i被选中，i∈S

基于上述参数设置，建立货架选择问题的数学模型如下：

式(1)目标函数是要求完成所有订单的拣货服务的货架数最小化；约束(2)表示提供拣货服务的货架商品的数量要满足订单对商品的需求；约束(3)表示提供拣货服务的货架的商品拣选数量不能超过货架所有的商品数量；约束(4)定义两个变量之间的关系。

货架选择问题具有NP-hard特性，因为它在下述假设下可转化为一类特殊的集合覆盖问题(Set Covering Problem，SCP)：每个订单订购每类商品的数量最多为1件；所有订单订购的商品种类并不相同。在这些假设下，货架选择问题就转化为一类SCP问题，即如何选择尽量少的货架(商品的集合)，才能使这些货架上的商品覆盖订单中的所有商品集合。由于SCP问题已经被证明为NP-hard问题[19]，因此货架选择问题也具有NP-hard复杂性。当问题规模较小时，可通过线性规划求解器来求解问题模型；但针对现实中的大规模问题，建立启发式算法就是一种有效的途径。

模拟退火(Simulate Anneal，SA)算法是S. Kirkpatrick于1983 年提出的一种仿生智能算法。由于该算法具有描述简单、使用灵活、运用广泛、运行效率高和较少受到初始条件约束等优点而被广泛运用于很多经典组合优化问题。该算法框架更有助于货架选择方案跳出局部最优，因此本文针对货架选择问题实现了一种改进的模拟退火算法，改进之处在于：基于移动货架仓库中面向订单拣选的货架选择模型，本文算法设计的目标是找到一个最小的货架集合来满足当前订单的拣选需求，因此，设计了一种新的启发式算法来产生初始解；在邻域操作部分，为了实现货架数的最小化、同时与模型的目标函数和约束方程保持一致，设计了能够满足当前订单拣选需求的6种local search 算子来产生新的邻域解；若邻域解的货架数少于当前解的货架数，则用邻域解替换当前解，否则按照e-∆fT的概率替换当前解，其中，∆f为邻域解与当前解的货架数之差，T为温度，每次迭代后T=αT(0<α<1)；算法从初始温度T0开始迭代，直至终止温度Tmin结束。本章详细阐述初始解产生和邻域操作方法。

本文设计了一种启发式算法生成初始解，步骤见下：

输入：该批订单需要的全部商品列表Prod及数量Demand、所在的货架列表RackLst，最优解best_solution；

Step1：计算RackLst列表中每个货架的权重

权重的计算如下：

pij: 表示货架i上商品j的数量，∀i∈RackLst，j∈Prod

sj: RackLst列表中所有货架包含商品j的总数量

sj=∑ipij∀j∈Prod(5)

wi: 表示货架i的权重

wi=∑jpijsj∀i∈RackLst(6)

Step 2：按照货架权重的大小降序排列，得到货架列表RackLst；

Step 3：将权重最大的货架添加到best_solution中，并将其从RackLst中移除；更新商品列表Prod，若商品的拣选需求得到满足，则将其从Prod中移除；

Step 4：判断Prod列表是否为空，若是，则输出初始解best_solution；否则，转Step 1。

针对邻域操作部分，设计了6种Local Search算子，每种算子都将当前解中已选择的某些货架替换为新货架。当前解中已选择的、待替换的货架集合可包含1个、2个、或3个货架，针对每种货架数量，设计算子如下：

算子1：若当前解含有货架A，且移除A后的解仍符合模型约束，则移除A；

算子2：若当前解含有货架A但不含B，且用B替换A后的解仍能满足模型约束，则用B替换A；

算子3：若当前解含有货架A和B但不含C，且用C替换A、B后的解仍能满足模型约束，则用C替换A和B；

算子4：若当前解含有货架A和B但不含C和D，且用C、D替换A、B后的解仍能满足模型约束，则用C、D替换A、B；

算子5：若当前解含有货架A、B、C但不含D和E，且用D、E替换A、B、C后的解仍能满足模型约束，则用D、E替换A、B、C；

算子6：若当前解含有货架A、B、C但不含D、E、F，且用D、E、F替换A、B、C后的解仍能满足模型约束，则用D、E、F替换A、B、C。

按下述方式设定六种算子的权重：

choose[i]：算子i被选择的次数；

count[i]：算子i被选择的情况下，当前解被更新的次数；

OperW[i]：算子i的权重。

OperW[i]=count[i]choose[i](7)

基于算子权重，在每次迭代时使用轮盘赌方法选择一种算子产生邻域解。该方式既增加了算子的随机性，又能选出效果较好的算子，来增加算法的寻优能力。

邻域操作主要分为两个阶段，第一阶段选择待替换的货架集合replaceLst：(1) 针对1个货架，从当前解中随机选择一个货架；(2) 针对2个或3个货架，采用轮盘赌选择待替换的货架集合。

第二阶段查找满足商品拣选需求的货架集合MyRack：找出移除replaceLst中货架后未满足拣选需求的商品列表UnPord，在剩余货架中按图3所示的方法查找货架集合MyRack。该方法参考Li[20]算法的思想，权重越大的货架所需要的商品种类数和商品数量越多，因此将权重较大的货架添加进来，更能满足所需商品的需求，大概率减少所需货架数。

本章首先生成不同规模的算例，然后将本文的模拟退火算法分别与Gurobi及该领域的代表性算法——大邻域搜索算法[21]进行对比，验证本文模型和算法的有效性。

根据电商订单小批次、多品种的特性，生成算例，每个算例包含订单和货架信息，订单数最大为500个，仓库中SKU数最大为5000个，货架数最大为2000个。模拟退火算法中，初始温度T0=500，温度衰减系数α=0.98，终止温度Tmin=0.01。

分别利用Gurobi和模拟退火算法(SA)对小规模算例进行求解，结果见表1。由表可见，SA算法能在更短的时间内找到Gurobi所给出的精确解；针对600个货架以上的算例，Gurobi在有限时间内找不到最优解，但SA算法仍能在几十秒之内就能找到当前最好解，这说明了SA算法的有效性和优越性。

大邻域搜索算法最早由Shaw在1998年提出，因其容易跳离局部最优，对大规模数据的求解问题具有良好的表现，而被成功运用于仓库运营管理的相关问题[21]。本文选择该算法作为对比算法，改进了文献[21]的算法使之适用于本文问题，其算法流程见图4。算法的修复算子参考了本文3.2节第二阶段查找MyRack的方法；相似性删除算子思路是：随机选择当前货架集合的一个货架，找出与其相似程度较高的货架作为下一个被删除的货架，之后在已删除的货架集合随机找一个货架，删除与其相似程度较高的货架，以此类推，直至达到删除比例；货架的相似程度采用式(8)计算而得，其中FA和FB分别表示货架A和B包含的商品种类集合。

phi（A,B）=FA∩FBFA⋃FB(8)

为保证公平性，大邻域搜索LNS算法的外层循环同样采用温度下降的方法来控制迭代次数，运行10次后记录最好解，结果见表2。在求解质量方面，在14个算例中LNS只有一个算例的结果与SA的结果一致，其余算例的结果均劣于SA算法。在运行时间方面，两种算法的差异较大，基本上保持在50%以上，说明在保证求解质量的前提下，SA效果更好。

两种算法的运行时间随算例规模而变化的趋势进一步绘制在图5中。由图可见，随着问题规模的增加，SA算法运行时间曲线的斜率要比LNS算法运行时间曲线的斜率小，说明SA算法的稳定性要优于LNS算法。

综上，针对小规模算例，SA算法能够用较少时间找到最优解；针对大规模算例，SA相较于大邻域搜索算法，在求解质量和运行时间方面，都具有较好的效果。这些结果验证了本文SA算法的有效性。

在不同的时段，顾客订单中所订购的商品结构会有很大不同。例如电商促销日，由于某些特定商品的优惠力度较大，订单中对这些商品的购买频率和数量就会增加。那么，不同订单结构如何影响货架选择方案，本节主要分析不同订单中SKU种类数、每种SKU被订购的件数对货架数及货架特点的影响，旨在给决策者提供相应的管理启示。

（1）订单中SKU种类数敏感度分析

针对200、500个订单，分析订单中SKU种类数对货架数的影响，结果见图6，订单量越大，所需要的货架数也就越多；针对相同规模的数据，所需货架数随SKU种类数的增加而增加；针对200个订单计算被选中和未被选中的货架上SKU种类数、SKU总件数，结果见图7、图8，针对相同SKU种类数，被选中的货架上SKU种类数以及SKU总件数要大于未被选中的货架。

（2）每种SKU被订购的件数敏感度分析

针对不同的订单规模分析每种SKU被订购的件数对所需货架数的影响，结果见图9，针对不同规模的订单，所需货架数会随每种SKU被订购的件数增加而增加；对结果用Excel进行线性拟合，见图10，针对500个订单的趋势线的斜率高于200个订单，说明订单量越大，所需货架数随SKU被订购的件数的变化幅度越大；针对500订单的运行结果计算被选中与未被选中的货架SKU种类数和SKU总件数，见图11、图12，针对相同每种SKU被订购的件数，被选中的货架SKU种类数和SKU总件数较于未被选中的货架要高。

综上，不同规模订单所需要的货架数随订单中SKU种类数或每种SKU被订购的件数的增加而增加，且被选中的货架上SKU种类数和SKU总件数要高于未被选中的货架，因此，应该优先选择SKU种类数多和SKU总件数多的货架来提供拣货服务，SKU种类数越多或SKU总件数越多的货架，越有利于降低所选择的货架数，使得所需要的货架越少。同时本文的模拟退火算法适用于同种SKU被存放在多个货架上，而不是将商品存放在一个货架上，而现实生活中，大部分的移动货架仓库中储位分配也不会将同种商品放在一个货架上，而是一个货架上存放多种商品，一种商品存放在多个货架上，所以本文的研究具有一定的现实意义。

本文研究了移动货架仓库中的货架选择问题，针对一批订单的拣选需求，构建了以满足订单拣选需求、所需货架数最小化的数学模型，并设计了改进的模拟退火算法，最后进行了算例实验。实验结果表明：模拟退火算法在不同规模的算例测试中，均有较好的表现，针对小规模算例，该算法能够求出最优解，且比Gurobi耗时更少；针对大规模算例，比大邻域搜索算法的求解质量更优，且耗时更少；不同规模的算例都证明了该算法的优越性。使用不同订单集合对算法进行敏感度分析，发现SKU种类数和SKU件数较多的货架更容易被选中，说明在货架选择问题上，系统优先选择这类货架，能提高仓库的拣选效率，这就为货架在仓库中的位置摆放提供了理论基础，如决策者可将SKU种类数和SKU件数较多的货架摆放在距离拣货台较近的位置上，以便减少货架在拣货时的搬运距离。

此外，本文针对已知的一批订单而进行货架选择操作。在实际中，结合未来可能的订单而进行货架的实时选择，也是一个值得研究的课题，它将作为本文下一步的研究方向。