储销一体仓储式超市中的存储货位指派优化问题研究

徐泽宇，杨 双

（暨南大学 管理学院，广东 广州 510000）

0 引言

随着经济发展和居民消费水平的提高，以储销一体、批零兼营为主要特征的仓储式超市迅速兴起。这类会员制仓储超市凭借着仓储式的陈列降低了中间存放和二次运输成本，产品的大包装和高周转可以覆盖采购成本和品质损耗。

但相应地，产品的大包装和高周转率可能引起更繁重的搬运工作，而且由于场地限制，超市内部不适合安装大型搬运设备，所以对仓储式超市进行货位分配优化以减少搬运工作量十分必要。另一方面，以往的货位优化问题中，货架仅有一个I/O，即货物由不同起点搬运至共同的终点。但在仓储式超市中，货物需要从存储货架搬运至对应的销售货架，即货物由不同的起点搬运至不同的终点。

针对货位优化问题，诸多学者在算法方面进行了创新。张延华，等[1]借鉴模拟退火算法思想，设计了改进模拟退火遗传算法，虽然优化效果显著，但研究对象为仅有一个I/O点的自动化立式仓库，问题并不复杂。罗焕，等[2]建立了多目标货位优化模型，并采用变邻域NSGA-2算法进行优化，虽然优化效果显著，但研究对象也为仅有一个I/O点的自动化立式仓库。王铁铮，等[3]采用强化学习的方式解决优化问题，虽然方式新颖，但缺少与启发式算法的优化效果对比，且寻优效率较低。姜良重，等[4]从货物价值剩余率的角度建立货位优化模型并利用自适应遗传算法进行求解，虽然建模角度新颖但没有考虑货架重心约束。刘旺盛，等[5]研究了多出入口的仓库货位优化，相比单一出入口的自动化立体仓库，虽然出入口数量增加，但增加数量有限。

综合现有的研究成果，大多数学者聚焦于单一出入口的立体仓库进行研究，即使存在多出入口仓库的研究，出入口数也只增加少数几个，不能从根本上改变问题的复杂度。而目前仓储式超市的货位优化问题，货物搬运的起终点随货物种类的增加而增加，是现有研究尚未触及的。因此，有必要针对储销一体的仓储式超市的货位优化问题建立合适的数学模型，设计改进自适应交叉变异的遗传算法进行求解，并与贪婪算法、传统遗传算法的求解结果进行对比，对相关参数进行灵敏度分析并得出相应的管理启示，以此验证模型的可靠性和算法求解的有效性。

1 储销混合货位优化模型

1.1 问题描述

如图1所示，某大型超市存储销售一体的立体仓库由销售货架和存储货架组成。最底层货架为销售货架，摆放待销售的货物，每个销售货位固定摆放一种货物，销售货架的货物摆放情况由超市决定。第二层及以上货架为存储货架，每个存储货位只能摆放一个库存量单位（Stock Keeping Unit）的货物。当销售货位上的货物被售出时会立即从存储货架上搬运同种货物的一个库存量单位以完成补货。具体优化问题可以描述为：已知货物的种类数、每种货物的库存量单位数和每种货物每个库存量单位的重量。按照一定的指派规则，将所有货物的库存量分配到存储货位中，在保证货架重心不超过一定高度的条件下，同种货物尽可能集中摆放，以使全部货物搬运到对应销售货位所需时间最少。

图1 销售-存储仓库示意图

1.2 假设条件

（1）每个存储货位及销售货位形状大小相同，沿x，y，z轴方向分别长为ℎx，宽为ℎy，高为ℎz。

（2）销售货位：沿x，y轴方向分别有a行b列，共有a×b个销售货位，均在第1层（最底层），每个销售货位摆放固定种类的货物。

（3）存储货位：沿x，y，z轴方向分别有a行c列t层（c＜b），共有a×c×t个存储货位位于第2层至第t+1层。

（4）巷道：所有巷道宽度相同，存在多条x轴向巷道但仅存在一条y轴向巷道位于第c列到第c+1列之间。

