基于关联规则和遗传算法的服装辅料储位优化*

周 叶，连明昌，陈松航，吴佳彬，陈 豪

（1.福州大学 先进制造学院，福建 泉州 362251；2.中国科学院 海西研究院泉州装备制造研究中心，福建 泉州 362216；3.福建柒牌时装科技股份有限公司，福建 泉州 362200）

0 引言

我国是世界上最大的纺织品服装生产和出口国，服装纺织对我国产业布局和经济发展至关重要。服装纺织业作为传统劳动密集型产业，各环节都需要仓储环节参与，但其仓储管理还高度依赖人工，仅料单拣选就占据60%以上的人力成本；而且，辅料型号受到时尚潮流影响更新频繁。这些现象引发了储位分配不合理、库存结构混乱等问题。通过优化仓库储位分配方法能够有效解决上述问题，提高企业仓库作业效率[1]。

储位分配问题已经被证明是NP-hard 问题[2]。目前多数研究利用物料间相关信息，采用元启发式算法进行优化[3]。Chen 等提出基于两阶段式禁忌搜索方法来优化最小化平均行走时间[4]。Rani 等以检索时间和频次为目标建立多目标优化模型，通过遗传算法（Genetic Algorithm，GA）计算储位分配[5]。但传统遗传算法存在收敛过早、局部搜索能力差等问题[6]。焦玉玲等针对收敛过早问题，提出多种群遗传算法，以货物出入库效率、货架稳定性及产品关联性为目标建立模型获得分配结果[7]。朱杰等针对遗传算法易陷入局部最优，将模拟退火算法与遗传算法结合来优化储位分配模型[8]。少数学者引入数据挖掘方法进行储位优化[9]。Chiang 等提出基于关联规则的自适应库位分配方法，拣选距离较传统分类方法提升明显[10-11]。Pang 等采用关联规则挖掘订单物料间的关系最小化拣货距离[12]。

上述研究多数采用一次性优化策略来处理储位分配问题，无法根据订单变化进行储位调整。而且研究领域主要集中在电商仓库，对服装辅料仓库研究较少。本文针对服装辅料仓库储位分配问题，设计一种基于Apriori 算法和改进遗传算法（Apriori Improved Genetic Algorithm，AIGA）的储位优化方法，首先采用Apriori 算法挖掘订单信息，根据订单变化动态生成调整库区划分，将库区划分结果作为遗传算法产生初始种群条件，提高初始种群质量；其次设计灾变机制和改进交叉变异算子，提高遗传算法全局搜索能力，寻找合适的储位分配方案，降低出入库行走距离，提高现场人员作业效率。

1 模型建立

1.1 问题描述

某服装企业辅料仓库布局如图1 所示，该仓库拥有24 排货架，每排货架有48 列，每列有4 层储位，共计4 608 个储位。

图1 辅料仓库平面图

储位结构如图2 所示，以“排-列-层”的方式对储位进行编码，其中每个储位宽0.8 m，高0.6 m，深0.8 m。

图2 储位结构图

传统作业方式中，物料由供应商送货质检完成后进入仓库，现场人员根据入库单进行上架操作，主要按照随机存储和靠近出库口存储两种策略进行上架。此种作业方式的优点是储位利用率高，但存在以下问题：

(1)物料没有进行分类存储，分散在仓库之中，盘点同类物料库存时工作量大。

(2)相关性强的物料未靠近放置。由于服装制作原料中存在齐套性，如拉链和拉链头通常会一起拣货，因此应考虑将齐套物料或者相关性高的物料靠近放置[13]。

(3)部分高频物料被放置在仓库尾部，导致作业时拣货距离加大，影响作业效率，增加人员作业强度。

针对第一和第二个问题，可以对仓库中物料采用Apriori 算法进行相关性分析，同物料组且相关性高的物料靠近集中放置。针对第三个问题，通过建立储位分配模型，应用改进遗传算法进行最优储位分配方案的搜索，求解最短分拣路程的分拣方案，降低现场人员作业强度，提高作业效率。

1.2 储位分配模型建立

为方便储位分配模型建立和求解，在不影响分配结果的情况下，进行以下假设：

(1)每个订单均由一辆拣货车拣取；

(2)拣货单需要的物料不存在缺货情况；

(3)订单物料需求量不超过一辆拣货车最大拣货量；

(4)一个储位只存放一种物料。

目标函数需要用到的参数如表1 所示。

表1 参数符号含义

考虑到仓管员在作业过程中的拣货距离和库存结构，建立储位分配建模，从拣货距离和物料相关性两方面建立优化目标。

(1) 最小化拣货距离。储位优化首要目标是减少拣货行走距离。当作业人员接到一个拣货任务时，拣货距离可分为三段：一是从办公室到第一个物料的距离；二是物料间的行走距离；三是最后一个物料到出库区的距离，所以完成单个拣货任务的总距离为式：

