基于大邻域搜索算法的储位分配研究

曹 孟，杨 健

(安徽理工大学，安徽 淮南 232001)

0 引 言

在物流各环节中，订单拣选成本占总成本的50%～70%，无论是“人到货”仓库还是“货到人”仓库，订单拣选作业都需要从货架上拣选出订单所需要的商品[1]，在这个过程中，合理的储位分配方式可以减少拣选作业的拣选距离和拣选时间，降低订单拣选成本，提高订单的拣选效率，因此储位分配问题的研究对于仓库实际作业有着重要意义。

学者们在货位分配问题上作了深入的研究。何李等[2]考虑货物重量以及出入库频率来进行货架区域划分，建立仿真模型，以指令内最小化单载具堆垛机运行时间为研究目标，设计了一种两阶段狼群算法对其进行优化。杨玮等[3]以最小化堆垛机行程时间为目标，提出货位分配与作业调度集成优化方法，设计了双层遗传算法对模型进行求解。针对基于AGV的自动化立体仓库储位分配问题，胡祥培等[4]以提高货架商品间关联性为目标，提出“关联网络构建→关联网络分析→关联网络聚类”的三阶段货位分配方法，来快速高效生成储位分配方案，Zhongqiang Ma[5]等以货架上商品关联度最大为目标，同时考虑商品的分类和商品之间的关联性，提出了一种自适应模拟退火变邻域搜索算法来解决储位分配的问题。

现有针对基于AGV的自动化无人仓库储位分配问题的研究[6-9]大多都假设仓库的初始状态是空的，而现实中这种情况并不多见，更为实际的问题是仓库的初始状态非空，即仓库处于补货状态，而针对这种情况的研究并不多，因此本文将研究仓库初始状态非空时的储位分配问题。

1 问题描述

假设某自动化无人仓库中共存储S种商品，仓库中有M个货架，每个货架上有P个储位，每个储位仅存放一种商品，商品存储方式为分散存储，即一种商品可以存放在多个货架上，每种商品需要占用的储位数已知，在某个补货阶段，需要将一定量的商品上架到货架上，考虑如何合理规划商品存放位置，减少商品的拣选成本。

由于现实问题较为复杂，涉及诸多方面的优化问题，为了简化问题，作出以下假设：

(1)订单的拣选方式为按订单拣选。

(2)历史订单信息是已知的，在未来一段时间内，订单结构几乎不会发生改变，这个假设保证了商品之间的关联性是稳定的。

(3)每个储位上存储的商品数量满足一个订单中对该商品的需求。

(4)不考虑缺货情况。

(5)每种商品可以放在多个货架的多个储位上，每个储位上只能存放一种商品。

2 数学模型构建

2.1 基本符号

为建立上述问题的数学模型，定义如下参数符号，如表1所示。

表1 参数符号

定义决策变量：

xjm表示待补货商品j在货架m上占用的储伴数。

2.2 商品关联度矩阵R的定义

Oi表示包含商品i的订单数，Oj表示包含商品j的订单数，Oij表示同时包含商品i和j的订单数，分别统计一定时期内的Oi、Oj、Oij，如式(1)和式(2)所示。

同时rij=rji，当i=j时rij=0，则R为：

2.3 模型构建

目标函数如式(3)所示。

(3)

约束条件如式(4)～式(10)。

目标函数式(3)表示对所有货架上存放的商品之间的关联度之和求最大，从第一项到第三项分别表示同一货架上原有商品之间的关联度之和、补货商品与货架上已有商品之间的关联度之和、货架上补货商品之间的关联度之和；约束条件式(4)表示存放在每个货架上的空储位数全部被待补货商品所占用；约束条件式(5)确保待补货商品j实际占用的总储位数等于商品j需要的储位数；约束条件式(6)表示如果待补货商品j被放到第m个货架上，那么它占据的储位数小于等于货架m的空余储位数Qm；约束条件式(7)表示如果待补货商品j被放到第m个货架上，那么商品j占用的储位数量大于等于1；约束条件式(8)表示每种补货商品至少需要存放到一个货架上；约束条件式(9)和式(10)为决策变量取值约束。

3 求解算法设计

对于小规模的货位分配问题可以直接求得问题的精确解，对于大规模的问题来说，精确解很难求得，或者耗时很久，学者们大都是设计启发式算法进行求解，在这里结合以上模型设计基于大邻域搜索的两阶段启发式算法。大邻域搜索算法(LNS)是由变邻域搜索算法演变而来，对比变邻域搜索算法，它具有搜索范围广，所得局部最优解质量好等特点，但耗时也会相对较长。算法共分为两大步骤：首先在算法开始时利用设计的贪婪算法对问题求得初始解；然后基于贪婪算法所求的解，利用大邻域搜索算法对解进行迭代，求得本问题的最终解，即储位分配方案。

3.1 基于关联度的贪婪算法

算法的过程就是将待补货商品不断放置到货架上，依次将与货架上商品关联度最大的商品放置到货架上，使得总关联度之和最大。贪婪算法的具体步骤：

(1)输入：补货前货架上存放的商品信息矩阵和货架上原有商品集合、待补货商品集合和待补货商品需要占据的储位数、商品的关联度矩阵R。

