改进遗传算法在自动化立体仓库货位分配中的应用

□ 赵 阳

(兰州交通大学 机电工程学院，甘肃 兰州 730070)

1 引言

在当今社会互联网、电商等各类技术与产业竞相发展的背景下，物流仓储在社会物质生产活动中的地位日益提升。仓储的运作管理对优化物流产业，提高经济活动的运行质量和效率都具有重大意义。自动化立体仓库(AS/RS)要达到在能耗小和成本低的条件下对货物进行存取的客户需求，在规定的期限内将物品准确提供给客户[1]。货位管理运用的核心在于：在遵循货物存储的基本原则下提高货位的使用率，尽量提高仓库使用效率。

近年针对仓储货位分配策略优化问题的研究主要有：李鹏飞等[2]以出入库效率为优化目标建模，采取病毒协同遗传算法进行仿真，表明病毒协同遗传算法是进行货位优化的一种有效方法；李霞等[3]从入库、出库和倒库三个阶段来对动态货位优化进行建模与仿真，选用遗传算法求解模型并验证了算法的有效性；刘万强等[4]从提高AGV小车作业效率出发，研究棋盘格密集仓库的货位分配问题，设计相应的改进算法，解决货位分配问题的同时，AGV小车的作业效率也大幅提升；彭小利等[5]提出基于制造物联技术的智能仓库，引入RFID技术实现物品、货架、叉车、工人等的智能化；徐伟华等[6]针对密集型仓库使用实际，根据两种工况设计模型，利用遗传算法进行求解有效提升了堆垛机搬运货物的效率。

从已有的文献可以总结出，较多现有研究对具体问题的优化目标考虑不够详尽，有的研究只考虑货物分类摆放和货架重量的问题，有的研究只考虑货物的出入库效率问题而又忽略了货架的整体稳定性，将多目标结合起来建模求解的研究还较少。同时对于多目标问题求解的优化算法选择也存在一些问题，部分求解算法收敛性不好、计算速度慢、解的质量低等问题仍然存在。另外在现代智能优化算法的研究中，算法参数的选取与具体操作的设计是影响算法性能指标的关键环节。因此，本文提出以货架稳定性、货物周转率、货物相关性等原则为基础的多目标货位优化模型，并设计双种群遗传算法[7]进行求解，对立体仓库的货位分配策略进行研究。

2 自动化立体仓库货位分配模型

2.1 货位分配规则

仓库货位分配在考虑货位利用率的同时，还需要同时兼顾货架整体稳定性、各类物品的时效性和总体的出入库效率等。通过对实际场景的研究和分析，本文建立的货位分配规则涵盖以下几个方面。

①较重物品低层存放。现有研究通常仅单纯考虑节约堆垛机存取货物耗时，并未充分考虑不同种类货位存储时重量、体积差异给货架稳定性带来的影响。本文设置“重物品分配较低层，轻物品分配较高层”的规则，使货架承载稳定。

②周转频率较高的货物靠近巷道口存放。为减少堆垛机对同类物品反复存取耗时，提高出入库效率，应将该类物品靠近巷道口存放。

③相关物品靠近存放。对于关联物品种类，通常会出现同时需要进行出库操作的情况，一次要安排尽可能靠近存放，以便提高物品的查找和存取。

④物品先进先出。先进先出原则的设置是考虑到例如食品、药品等种类的货物要求有较强的时效性，避免因长时间存储为之后的使用带来问题，需考虑先入库的物品在出库操作时拥有较高的优先级。

2.2 货位分配建模

2.2.1 基本条件假设

为方便将实际问题抽象成为数学问题，在保证符合实际操作原理的基础上，本文需将数学模型的建立进行以下假设：

①各货架整齐平行排列，巷道两侧仅各有一排货架。货架构造即各个货架层、列、货位的尺寸、数量均相同；

②为方便统计计算，将货架靠近出入口的一列记为第一列，最下方一层为第一层；

③为便于实际操作和实例的分析转化，每条巷道内设置一架堆垛机；

④考虑到计算的复杂性，假设堆垛机在搬运物品时进行的是匀速直线运动，水平和竖直方向的速度分别为vx和vy；

⑤货物种类已知，相同种类的物品可以在不超过货位容量的情况下合并放在同一个货架中，且重量要均匀分布。

2.2.2 货位分配规则建模

①根据“较重物品低层存放”原则建立的目标函数f1。

为保证整个货架的稳定性，遵循“重心越低则越稳定”原则。货架整体重心指标可以用托盘上物品质量与货架层数的乘积来表示，乘积越小则重心越低。根据此建立的数学模型为

(1)

其中：r为区域内的货架总数；p为一排货架的层数；q为一排货架的列数；k为物品所在货架编号；i为物品所在货架层；j为物品所在货架列；mkij为第k排货架第i层第j列货位上的物品质量；f1为每个托盘上物品质量、物品所在货架、物品所在层三个参数的乘积。