（5）每个存储货位和销售货位都只能存放一种货物的一个库存量单位，一个库存量单位也只能放在一个货位上，且库存量单位是最小的存放单位，不可拆分。

（6）共有n个货物种类，其中第i类货物有ki个库存量单位。满足，即库存量单位总数不得超过存储货位数。

（7）每个货物的每个库存量单位重量已知，其中第i 类货物的第j 个库存量单位重量为mij(i≤n，j≤ki)。

（8）货物由存储货位转运到销售货位时是按照直线运动的，且每次仅能沿x轴、y轴、z轴中的一个方向运动，运输路线不能从货架内部穿过。

（9）货物到达货位中心即视为货物放置完成，不考虑货物放置后的调整时间。

（10）在单位销售周期内，存储货架上的所有货物最终均会转移到销售货架上并售出。

1.3 符号说明

为了建立合适的储存-销售货位优化模型，现规定具体符号及其定义见表1。其中，决策变量仅为xij、yij、zij。而表示第i类货物所在的销售货位坐标，由超市决定。

表1 符号定义

1.4 目标函数

建立货位优化模型的目标函数，需要遵守以下几个原则：

（1）补货效率最大化原则。补货效率最大化是指在单位销售周期内存储货架上的所有货物搬运到销售货架上对应货位的时间最短[6]。为便于描述，规定(xij,yij,zij)表示第i类第j个库存量单位在存储货架上的坐标，表示第i 类货物的销售货位坐标。由此所有产品的搬运时间见式（1）。其中，Distx(i,j)，Disty(i,j)，Distz(i,j)分别表示将第i类第j个库存量单位从存储货位搬运至对应的销售货位的x轴向距离，y轴向距离和z轴向距离。

（2）产品相关性原则。为了便于存储货架上货物的管理和保存，使存储货架上的货物排列整齐有序，每种货物在存放时应当尽可能的集中布置[7]。

由此做出如下定义：

②类内分散度。定义di为第i类货物的类内分散度。其计算方法为第i类货物中每个货物到中心位置的距离之和。具体见式（3）。

④类间分散度。定义D为类间分散度，计算方法为各类货物中心位置与所有货物中心位置距离之和。

按照产品关联规则，将相关性最强的货物尽可能摆在靠近的位置，以每一类的类内产品距离最小、类间产品距离最大为目标函数F2。

1.5 约束条件

（1）一位一物。每个货位只摆放一个库存量单位的货物，每个库存量单位的货物可以摆放在任意一个存储货位中[8]。具体函数形式见式（7），即任意两个库存量单位的货物至少存在一个维度的坐标不相等。

（2）货架稳定。货架稳定约束是指货架在使用过程中保持稳定，避免倾斜倒塌[9]。即货物的分布应使存储货架的重心在一定高度以下。具体函数形式见式（8），其中α(α＞1)表示宽放系数，zmin表示当前货物重量配置下货架重心所能下达的最低高度。具体计算方法是将所有货物按从重到轻进行排序，按此顺序从低层至高层填充货架。

（3）货位中心摆放。货物的位置摆放在储位中心上，具体如图2所示。其中ℎx表示存储货位沿x轴向的长度，l表示巷道宽度，a表示所有货架行数。ℎy表示存储货位沿y轴向的长度，c表示存储货架列数。ℎz表示存储货位沿z轴向的长度，t表示存储货架层数。由此则可得到货物坐标，见式（9）。

图2 储-销货架俯视图

图3 改进自适应交叉变异的遗传算法流程图

1.6 建立模型

综上所述，可以建立如下所示的货位优化模型

s.t.

其中，F1表示补货效率最优，F2表示同种货物集中布置、不同种货物分散布置，D和di的具体计算见式（3）和式（5）。第一个约束条件表示一个货位只能放置一个货物，第二个约束条件表示货架重心控制在一定高度以下，第三个约束条件表示货物摆放在货位中心上。

2 改进自适应交叉变异的遗传算法

2.1 改进自适应交叉变异的遗传算法流程