①第1步：判断待补货商品集合是否为空，若不为空继续，否则结束。

②第2步：对货架上各个商品与待补货商品之间的关联度进行排序，寻找关联度最大的一对商品，这对商品包括一种货架上的商品i，和一种待补货商品j，统计包含商品i且有空余储位的货架数t，根据t与商品j需要的储位数Dj的大小关系分为两种情况为商品j分配储位。

第一种情况若t大于等于Dj，则将商品j随机分配到这t个货架上，每个货架上占据一个储位。

第二种情况t小于Dj，则先在这t个货架上各分配一个商品j，此时商品j所需的储位还没有满足，继续将商品j随机分配到有空余储位的货架上，每个货架上依然占据一个储位。

③第3步：更新货架上商品信息矩阵、货架上商品集合、待补货商品集合，转第1步。

(2)输出：储位分配结果X0，目标函数值Z0。

3.2 大邻域搜索算法

大邻域搜索算法属于邻域搜索算法的一种，最早由 Shaw[10]于1998 年提出。该算法的基本框架和其他邻域搜索算法类似，即先产生一个初始解，然后对解不断进行破坏与修复以提高解的质量，直至得到满意的解为止。具体而言，大邻域搜索算法的一次迭代由两部分构成：第一步对当前解进行破坏，在本文中破坏表示将商品从货架上移除，并对当前解进行拆解(如从路径中删除若干个点)；第二步为对破坏后的解进行重构生成新解，在本文中表示将商品插入到货架上。大邻域搜索算法的一般步骤如下：

(1)输入初始解X。

(2)令当前最优解Xb=X。

(3)判断算法终止条件是否满足。如果是，输出当前最优解Xb并结束该算法；否则继续。

(4)对当前解X进行破坏，得到解Xd。

(5)对解Xd进行修复，得到解Xr。

(6)比较Xr与Xb的目标函数值，如果Xr比Xb更优，则取当前最优解Xb=Xr，否则继续。

(7)转至步骤(3)。

本文设计三种移除算子和三种插入算子，由此共有9种组合的大邻域搜索。

3.2.1 移除算子

(1)最差移除(Worst Removal ，WR)

最差移除是指移除货架上贡献度最小的补货商品，具体过程如下：首先计算货架上各个补货商品的贡献度，商品i的贡献度的定义为Ci=f-f-i，其中f为货架上原有商品关联度之和，f-i为该货架去掉商品i的关联度之和，该等式等价于商品i与货架上其他商品关联度之和；然后计算所有货架上补货商品的贡献度之后，将这些商品按照贡献度大小进行排序，引入P1≥1，生成随机数rand，移除上述商品序列中的第(rand^P1*商品序列长度)个商品。重复此步骤，直到移除商品个数满足需要移除商品的数量。P1的大小用来控制移除商品过程中的随机性，P1越大代表随机性越小，反之随机性越大。

(2)相似移除(Shaw Removal ，SR)

相似移除算子来源于Shaw，本文中移除的原则依然是相似性，只是在该算子最初被提出时是用来解决车辆路径问题，对它进行了改动，以适用于储位分配问题，并直接用商品之间的关联度来表示商品相似性的度量。具体过程如下：首先建立货架上补货商品的集合n1，随机从n1中选择一个商品放入移除商品集合中n2；然后重复：从n2中随机选择一种商品i，按照货架上补货商品与商品i的关联度由大到小排序，移除上述商品序列中的第(rand^P2*商品序列长度)个商品。重复此步骤，直到移除商品个数满足需要移除商品的数量。与最差移除相似的是引入P2≥1，增加选择过程带来一定随机性，P2越大代表随机性越小，反之随机性越大。

(3)随机移除(Random Removal ，RR)

随机移除是指从货架上的补货商品上随机移除n个商品，这种移除可以通过改变相似移除和最差移除中的P1、P2来实现，当P1或者P2的值为1时这两种移除方式变为随机移除。

3.2.2 插入算子

(1)贪婪插入(Greedy Insertion ，GI)该插入算子与初始解生成的方式相似，是在插入过程中依次选择插入贡献最大的商品和位置。具体就是计算每种商品插入到有空余储位的货架上后该货架的平均贡献，以此为依据，选择平均贡献最大的商品与货架，将该商品插入到该货架上。其中商品i放置在货架m上的平均贡献Ci，m定义如式(11)所示。

(11)

其中，f为将商品i插入到货架m上之后该货架的相似度之和；f-i为商品i未插入货架m上时的相似度之和；N为未插入商品i时货架上原有商品的数量。

该表达式代表了将商品i插入货架m后货架m相似度增加的平均值。

(2)随机插入(Random Insertion ，RI)

随机插入是指在插入过程中随机选择被移除的商品随机放入空余储位上，该方式可以保证插入的多样性。

(3)最大后悔插入(Regret Insertion ，ReI)