②根据“周转率靠近出入口存放”原则建立的目标函数f2。

该规则要求出入库过程堆垛机搬运的效率高，堆垛机搬运物品的效率与货叉的移动距离有关，因此，物品存放位置直接影响堆垛机运用效率。为此出入库频率高的物品应分配靠近巷道出入口的货位。物品的周转率定义为某时间段货物出入库的数量与此物品总量的比值。由此可得到数学模型为：

(2)

其中：pkij为存放在(k,i,j)货位物品的周转率；tkij为堆垛机从巷道口出入库点到(k,i,j)货位运行耗时；f2为某物品周转率与堆垛机运行耗时的乘积之和。此外：

因此，将tkij代入式(2)得：

(3)

约束条件为：

③根据“相关物品靠近存放”原则建立的目标函数f3。

出库物品的种类常与其商业用途有关，以工厂生产车间物流配送为例，各类零部件配件往往会同时被需要。因此，具有相关性的物品入库安排货位时必须为同一货架或相邻货架，且两者之间的距离尽量小，否则认定为没有达到相邻的要求。假设具有相关性的两物品存放位置分别为(k1,i1,j1)和(k2,i2,j2)，其所在货架为同一货架或同一巷道相邻货架。

可建立如下模型：

(4)

约束条件为：

其中：k1为物品1所在货架的排；j1为所在货架的列；i1为所在货架的层；k2,j2,i2同理；w为两货架间巷道的宽度；m为相关物品的组数；c为相关物品的组序号；f3为相关性物品的距离之和。当k2-k1=0时，表示两物品存储在同一货架；当k2-k1=1，表示两物品存储在相邻货架上，为确保物品存储于同一巷道的两排货架，需将k1取奇数以满足假设。

④根据“先进先出”原则建立的数学模型。

同种类物品是物品具有相关性的特殊情况，存放时应同时满足“相关物品靠近存放”的规则，因此把“先进先出”原则的建模公式作为前者的约束条件。假设放置同种类例如食品：物品1、物品2，其中物品1在先前已入库，物品2为待入库的物品。根据以上分析，物品2所在货位与巷道口的距离应远于物品1，即堆垛机从出入库点取走物品2的耗时大于取走物品1的耗时，即t2≥t1。设物品1货位坐标为(k1,j1,i1)，物品2货位坐标为(k2,j2,i2)，据此建模为：

化简得：

2.3 多目标货位分配模型

在实际操作中对货位进行分配时，需要同时考虑以上几个规则，即货位分配时需要同时满足式(1)、(3)、(4)三个方程。

约束条件为：

根据实际问题构建的数学模型式(1)、(3)、(4)，对自动化立体仓库的货位优化问题进行求解，但本问题是多目标函数的求解问题，不易得出求解方案，因此为三个目标函数分配三个影响因子θ1、θ2、θ3，采用权值分配将其转换成单目标函数求极值的问题。

minf=θ1f1+θ2f2+θ3f3

(5)

3 基于双种群遗传算法的模型求解

3.1 求解思路及算法流程

通过之前对数学模型的描述，将具体问题的数学模型分别建立为三个求极小值的目标函数，但由于三个目标函数之间互相影响，尽管将其转化为单目标函数求极值，其实质仍是多目标函数的优化问题。大多数工程实例都会被转化为多目标函数问题，对其有良好效果的智能求解方法一直是近年来的研究热点。其中，遗传算法对货位分配策略优化求解效果优秀[8]。遗传算法的基本原理是：根据生物“物竞天择，适者生存”的自然规则设置一定种群数量的候选解后，进行选择、交叉、变异等一系列操作增加种群多样性增加算法的计算性能，得出最优解，在求解同时能兼顾运算效率和运算精度。此外为改善传统遗传算法存在的缺陷，本文采用双种群遗传算法进行求解。算法流程如下：

第一步：根据工程问题构建的数学模型进行编码；

第二步：根据问题模型随机产生N个解构成初始种群，令i=0；

第三步：种群一进行适应度函数评价后采用锦标赛法进行选择运算；

种群二进行适应度函数评价后采用轮盘赌选择法进行选择运算；

第四步：两个种群在选择运算后分别进行交叉、变异运算生成新一代物种；

第五步：两种群合并再次进行遗传运算；若i到达最大进化代数则输出最大适应度个体；反之则在i+1后进行第三步操作；

第六步：结束。

3.2 参数设计及遗传运算

3.2.1 编码

本文模型选择整数编码的方法[9]。具体实现方法是：用坐标表示货位编号，每条染色体表示一种分配方式；每条染色体都可以分为N段，每段代表一个基因，而每个基因代表空间内一个货物货位的位置(k,i,j),即每个基因都对应一个货位的编号，其中N为这条染色体中货位的个数。此外，每段基因都是由三位整数表示，百位k、十位i、个位j的值分别代表货位所在货架的编号、货位水平方向在第几行、竖直方向在第几列。