(2) 最小化同物料组的组间距离。为方便盘点等工作和遵循同物料组集中存放原则，同类物料尽量集中放置，相关性强的物料靠近放置。假设物料组的中心坐标为Ri，该物料组的某个物料在仓库存放储位的坐标G为（xi,yi,zi），则Ri为：

对于坐标为(xi,yi,zi)的物料，该物料与中心坐标Ri距离di如式（3）所示：

同物料组的物料离中心点距离越小，集中程度就越高，目标函数即为：

综合式（1）和式（4）得出最终模型的目标函数为：

2 算法设计

2.1 基于Apriori 的库区划分方法

服装企业辅料型号众多且更新频繁，虽已使用物料组进行分类，但由于分类方式偏重于生产需要，分类规则过于细致，导致物料组数量过多，不利于存放管理，因此需要对物料组使用Apriori 算法进行关联规则挖掘，将相关性强的物料组聚合形成大类库区，详细步骤如下：

（1）获取历史订单记录，对订单行数为1 的数据进行过滤，对不规范和缺失的数据进行补全或筛除。

（2）设置最小支持度以及最小置信度，运行Apriori算法挖掘物料组间关联规则，计算提升度和所有物料组的拣货频次。

（3）根据关联规则结果，按照包含物料组数量以及支持度进行排序，优先选择包含数量更多或者数量相同支持度更高的关联规则。

（4）对关联规则进行遍历，检查其包含的物料组是否已经进行大类划分。如果有，跳过该规则；如果没有，则将包含物料组划分成一个大类；否则，则不进行划分。

（5）将分好的大类按照拣货频次进行排序，按照大类数量划分等量的大类库区，并统计现有库存中每个大类包含的具体物料编码数量，按照该数量从靠近出库区的位置开始分配大类库区。

（6）输出大类库区划分结果。

2.2 基于改进遗传算法的储位分配方法

（1）染色体编码

根据仓库情况及储位优化模型特点，编码方式采用实数编码。每条染色体包含a·b·c个基因，a代表排，b代表列，c代表层。每个基因代表储位和物料的对应关系，储位编码通过转换公式转化为基因位置下标index，公式如式（6）所示。

如图3 所示，储位01-01-2 经过式（9）转化计算得到位置下标为2，染色体下标为2 的位置放置ID 为9 的物料，即代表储位01-01-2 放置了9 号物料：

图3 染色体编码方式

（2）适应度函数

考虑到式（5）建立的模型是双目标函数求解问题，不易得出求解方案，因此为两个目标函数分配两个影响因子λ1和λ2，采用权值分配将其转换成单目标函数求极值问题。转化后单目标优化公式如式（7）所示，由于最小化拣货距离目标比最小化同物料组物料距离目标更为重要，因此经过计算分析得λ1=0.75，λ2=0.25。

（3）初始化种群

首先判断物料所属物料组，在物料组中随机选择一个储位进行分配。为确保一个储位只存放一种物料，储位被分配后标记为已放置。遍历所有物料直到都被放在储位上，因为物料种类数量可能小于储位数量，所以没有物料存放的储位默认设置为-1。

（4）改进多段交叉算子

由于需要保证物料的唯一性，因此采用顺序交叉方式，传统顺序交叉直接选择两个父代染色体的随机起止位置进行交叉。本文先选取两个父代染色体，在父代染色体随机选取n个库区所在的基因片段，在各自的基因片段中随机选择起止位置，将父代1 起止位置内的基因复制到子代1 相同位置上，起止位置外的基因根据父代染色体2 上的顺序填入子代1 中。未选中库区则不做变动复制至子代中，具体如图4 所示。

图4 染色体交叉方式

为提高算法全局搜索能力，交叉概率Pc应根据染色体适应度情况和迭代次数动态调整，如式(8)所示。其中，Itcur为当前迭代次数；MaxIt 为最大迭代次数，Pcmax和Pcmin分别为最大交叉概率和最小交叉概率，frank为当前个体在种群中按照适应度由小到大的排名。随着迭代次数和适应度排名增大，交叉概率会逐渐增大。

（5）改进变异算子

变异同样需要保证物料唯一性，只有满足同一库区内的两个物料才可进行变异操作，设置变异概率Pm随适应度排名frank和迭代次数Itcur增大而增大，与交叉同理，其公式如式（9）所示，具体变异方式如图5 所示。

图5 染色体变异方式

（6）灾变机制

算法迭代后期，种群个体间相似度较高，难以通过遗传操作产生更优个体[14]。本文引入灾变机制增加种群多样性、提高全局搜索能力。由于传统灾变只生产新个体，并未考虑迭代次数和个体适应度情况，因此灾变概率最好采用自适应调整。进化前期，迭代次数较小，种群多样性丰富，可以将灾变概率控制在较低水准；进化中期，个体间相似度较高，可以将灾变概率逐渐提高，增加种群多样性；进化后期，种群中的个体较优，灾变概率应逐渐降低，避免丢失种群进化结果；同时对种群中优秀个体应保持较低灾变概率，保留优良信息，较差个体保持较大灾变概率，增加种群多样性。基于上述目标，本文设计一种自适应灾变概率，如式(10)和式(11)所示：

