面向存储空间受限的分拣系统内多类型存储单元数量配置

李 靖，陈庆新，毛 宁

(广东工业大学 广东省计算机集成制造重点实验室，广东 广州 510006)

为提高大规模板式家具的生产加工效率，往往将多个订单组批生产，即一个生产批次中包含若干个订单，每个订单又包含了不同尺寸类型不同数量的板材。在订单组批生产加工完成后，需要按订单分拣板材，再打包交付客户[1-2]。这就意味着，需要分拣系统来改变板材的生产顺序和打包顺序，为此需要在分拣系统中设置一定数量的板材存储单元。由于存储单元是围绕着定点机械手设置的，因机械手的活动范围有限，导致总体存储空间受到限制。如果这些存储单元的尺寸相同，会浪费存储空间(小尺寸的板材占用大尺寸的存储空间)，使得有限空间内存储单元的数量较少，无法满足生产需求。另一方面，鉴于生产批次中订单情况的不确定性，设置不同数量不同尺寸的存储单元，虽然能够有效地利用存储空间，但却存在着较大尺寸的板材偶尔会出现无法存放的风险。针对这一问题，本文考虑生产批次订单情况的不确定性，研究在一定风险(大尺寸板材无法存储的概率) 约束条件下，优化多种尺寸存储单元的数量配置，提高分拣系统有限存储空间的利用率。

国内外关于分拣系统内存储单元尺寸和数量配置的研究中，鲜有关于多尺寸种类存储单元的文献。关于单一类型存储单元的数量配置问题，文献[3-8]研究单一类型货位区域分类对需求存储空间的影响，认为更多的货位区域分类降低货位共享性，导致总的存储单元数量增加，所需的总的存储空间增加。赖明勇等[9]研究高层货架最佳货格的整数规划模型，使得建设费用与运行费用之和最低。关于单一类型存储单元的尺寸和货架布局问题，马文凯等[10]采用优化算法得到最优的系统配置(层、排、列) 使得系统成本最少。张欢欢[11]探讨自动化仓库规划设计中货架最佳高度和长度，给出了货位尺寸计算模型和仓库的布局方法。Lee等[12]提出可以根据货物的体积对货架标准货位尺寸进行相应改变的方法，以提高货架的空间使用效率。

上述文献针对立体仓库的存储单元数量配置问题作了一定研究，但均基于单一尺寸类型货位，而单一类型货位对于多尺寸货物会造成存储空间较大的浪费，导致货位数量不足，无法满足实际需求。为此，本文构建一种多尺寸类型存储单元的数量配置模型，为有限存储空间下货位数量配置提供决策指导。

1 模型构建

1.1 问题描述

版式家具分拣系统由多个机械手分拣单元构成。如图1所示，多个订单多种尺寸的板材经传送带无序到达分拣单元，机械手从传送带上抓取板材，放入货架。当货架内某类订单板材完整时，则将这个订单内板材从货架中取出，实现货物按订单的有序出库。但因机械手的活动范围有限，导致总体存储空间受到限制。因此，为了提高存储空间的利用率，货架内多尺寸类存储单元的数量配置成为值得研究的问题。

图1 单批次货物进出分拣系统示意图Figure 1 Schematic diagram of a single batch of goods in and out of the sorting system

模型假设如下。

1) 货物的几何形状为长方体，总的货物类数服从随机分布，各类货物的长、宽、高服从随机分布，单个货位存放一个货物。货架内货位的几何形状也为长方体。

2) 单个批次有随机数量的订单，单个订单内某类尺寸货物的数量服从随机整数分布。

3) 同类货物在不同订单的数量服从独立同分布，单个订单内不同类货物的数量相互独立。

4) 货物入库顺序：批次内货物按随机顺序逐个入库，入库时间间隔服从指数分布x～E(λ)，上一个批次未开始出库之前，下一个批次不入库(即货架内最多不超过两个批次) 。

5) 货物出库顺序与触发机制：货架内某个订单到齐后，订单内货物按随机顺序逐个出库。出库时间间隔服从同一指数分布x～E(λ)。

6) 入库货位分配策略：在货架当前可供存放且其中体积最小的空余货位中随机分配。

7) 货物在出入库过程中，认为线体传输能力与机械手搬运能力不是瓶颈，足够满足以上假设的货物出入库的时间间隔。

8) 本文不考虑多尺寸类货位构成的货架布局问题。

1.2 模型分析

1.2.1 变量与符号

变量与符号如表1所示。

1.2.2 基于正态分布的数量配置

本文基于正态分布给出了各类存储单元数量配置的初步计算结果，并引入“出现较大尺寸货物无法存储的概率不超过5%的风险”(存储单元数量配置满足不爆仓率95%～100%之间) 的概念。入库货位分配策略为：在当前可供存放且其中体积最小的空余货位中随机分配。假设各类货位数量无限大，即不考虑货位类之间借用的情况下，各类存储单元总是会优先存储某几类货物。所以计算任意几类尺寸类型货物数量之和分布是配置各类存储单元数量的先决条件。因为第i类尺寸类型货物在第k个订单的数量Xik服从独立同分布，由中心极限定理，则一定数量订单组成的单个批次内任意几类尺寸类型货物数量和近似服从正态分布，期望和方差的理论值分别为