经典遗传算法（Genetic Algorithm）的基本思想是对种群不断进行选择、交叉、变异操作，以此来实现“优胜劣汰”[10]。但经典遗传算法在迭代初期容易陷入局部最优解，迭代后期又难以收敛。故其求解效果有时并不理想。本文提出改进自适应交叉变异的遗传算法。不仅对交叉和变异操作进行改进，而且还引入精英保留策略。此外，本文增加降低重心高度的操作，通过降重算法对经过交叉、变异后重心高度过高的个体进行调整，以保证最后迭代产生的个体均满足重心约束。

改进自适应交叉变异GA的具体步骤如下：

（1）设置初始参数：设置种群规模Popsize，交叉概率Pc，变异概率Pm，最大迭代次数Genmax。

（2）初始化种群：采用实数编码产生个体数量为Popsize的随机初始种群。

（3）计算每个个体的适应度：根据前文公式计算每个个体的目标函数值。

（4）选择操作：采用二元锦标赛选择法，随机选取两个个体，将目标函数值较小的个体放入子代种群中。

（5）自适应交叉操作：对基于位置的交叉操作（Position-based Crossover）进行改进。传统的基于位置的交叉操作分为两个阶段，第一阶段是从两个父代染色体上随机选择若干位置，这些位置的基因复制保留到子代相同位置，第二阶段是在父代染色体2上寻找子代染色体1缺少的基因并将这些基因以在父代染色体2中的顺序填入，另一个子代以相同的方式产生，具体如图4所示。

图4 自适应交叉操作示意图

为了保证迭代过程中解的多样性，本文针对第一阶段复制保留的基因数量采取自适应操作。即复制保留的基因数量与当前迭代次数相关，具体见式（10）。

其中，n表示第一阶段被保留的基因个数，dim表示染色体上的基因总数，tmax表示最大迭代次数，t表示当前迭代次数，rand(-1,1)表示在(-1,1)之间的随机数。

（6）变邻域变异操作：经典遗传算法在求解离散问题时往往采用互换变异方式，然而单一的变异方式不足以进行深入的搜索，所以本文采用三种变异方式，并从中选择最优的个体作为最终的变异个体，具体如图5所示。

图5 变邻域变异操作示意图

（7）精英保留策略：将初始随机种群P0和经过选择、交叉、变异的种群Q0进行合并，形成个体数量为2×Popsize的种群R0。计算所有个体的适应度，将适应度较高的个体保留到下一代中，从而形成新一代种群P1[11]。具体如图6所示。

图6 精英保留策略示意图

2.2 算法设计

2.2.1 编码方式。本文采用的编码方式是基于顺序库存量单位对货位进行编码。即产生一个[1,a×b]的随机序列作为初始个体。具体如图7所示。

图7 编码示意图

图7表示第1类第1个库存量放置在第7号存储货位，第1类第2个库存量放置在第9号存储货位，以此类推，第n类货物的第kn个库存量放置在第6号存储货位。

存储货位的编号方式如下：距离原点最近的存储货位编号为1，沿y轴正方向延伸的存储货位编号依次增加。当该行存储货位全部编号完成后，再对更高一层进行编号，每层编号规则均为沿y轴正方向延伸的存储货位编号依次增加，当该排货架全部编号完成后，再对沿x正方向的货架排进行编号。即编号的顺序遵循先对y轴正方向，再对z轴正方向，最后是x轴正方向。具体如图8所示。

图8 货位编号示意图

2.2.2 重心调整操作。如果个体的重心高度超过给定高度，则对其进行调整。具体调整操作为：首先随机选取两个货物，其次比较两者的重量和重心高度。如果重量较大者位置也较高则两者互换位置，否则不操作。再次计算当前摆放情况的重心高度，若满足约束则结束操作，若不满足则继续随机选取两个货物，重复上述操作直至满足重心约束或者达到最大操作次数。算法流程图如图9所示。

图9 重心调整操作算法流程图

3 实例验证及分析

在本节中，首先描述测试问题的生成过程。其次基于不同规模的算例对本文提出的改进自适应交叉变异遗传算法进行评估，并将其与贪婪算法和经典遗传算法进行比较。最后通过实验结果说明几个关键因素对货物搬运效率和品类集中度的影响。