根据式（10）和式（11）所示，随着迭代次数增大，θ先从0 增大到π/2，随后从π/2 减小至0，总体呈现先增大后减小的趋势；同时考虑个体优良情况，当个体适应度排名靠前，则采用较小的动态灾变概率防止优良基因被破坏，适应度排名靠后的个体则获得较大的概率。同时采用精英保留策略，保证灾变过程中较优个体不会被消灭，指引种群向正确的方向进化。同时考虑灾变机制的触发条件，预设值灾变周期T，当种群每经过T次迭代或者全局最优值连续3 次相同时，进行一次灾变操作。

2.3 储位分配方法流程

AIGA 总体方法流程如图6 所示。根据图6 中流程图输出优化后的种群，在优化后种群中选择最优染色体作为问题输出解。

图6 储位分配方法流程

3 案例应用

为验证模型和算法的有效性，在自主研发的服装辅料仓库管理系统MWMS 中集成应用本文设计的优化方法。以本文研究的服装企业拣货记录为例，从MWMS中获取企业辅料仓库2022 年4 月～6 月一季度的拣货订单记录5 771 条和入库上架单记录3 795 条，共包含37 521 条明细、22 种物料组和4 364 种物料编码。

3.1 库区划分

首先运用Apriori 算法对拣货订单数据进行关联规则挖掘。支持度、置信度以及提升度作为判断物料组相关度的重要依据，设置最小支持度0.1，最小置信度0.6。设置物料组集合中最大置信度为最终置信度，最大提升度为最终提升度，最终获得符合条件的物料组关联规则98 条，部分关联规则见表2。

表2 物料组部分关联规则

由表2 可得，每个关联规则提升度均大于1，说明在满足最小支持度和最小置信度下物料组之间存在正相关。根据挖掘出的关联规则，最终将22 种物料组划分成11 个大类，并按照大类拣货频次进行排序编号，如表3 所示。

表3 物料组大类划分结果

考虑物料组相关性和拣货频次对大类进行位置划分。大类K1 拣货频次最高，在最靠近出库区的位置。其次是大类K2，在离出库区距离仅次于大类K1 的位置。其他大类按照拣货频次由高到低依次放置，根据大类中物料编码数量确定库区大小，最终结果如图7所示。

图7 库区划分结果

3.2 储位分配

将大类库区所属储位及物料作为遗传算法前置条件。种群数量为100，交叉概率Pcmin为0.8、Pcmax为0.95，变异 概率Pmmin为0.05、Pmmax为0.2，运行3 次取 最优值。表4 展示部分物料现有储位和库区划分后各方案优化前后储位对比，可以看出部分高频物料被调整到靠近出库区的位置，低频物料被调整到远离出库区的位置，且在库区约束下，辅料在分配时也未离开所属库区范围。

表4 部分储位分配结果表

3.3 结果分析

为保证实验不受偶然因素影响，每个方案进行10 次实验，取平均值作为评价标准，遗传算法种群数量设置为100，迭代次数为200，传统遗传算法交叉概率为0.8，变异概率0.1。最后结果如图8 和图9 所示，可以看出使用AIGA 效果优于其他算法，具体表现为如下：

图8 方案效果对比

图9 初始种群适应度大小

（1）从整体适应度评价，AIGA 适应度比GA、Apriori+GA(AGA)以及改进遗传算法IGA 平均分有13.97%、10.1%以及3.47%的提升；

（2）从收敛效果看，AIGA 的最终适应度收敛值最低且速度最快，其最终适应度降至初始适应度的57.45%，优于IGA 的59.87%和AGA 的63.7%；

（3）从初始种群适应度水平看，Apriori 算法有效降低遗传算法的初始种群适应度。由图9 得出，加入Apriori 算法后，GA 及IGA 的初始种群平均适应度分别下降10 709 和13 346；并且IGA 相较于传统的GA 也有一定的优化效果，平均适应度下降2 197。

以2022 年10 月的入库单和拣货单作为验证，按照S型路线作为行走路径来统计行走距离，如表5 所示，可以得出：

（1）AIGA 算法的拣货距离相比于仓库目前储位分配方案缩短23.85%，优化效果明显；与AGA 方法相比提升10.24%，证明改进遗传算法的有效性。

（2）入库上架方面，由于入库距离不是首要考虑目标，但因为部分高频物料由原来靠后的位置放置到较靠前的位置，也使得入库上架距离有一定缩短，与现有方案相比，AIGA 在上架距离上平均缩短13.70%，与AGA方法相比提升8.2%，证明了算法的有效性。

4 结论

本文采用Apriori 与改进遗传算法结合的方法对服装辅料仓库储位分配进行优化研究。通过Apriori 算法生成大类库区，对遗传算法初始种群进行改进，提高初始种群质量；设计自适应变异交叉算子和灾变机制，提高算法搜索效率和性能，克服传统遗传算法收敛慢和易陷入局部最优的不足，最后在实际应用取得良好效果，验证了算法可行性和有效性。