以上计算得到静止状态下单个批次内任意几类货物数量之和分布。然而，并不适用于出入库时任意几类货物数量之和分布。若分拣系统内最多不允许超过b个 完整批次，当批次数大于b时，暂停货物入库过程(如果对入库过程不加控制，由于出入库相邻货物时间服从同一指数分布，即出入库速度相等，而入库过程是连续的，出库过程是非连续的，必然会造成分拣系统内货物数量随着时间持续增长) 。因有单个批次货物数量95%概率小于E(X)+1.96D(X)，则在所有批次货物数量均为E(X)+1.96D(X)的连续出入库时，任意几类货物数量之和近似实际过程中的上限。在相邻两个批次的连续出入库过程中，后一个批次的入库完成时间段内，前一个批次的出库数量服从u=E(X)+1.96D(X)的泊松分布(相邻货物时间间隔服从指数分布，则单位时间货物数量服从泊松分布) 。当u达到一定值时，即近似服从N(u,u)正态分布，前一个批次货物出库数量大于任意数字a的单次概率计算如下。

当分拣系统内最多不允许超过b个完整批次时，给定任一数字c，则

由式(4) 可计算出入库过程中任意几类货物峰值的概率分布。当b=2时，c=u2+1.96u20.5，即在货物出入库过程中，当货架内最多不超过两个批次时，

即各类存储单元数量配置为E(X)+1.96D(X)+1.96(E(X)+1.96D(X))0.5时，各类货位的数量配置大于所存储某几类货物峰值的概率介于95%到100%之间，确保出现较大尺寸货物无法存储的风险低于5%。

1.2.3 考虑缓存下的数量配置减少

以上计算得到各类货位的数量配置在95%的概率上大于所存储某几类货物的峰值。然而由于不同存储单元类内的货物峰值出现时间不一，不同存储单元类之间在入库过程中可以彼此借用、缓存，以减少数量配置。当一类货位的长、宽、高均小于另一类货位的长、宽、高时，称这两类货位之间存在包容关系。在货物出入库过程中，当小货位数量不足时，大货位可以借用给小货位存放货物，大货位可称为小货位的缓存货位。依据缓存货位的体积大小比较可得到各类货位的各级缓存货位，某类货位的各级缓存货位两两之间并不一定具有包容关系。假设配置了10类货位，各类货位的缓存关系如图2所示，第10类货位是所有货位类的最高级缓存货位类。考虑缓存后，对只出不进的存储单元类的集合，有数量配置的减少，对只进不出的存储单元类的集合，有数量配置的最低要求。实现步骤如下。

图2 各类存储单元缓存关系图Figure 2 Buffer relationship diagram of various storage units

步骤1得到矩阵HWJS。当第i类货物可被第j类存储单元存储时，xij=1，否则xij=0。jmax=imax。

步骤2得到矩阵HWJS′。当HWJS的 行数不变，取部分列数。

步骤3得到矩阵HWJS′′。保留HWJS′矩阵各行等于1的列中体积最小存储单元的值，此行对应的其余列的值全部为0。

步骤4得到矩阵HWJS′′′。对HWJS′矩阵各行等于1的列中，按存储单元体积从小到大排序。

步骤5得到只出不进存储单元类的集合。若任意几类在HWJS′′中可接受的货物类的集合等于在HWJS′中可接受的货物类的集合，则将这组存储单元称为只出不进存储单元类的集合，如图2所示，对只出不进存储单元类的集合，即便考虑存储单元类之间的缓存，就整体而言，也不再接受额外的货物类的放置，形成只出不进闭环。故考虑缓存后的数量减少。

步骤6得到只进不出存储单元类的集合。若任意几组尺寸类型存储单元在HWJS′′中所接受的货物类的集合等于在HWJS′′′中可以接受的货物类的集合，则将这任意n种组合存储单元称为只进不出存储单元类的集合。对这组存储单元，有最低的数量配置要求，使得爆仓率低于5%的风险。

式(6) 为考虑缓存后的数量配置减少；式(7) 为满足爆仓率低于5%的约束，即考虑缓存后的各类存储单元数量配置减少，各类货位的数量配置大于所存储某几类货物峰值的概率低于95%，但出现较大尺寸货物无法存储的风险仍低于5%。

1.3 模型建立

在爆仓率低于5%的约束下，构建所需存储空间最小为目标的各类存储单元尺寸和数量配置的非线性整数规划模型。

目标函数为

约束条件为式(6)～(7)。