3.1 数据产生

首先生成三组不同规模测试算例（小规模、中规模、大规模）。根据实地观察，无论存储货位和销售货位的数量如何变化，始终保持两条巷道的布局，即一条巷道沿x轴方向，一条巷道沿y轴方向，巷道宽度l也固定为2m。每个存储货位和销售货位的长、宽、高也保持不变，即ℎx=1,ℎy=1.2,ℎz=1.4。机械臂的移动速度也保持不变，即vx=0.5,vy=1,vz=0.2。而问题规模不同，存储货位和销售货位的数量也不同，相应地存储货位和销售货位的陈列方式也不同。另外，由于两个目标函数值量纲相差较大，为了平衡量纲，将权重设置为0.001。其他参数具体设置见表2。

表2 实验参数表

遗传算法的相关参数设置如下：种群大小Popsize=100，最大迭代次数Genmax=400，交叉概率Pc=0.7，变异概率Pm=0.3。

不同规模的货物种类产生方式为：通过产生n个随机正整数，且其和为U，每个随机正整数表示每类货物所包含的库存量单位个数。

3.2 算法性能评估

为了证明改进自适应交叉变异遗传算法的优越性，本文引入一般的贪婪算法进行对比。贪婪算法的具体规则如下：

步骤1：对所有存储货位进行编号。

步骤2：将各类货物按平均重量由大到小排序，不妨设第1 类货物的平均重量最大，第2 类次之，……，第n类货物平均重量最小。对同类货物内部也按重量由大到小排序，比如第i类货品的第1个货物最重，第2个货物次之，…，第ki个货物最轻。令Oi,j表示第i类货物中第j个货物，并令Vi,j(s) 为第s个存储货位到Oi,j的销售货位的F1目标函数值。

步骤3:fori=1,2,…,n,j=1,2,…,ki，do:令S为当前高度最低的所有空闲存储货位的集合，并对任意s∈S，计算Vi,j(s)；选出S中Vi,j(s) 值最小的存储货位，比如；指派货物Oi,j到存储货位。

为了更准确地评估经典GA算法和改进自适应交叉变异GA算法的性能。现做出如下定义：

其中，GAPBefore(i),GAPAfter(i)分别表示经典遗传算法的优化率和改进遗传算法的优化率。ZGreedy(i)表示第i个算例中贪婪算法的目标函数值；ZBefore(i)表示第i个算例中经典遗传算法的目标函数值；ZAfter(i)表示第i个算例中改进遗传算法的目标函数值。

每个算例进行五次实验并计算五次实验结果的平均值作为该算法的最终结果。最终实验结果见表3。

表3 算法结果表

由表3可以看出，无论是小、中、大规模，改进自适应交叉变异遗传算法的优化效果明显优于经典遗传算法和贪婪算法。其在贪婪算法结果的基础上最小者优化了5.31%，最大者优化了31.13%。与经典遗传算法相比，改进自适应交叉变异遗传算法平均优化效果提升了6.78%。

实验的迭代曲线如图10所示。可以看出改进后的遗传算法比经典遗传算法能够更快速地收敛，而且目标函数值也更低，能有效地防止算法陷入局部最优解。由此可得改进后的遗传算法无论是在求解效率还是求解效果上均优于经典遗传算法。

图10 算法迭代图

3.3 关键参数对目标函数的影响

将表3的目标函数值绘制成如图11所示的折线图。可以看出，在同一问题规模下，存储货架的层数越低，目标函数值越小。所以管理者在布置存储货位时，应尽可能地降低货架总层数。

图11 不同算例下算法结果对比图

4 结语

本文针对储销一体化的货位优化问题建立了多目标优化的数学模型，采用自适应交叉变异的遗传算法，即对遗传算法中的交叉和变异操作进行针对性优化并引入经营策略以增强算法的全局搜索能力。通过多次仿真实验验证了改进算法相对于贪婪算法的优越性，算法结果可以获得更短的搬运时间和更集中的货物摆放。此外，根据算法结果也总结出相应的管理启示，在布置存储货位时，应当尽可能降低货架总层数。