假设缓存区域有五个货物需要进行分拣入库，其中1号货物置于(3,2,1)即3号货架的第2行第1列的位置；以下同理，2号货物置于(3,2,2)；3号货物置于(4,2,3)；4号货物置于(4,4,4)，5号货物置于(2,2,4)。那么“321”、“322”、“423”、“444”、“224”就分别表示一条染色体的五个基因，此时染色体“321322423444224”即为一个解，表示一种可能的货位分配方式。

3.2.2 适应度评价函数

适应度值是算法评价染色体解的优劣的重要指标，适应度值大的个体被遗传保留到新一代种群的可能性会更大，反之则很难被保留到下一代种群[10]。本算法采用建模过程中得到的函数模型式(5)的函数值来评价个体的优劣程度。

3.2.3 遗传运算

①选择运算。

选择运算体现“适者生存”的自然原理，根据适应度函数值来选择更适合进入下一代种群的个体。在此针对两个种群分别选用“锦标赛法”和“轮盘赌法”作为选择操作。其中种群一使用的“锦标赛法”：确定每次选择的个体数量，种群中随机选择个体构成组，根据个体适应度值，选择其中适应度最好的个体进入子代种群重复该操作直至种群规模达到要求。为了体现两个种群的差异性，对于第二个种群的选择运算使用“轮盘赌选择法”，即将各目标函数分配权重后，以其加权和在总和中所占的比重作为选择标准进行选择，加权和越大的个体被选择的概率越大。

②交叉运算。

交叉运算是算法过程中种群产生新个体的主要来源，两个体的部分染色体在某概率下按照一定的规则进行交换。本文设计的交叉操作为：种群中的某个体为一种货位分配方案，将种群中的两个个体相交叉即可产生两个全新的解。随机配对方法是仓库货位分配中常采用的配对方法，设种群个体数目为N，进行配对时按随机方式将其分为N/2组，在组内部的两个体进行交叉运算。根据前述编码方式的设计，本文选择三点交叉方式进行交叉运算，交叉运算示意如图1。

图1 交叉运算操作

③变异运算。

遗传算法的运算可使部分个体或染色体失去基因的多样性，这其中可能包含有用基因，变异操作即是为了避免遗失部分有用的遗传基因，避免失去检验有用基因的机会，从而保障解的质量。变异运算在遗传算法中充当的角色是一种辅助手段，以相对于交叉概率来讲的小概率来变换个体中部分基因。本文的变异操作采用基本位变异法，即在(0，1)之间随机生成一个数，若该数小于变异概率，则执行变异操作，反之则不执行。仓库货位分配中的个体值为一种货位分配排列，执行变异操作时，要注意货架层、列、排的对应，例如，在操作时要设置好在第4和第10基因座进行操作。变异运算示意如图2。

图2 变异运算操作

4 实验仿真与结果分析

根据前述建模过程，采用MATLAB工具对抽象出的货位分配模型及其求解进行测试验证。具体相关仿真数据设定如表1所示。

4.1 仓库基本参数

表1 仓库基本参数信息

4.2 货物基本信息

本文选择20件货物作为仿真数据，其中货物的重量是分拣后托盘和货物的总重量。货物的周转率根据以往数据求得。如表2所示。

表2 货物信息表及仿真结果

4.3 遗传算法参数选取

遗传算法参数的选取会影响最终输出结果的优劣，因此，在进行仿真的时候要对参数进行测验，但考虑仿真结果的客观性，程序中初步选取的遗传算法参数为：初始种群规模M为200，最大进化代数T为500，交叉概率pc为0.4，变异概率pm为0.05。

双种群遗传算法的货位优化结果如表所示，本文设定三个货位优化原则同等重要，即θ1=0.33、θ2=0.33、θ3=0.33。可以发现经过优化后，货物的出入库距离、货物出入库时间、货架稳定性等方面均有一定提升，货物的摆放更加规范，表明双种群遗传算法能有效给货位优化问题提供解决方案，验证了提出方法的有效性。

图3 平均计算时间随M变化的曲线

为了更好地对比双种群遗传算法相比传

统遗传算法的优越性，计算了两种算法的平均计算时间的变化情况，对比结果见图3。通过MATLAB的仿真实验可以看出：双种群遗传算法具有更高的计算效率，改善了基本遗传算法容易陷入局部最优解的缺陷，提高了货位分配策略的效率和结果的可靠性。

5 结束语

本文采用双种群遗传算法(DGA)对AS/RS货位分配策略进行优化研究，在得出最优分配策略的同时验证了算法的有效性，并将其平均计算时间等方面与传统遗传算法进行了对比，充分体现出了DGA在货位优化方面的优越性和可靠性，一定程度上改善了遗传算法迭代次数多、收敛速度慢等问题。但对于仓库货位优化问题，包括各类构造不同的仓库以及用怎样的智能算法和改进策略还需要进一步的研究和探讨。