其中，式(8) 为非线性规划目标函数，求解最佳存储单元数量和尺寸配置。式(9) 表明货物类和存储单元类配置范围约束。

2 基于整数规划的多类存储单元数量配置

本文所创建的多类货位数量配置模型是一种线性整数规划模型，可求得存储单元从最少1类到类似全周转率存储策略的最多类范围内，任意几种尺寸类型存储单元设定下，各类数量配置结果。模型求解过程并不复杂，可采用Matlab数学规划工具包直接求解，如图3所示。

图3 算法流程图Figure 3 Algorithm flowchart

步骤1排列出所有不同存储单元类组。货位类为i，在最大尺寸存储单元配置必不可少时，存储单元最多有组。各组存储单元尺寸分别为Ln,Wn,Hn=ln,wn,hn。

步骤2计算各组基于正态分布的数量配置。由订单数量分布信息Xik～U(ai1,ai2)，基于式(1)、(2)、(5) 计算得出。

步骤3计算各组内的缓存关系，得到只出不进类的集合和只进不出类的集合。列出各组约束条件式(6)、(7) 。

步骤4列出各组线性整数规划模型，求解得出考虑缓存后的数量配置。

步骤5比较各组的需求存储空间，取最小值。

3 算例

3.1 算例设计

仿真软件为Matlab R2016b。货物尺寸类型设置为20类，各类货物尺寸与货位类之间缓存关系如表2所示。第20号为货位类中最大尺寸，当以20号尺寸作为单一货位尺寸时，货位类最少1种；当各类尺寸货物均配置同种尺寸货位时，货位类最多20种；当货位类介于1～ 20之间时，20号尺寸货位总是必不可少。总的存储单元配置共有。单次实验设为10个批次，每个批次包含10个数量的订单，不同订单内同一类货物的数量服从[0,4]，[0,4]，[0,3]，[0,2]，[0,2]，[0,5]，[0,4]，[0,2]，[0,2]，[0,4]，[0,5]，[0,2]，[0,2]，[0,4]，[0,3]，[0,3]，[0,3]，[0,4]，[0,4]，[0,3]的随机均匀整数分布。出入库相邻货物时间间隔服从λ=0.1 s的指数分布。理论上每个批次货位数量范围在0～ 650之间。对每组不同类的存储单元配置进行10 000组实验，统计10 000次实验中的不爆仓率。

表2 各类货物与货位之间存储关系示意图Table 2 Schematic diagram of the storage relationship between various goods and storage units

3.2 数量配置计算结果

图4为一组配置为10类存储单元的算例。该算例给出了各类存储单元数量配置计算过程。依次对524 288组货位计算数量配置，结果如表3所示。考虑不同类货位之间缓存后，数量配置明显减少。

表3 各类存储单元数量配置结果Table 3 Configuration results of the number of various storage units

图4 一组配置为10类存储单元的算例Figure 4 A set of examples configured as 10 classes of storage units

3.3 实验结果

货物数量随时间变化与峰值分布如图5所示。在单次实验中，任意几类货物数量峰值具有不确性。在入库阶段，货架内货物数量逐渐增加。当货架内订单到齐开始出库时，由于出入库货物平均速度一致，仓库内货物数量维持相对平衡。在货物全部完成入库过程后，因仓库内货物尚未完全出库，此时仓库内货物数量逐渐减少。在总的10 000次实验中，任意几类货物峰值分布近似服从正态分布。设定5%的爆仓率约束既能很好地满足存储需求，又避免了较大的数量配置增加。

图5 出入库过程中货物数量变化与峰值分布图Figure 5 Schematic diagram of quantity change and peak distribution of goods in and out process

实验结果显示，两组数量配置方法均能保证较大尺寸货物无法存储的风险低于5%。图6为两组配置方法的需求存储空间比较图，表明考虑缓存后能有效减少货位的数量配置，降低需求存储空间。且随着存储单元类的增加，存储单元总数量配置增加，但需求存储空间减少。当存储单元类数等于货物类数时，需求存储空间最小。

图6 两组配置方法的需求存储空间比较图Figure 6 Comparison of the storage space requirements of the two configuration methods

4 结论

本文以板式家具机械手环绕式分拣系统为背景，考虑生产批次订单情况的不确定性，在一定风险(大尺寸板材无法存储的概率) 约束条件下，优化多种尺寸存储单元的数量配置，提高分拣系统有限存储空间的利用率。所得主要结论如下。

1) 较单一尺寸类型存储单元配置而言，本文的方法提高了存储单元空间的利用率，在有限的存储空间内能够配置更多的存储单元数量。

2) 随着存储单元种类的增加，存储单元共享性下降，存储单元数量必定增加，但总的需求存储空间减少。这与单一尺寸存储单元的“更多货位区域分类必定增加需求存储空间”的结论相悖。

3) 需求存储空间减少的原因为其空间利用率的提高带来的空间减少，优于存储单元数量增加而导致的空间增加。