最大后悔插入是对贪婪插入算子的改进，在最大后悔插入中，选择插入商品时同时考虑了该商品插入贡献最大的货架和插入贡献第二大的货架，以此来避免贪婪插入的短视问题。在最大后悔插入中首先计算商品i在每个有空余储位的货架上的插入贡献Ci，m，其中在货架m1上的插入贡献最大为Ci，m1，在货架m2上的插入贡献Ci，m2为第二大插入贡献，则商品i的后悔平均插入贡献值RCi如式(12)所示。

RCi=Ci，m1-Ci，m2

(12)

计算完每种商品的后悔值后取后悔值最大的商品j，将商品j插入到插入贡献最大的货架上。

4 模拟计算与结果分析

4.1 算例和参数设置

通过计算机随机生成三种规模的算例，验证上述组合算法表现的优异性，三种规模算例的区别在于商品种类、储位数、货架数的不同，小规模算例分为五种情况：商品种类(S)/储位数(P)/货架数(M)∈{10/5/10，10/5/20，10/5/30，20/5/10，30/5/30}；中等规模算例分为四种情况：商品种类(S)/储位数(P)/货架数(M)∈{30/5/25，40/5/40，50/5/50，60/5/50}，大规模算例分为三种情况：商品种类(S)/储位数(P)/货架数(M)∈{200/10/80，300/10/120，500/10/180}。

算法迭代次数设置为500次，P1，P2=10，在进行移除算子操作时移除商品的个数由移除率决定，本文设置移除率为0.8。所有实验均在搭载Intel(R)Core(TM)2.30GHz i5-8300H CPU 计算机，MatLab R2019(a)编程环境下编程运行。

4.2 结果分析

对于小规模算例，实验结果如表2所示(其中括号中数字为目标函数值的排名，1为最优，2次之，以此类推，表格只标记出排名前五的函数值，对于中等规模算例和大规模算例结果表格类似)。从目标函数值上来看RR-RI、RR-GI、RR-ReI、WR-GI、WR-ReI组合的大邻域搜索算法表现优于其他四种组合的邻域搜索算法，其中WR-ReI的大邻域搜索在五个算例中排名均位于前五，性能比较稳定，WR-RI的大邻域搜索表现最差，在五个算例中均未能排列前五。从时间上看，在五个算例中WR-RI、WR-GI 、WR-ReI、SR-GI、SR-ReI组合的大邻域搜索算法所耗时间相差不大但都明显大于RR-RI、RR-GI、RR-ReI、SR-RI组合的大邻域搜索算法。

表2 小规模算例结果比较

对于中等规模算例，实验结果如表3所示，各组合的大邻域搜索表现与小规模算例中的表现类似，从目标函数值上看，RR-RI、RR-GI、RR-ReI、WR-GI、WR-ReI组合的大邻域搜索算法表现优于其他四种组合的邻域搜索算法，这五种组合的算法在每个算例中均位于前五名，其中WR-ReI的大邻域搜索在四个算例中有三次排名第一，一次排名第二，性能比较优越，而其他四种组合的算法均未进入前五名。从时间上看，在四个算例中WR-RI、WR-GI 、WR-ReI、SR-GI、SR-ReI组合的大邻域搜索算法所耗时间相差不大但都明显大于RR-RI、RR-GI、RR-ReI、SR-RI组合的大邻域搜索算法。

表3 中等规模算例结果比较

对于大规模算例，实验结果如表4所示，WR-GI、WR-ReI、SR-GI、SR-ReI均不能在有限时间(1200s)内完成迭代，从目标函数值上来看RR-ReI组合算法最优，在三个算例中均排名第一，RR-GI组合算法次之，WR-RI、SR-RI组合的算法表现较差；从时间上看，在三个算例中所耗时间排序为SR-RI> WR-RI> RR-GI> RR-ReI> RR-RI。

表4 大规模算例结果比较

为了分析贪婪算法求得初始解的质量和大邻域搜索对解优化的效果，本节选取前文所述算例E1，E9，E12进行模拟计算，分别计算算例随机分配时的函数值，贪婪算法所得函数值，与大邻域搜索算法进行对比，实验结果如表5所示。

表5 RR-ReI组合算法性能分析

由表5可知贪婪分配所得初始解对比随机分配情况的解均有所改进，最高达到了13.12%，大邻域搜索的解相对贪婪分配所得的解也至少提升了33.10%，大邻域搜索的解相对随机分配所得的解至少提升了38.05%。可见大邻域搜索算法可有效提升贪婪分配初始解的质量，相对于随机分配优化效果更好。

5 结 语

本文研究了自动化无人仓库中的储位分配问题，并且针对补货阶段的储位分配问题，拓展了以往研究的深度。首先建立了一个混合整数模型，目标是货架上原有商品之间、补货商品之间、原有商品与补货商品之间的关联度和的最大化，设计了一种两阶段算法，第一阶段使用贪婪算法求得初始解，第二阶段使用大邻域搜索算法；然后设计了三种移除算子和三种插入算子，九种组合的算法；最后利用模拟算例对这九种算法进行评估。结果表明RR-ReI组合算法在所有算法中表现最优，在大规模算例中目标函数值最大，同时时间在3s以内，RR-ReI组合算法可以有效提升初始解的质量，最低可提升33.1%，相对于随机分配可提升38.05%，验证了所提算法的优越性。