ABSTRACT

Slotting optimization greatly affects the efficiency of automated power warehouse. This paper analyses warehousing efficiency and high-rise shelf stability, then constructs a multi-objective model of slotting optimization. An Improved Multi-Population Genetic Algorithm (IMPGA) which dominated by elite population is proposed to solve the problem. The simulation result shows that IMPGA is practical and effective. It has better convergence and can effectively improve the efficiency of material storage and shelf stability.

Keywords:Power Warehouse, Goods Location Assignment, Genetic Algorithm

基于改进多种群遗传算法的电力仓库货位分配

宋纪恩¹，薛劭节¹，冯曙明²

¹国网江苏省电力有限公司，江苏 南京

²江苏电力信息技术有限公司，江苏 南京

收稿日期：2018年11月30日；录用日期：2018年12月20日；发布日期：2018年12月27日

摘 要

针对江苏某电力自动化立体仓库货位优化分配问题，以出入库效率和高层货架稳定性为约束条件，建立了多目标的货位分配优化模型。提出了一种以精英种群为主导的多种群遗传算法用于求解优化模型。仿真实验结果验证了该算法具有更好的收敛性，能够有效提高物料出入库效率和货架的稳定性。

关键词 :电力仓库，货位分配，遗传算法

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

电力库存物资是电力检修、抢修等运维物资的主要供应形式，物资成本在供电公司基建及运维中占有很大比重。随着电力物资库存管理规模不断扩大，对电力仓库管理的标准化、规范化提出了更高的要求。充分利用现有的仓储资源，优化仓储货位分配，能够极大地提高电力仓库空间利用率和作业效率。

货位优化目标主要集中在改进仓库布局、提高物料周转率和降低仓储成本等方面。Park等 [1] 对货物出入库作业时间进行分析，将整个仓库存储区划分为货物高出入库频率储存区和货物低出入库频率储存区两类。Muppani [2] 构建了综合考虑产品组合、存储空间成本和订单拣选成本的商品分配级别及存储位置模型，并应用了模拟退火算法来求解复杂的二进制整数模型问题｡马永杰等 [3] 建立了多目标优化模型，并结合随机存储策略对立体仓库货位进行优化，使用Pareto遗传算法求解，得到最优货位分配方案。Li等 [4] 提出了一种基于改进遗传算法的货位分配优化算法，该算法中除了交叉和变异算子，还包括Pareto和小生境操作，从而提高了算法的性能。华红艳等 [5] 运用蚁群算法求解拣选路径优化问题，在算法设计中通过改进扰动分量，提高了算法运行效率。李敬波等 [6] 从提升仓库出入库效率、保证货架稳定性和货品分类摆放三方面进行货位优化，并利用遗传算法求解模型，实现了对目标函数的优化。李鹏飞等 [7] 通过病毒协同遗传算法(VEGA)实现了自动化立体仓库货位优化，有效提高货物出入库效率和货架的稳定性。

科学合理高效的电力物资入库货位优化方法十分重要。实现先进标准的电力仓储物资货位优化可以提高供电企业的仓储管理工作的效率和收益。本文针对电力自动化立体仓库的货位优化问题提出了一种改进的多种群遗传算法(Revised Multiple Population Genetic Algorithm, RMPGA)。该算法以精英种群为主导，通过精英种群、进化种群、搜索种群协同进化，有效的提高了算法收敛速度，保持了种群的多样性，避免算法早熟收敛。

2. 问题描述

在现代化的电力仓储管理中，主要通过ERP系统进行库存管理，通过自动化立体库进行仓库具体作业管理。自动化立体库也常被称为高层自动化仓库或者自动仓储AS/RS (Automated Storage and Retrieval System，自动存取系统)，主要由高层立体货架、巷道堆垛机、输送线等硬件设备以及WCS (Warehouse Control System，仓库控制系统)、WMS(Warehouse Management System，仓库管理系统)等软件组成，集物资存储、分类、拣选和动态管理等多项职能于一体，存储容量大、占地面积小、存取效率高、作业精度高。

在进行货位分配时，需要兼顾考虑物料入库作业和物料出库作业两方面。在满足物料出入库作业基本要求的基础之上，应考虑尽量提高物料出入库作业效率。同时，在实际操作过程中，还应该充分考虑存放物料后对货架稳定性的影响、存取便利性和安全性以及储存的物料之间是否有相互影响等因素。此外，在出库作业过程中为了保证物料的品质，通常采用先储存的物料优先出库的原则等。

电力自动化立体仓库的存储系统决定了整个仓库的运行效率。一个成功的货位分配策略可以缩短仓库堆垛机移动的距离，不仅可以节省能源、减少作业的时间，而且可以减小存储空间并减缓存储系统的磨损速度。

3. 模型构建

根据电力自动化立体仓库实际运行情况，有以下假设：

1、高层货架有a排b列c层。第x排y层第z列的货位标记为(x，y，z)， $x=1,2,3,\cdots ,a$ ； $y=1,2,3,\cdots ,b$ ； $z=1,2,3,\cdots ,c$ 。设置离出入口最近的一排为第1排，离出入口最近的一列为第1列，离地面最近的一层为第1层。

2、仓库中可存放Ｎ种不同的物料，相同种类的物料可以放在同一货位中(大小不得超过货位容量)，不允许同一货位中存放不同类型的物料。也就是一个托盘上只存放单一品种的物料。

3、每种物料的重量用M表示，物料的周转率用P表示，即某物料在一定时间内的周转次数为P。

4、每两排货架间有一巷道，巷道中有一台堆垛机。定义x方向水平运动速度是V_x；Y方向和Ｚ方向上运行速度分别为V_z和V_y。

1) 出入库效率原则

为了提高出入库效率，周转率高的物料应该离出入口较近从而使得总体的出入库时间较短。假设堆垛机取货时间可忽略，对于位于x排y列z层的货位(x, y, z)上的某物料，其出入库时间可简化为堆垛机运行时间，即 $\frac{x}{v_x}+\frac{y}{v_y}+\frac{z}{v_z}$ 。仓库在一定周期内的出入库效率可用以下函数表示：

$f_1=\underset{x=1}{\overset{a}{{\displaystyle \sum }}}\underset{y=1}{\overset{b}{{\displaystyle \sum }}}\underset{z=1}{\overset{c}{{\displaystyle \sum }}}\left(\frac{x}{v_x}+\frac{y}{v_y}+\frac{z}{v_z}\right)\cdot p_{x,y,z}$

2) 货架稳定性原则

为了保持仓库货架的稳定性，按照上轻下重、降低重心的原则，仓库货架的总重心可表示为 $f_2$ ：

$f_2=\frac{{{\displaystyle \sum }}_{x=1}^a{{\displaystyle \sum }}_{y=1}^b{M}_{x,y,z}\cdot z}{{{\displaystyle \sum }}_{x=1}^a{{\displaystyle \sum }}_{y=1}^b{M}_{x,y,z}}$

联立以上目标函数，可得货位优化模型为：

$\begin{array}{l}\{\begin{array}{l}\min f_1=\underset{x=1}{\overset{a}{{\displaystyle \sum }}}\underset{y=1}{\overset{b}{{\displaystyle \sum }}}\underset{z=1}{\overset{c}{{\displaystyle \sum }}}\left(\frac{x}{v_x}+\frac{y}{v_y}+\frac{z}{v_z}\right)\cdot p_{x,y,z}\\ \min f_2=\frac{{{\displaystyle \sum }}_{x=1}^a{{\displaystyle \sum }}_{y=1}^b{M}_{x,y,z}\cdot N_{x,y,z}\cdot z}{{{\displaystyle \sum }}_{x=1}^a{{\displaystyle \sum }}_{y=1}^b{M}_{x,y,z}}\end{array}\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}1\le x\le a\\ 1\le y\le b\\ 1\le z\le c\\ x,y,z\in Z\end{array}\end{array}$

显然，这是一个多目标优化问题，通过对设置权重，可将多目标问题转化成单目标问题：

$f={\varpi }_1\underset{x=1}{\overset{a}{{\displaystyle \sum }}}\underset{y=1}{\overset{b}{{\displaystyle \sum }}}\underset{z=1}{\overset{c}{{\displaystyle \sum }}}\left(\frac{x}{v_x}+\frac{y}{v_y}+\frac{z}{v_z}\right)\cdot p_{x,y,z}+{\varpi }_2\frac{{{\displaystyle \sum }}_{x=1}^a{{\displaystyle \sum }}_{y=1}^b{M}_{x,y,z}\cdot N_{x,y,z}\cdot z}{{{\displaystyle \sum }}_{x=1}^a{{\displaystyle \sum }}_{y=1}^b{M}_{x,y,z}}$

其中 $0\le {\varpi }_1\le 1$ ， $0\le {\varpi }_2\le 1$ 且 ${\varpi }_1+{\varpi }_2=1$ 。

4. 算法设计

遗传算法(Genetic Algorithm)是一种模拟自然界适者生存，优胜劣汰的寻优方式，广泛应用于求解复杂非线性最优化问题、复杂组合优化问题等。单种群遗传操作策略对初始参数较为敏感，算法收敛性能差，容易早熟、陷入局部最优。本文针对电力自动化立体仓库的货位优化问题提出了一种改进的多种群遗传算法(Improved Multiple Population Genetic Algorithm, IMPGA)。该算法引入了三个种群：精英种群、进化种群、搜索种群协同进化：精英种群通过选择算子保留了迭代中获得的较优解；在交叉操作中，进化种群、搜索种群中的个体通过与精英种群中个体交叉得到新的子代个体；各种群通过精英移民算子实现协同进化；搜索种群通过引入随机子代，保持了种群的多样性。具体算法流程如下：

Step1：初始化t = 0，种群规模N，随机初始化精英种群 $P_E\left(t\right)$ ，进化种群 $P_M\left(t\right)$ ，搜索种群 $P_S\left(t\right)$ ；

Step2：计算各子种群的适应度值；

Step3：pop1锦标赛选择，pop2轮盘赌选择；

Step4：pop0互相交叉，pop1与pop1交叉得newpop1，pop2与pop2交叉得newpop2；

Step5：各种群变异；

Step6：选择前M个优秀个体产生新的精英种群 $P_E\left(t+1\right)$ ；记录 $P_M\left(t\right)$ 中的最优个体M-elite(t)，记录 $P_S\left(t\right)$ 中的最优个体S-elite(t)，并用S-elite(t)替换 $P_M\left(t\right)$ 中适应值最小的个体；pop1优秀个体迁移，pop2随机个体；

Step7：判断是否满足终止条件；若是，则结束；否则转到step2。

4.1. 编码设计

在电力自动化立体仓库中，所有物料需要通过托盘完成入库、出库操作，并依托于托盘存放在货位上。入库就是为托盘寻找合适货位并通过堆垛机存放在该货位上的过程。考虑到在某一次入库操作时可选的空置货位数量是确定的，本文选择自然数编码的方法，每个个体的编码代表了一种可行的货位分配方案：染色体长度为此次分配中空置货位的数量，托盘编号用自然数表示作为染色体中的一个基因，基因所在位置表示为该托盘分配的货位位置，没有分配托盘的空置货位对应的基因为0。

4.2. 归一化适应度评价函数

根据建模过程中得到的函数模型，电力仓库货位优化问题为求函数的极小值问题，因此，采用原目标函数加1后取倒数来形成适应度函数，即：

$F=\frac{1}{{\varpi }_1{{\displaystyle \sum }}_{x=1}^a{{\displaystyle \sum }}_{y=1}^b{{\displaystyle \sum }}_{z=1}^c\left(\frac{x}{v_x}+\frac{y}{v_y}+\frac{z}{v_z}\right)\cdot p_{x,y,z}+{\varpi }_2\frac{{{\displaystyle \sum }}_{x=1}^a{{\displaystyle \sum }}_{y=1}^b{M}_{x,y,z}\cdot N_{x,y,z}\cdot z}{{{\displaystyle \sum }}_{x=1}^a{{\displaystyle \sum }}_{y=1}^b{M}_{x,y,z}}+1}$

4.3. 选择运算

在本文中使用锦标赛选择策略(Tournament Selection)，即每次选取一组(一般是2个)个体中适应值最高的个体作为新一代群体中的个体，重复这样的操作直到个体数达到群体规模。

4.4. 交叉运算

设交叉概率为 $p_c$ ，考虑到子代个体合法性，使用基于顺序的交叉方法(Order Crossover)，即先随机选择父代个体中一段基因，生成一个子代，并保证子代中被选中的基因的位置与父代相同，然后找出选中的基因在另一个父代中的位置，将剩余基因按顺序放入上一步生成的子代中。

4.5. 变异运算

本文采用基本位变异法实现变异运算。设变异概率为 $p_m$ ，考虑到个体的合法性，当个体满足变异条件时，随机选择变异点和交换点，直接交换位于变异点和交换点上的两个基因，从而形成合法的子代个体。

4.6. 移民算子

在多种群遗传算法中，各种群之间通过移民算子互相联系从而实现协同进化。本文提出的IMPGA以精英种群为主导，精英种群、进化种群、搜索种群进行协同进化。在进化过程中，采用精英移民算子将进化种群和搜索种群在进化过程中出现的最优个体引入精英种群中，搜索种群中的最优个体引入进化种群中，同时淘汰搜索种群中较差的一部分个体，引入新的随机个体以此来保证种群的多样性。

5. 实验仿真与分析

对于江苏某电力自动化立体仓库，该仓库配备高层立体货架共有6排20列4层，共计480个货位，水平方向使用传送带，垂直方向使用巷道式堆垛机，仓库和货位的相关参数见表1：

表1. 仓库运行参数

为了方便计算，假设传送带和堆垛机以恒定速度运行，启动和拣选物料的时间忽略不计。

以该仓库在2018年7月的运行数据为例，该月份上下架的主要物料见表2：

表2. 上下架物料数据

Continued

为了验证所提出IMPGA的有效性，运用IMPGA和MPGA、GA分别对模型进行求解，取交叉概率 $p_c=0.8$ ，变异概率 $p_m=0.01$ 。IMPGA中精英种群、进化种群、搜索种群规模设为30。MPGA中子种群数量设置为3。将IMPGA和MPGA、GA分别重复运行30次，记录每一次迭代中的最优适应度值，得到三种算法的平均收敛曲线如图1所示，记录每一次独立运算收敛后得到的最优适应度值，如图2所示。

在迭代过程中，IMPGA平均迭代至70代可以收敛获得最优解，MPGA和GA平均迭代至300次左右可以收敛。在多次重复数据实验，使用不同的随机初始种群情况下，IMPGA每一次都可以迅速寻找到最优解，MPGA寻找到最优解的质量略差，GA最差，由图2可见GA在迭代中易陷入局部最优，无法收敛。

可见，在三种算法中，IMPGA收敛速度最快，获得最优解的质量最稳定。MPGA收敛速度略慢，但是优于GA。经过多次独立运行，IMPGA能够稳定的获得最优解，MPGA不能每次都得到最优解，但是与GA相比，获得的解更接近最优解。也就是说，IMPGA收敛速度快、不易陷入局部最优值，在收敛速度、解的质量等方面均优于MPGA和GA。

图1. IMPGA、MPGA、GA多次独立运行最优适应度值迭代曲线

图2. IMPGA、MPGA、GA多次独立运行得到的最优适应度值

6. 结束语

电力物资仓储管理是电力物流流通的重要环节，货位优化分配能够在保证安全性的情况下使仓储空间货位达到最佳，有效提高仓库作业效率。本文以江苏某电力自动化立体仓库为研究对象，对货位分配优化方法进行了研究。首先，以货架稳定性以及出入库作业效率为约束条件，建立了货位分配优化模型；然后提出了一种改进的多种群遗传算法用于模型求解。最后，通过实验对模型及其求解方法进行了有效性验证。结果表明，该算法与经典多种群遗传算法相比能够更快收敛，能更稳定的获得最优解。

文章引用

宋纪恩,薛劭节,冯曙明. 基于改进多种群遗传算法的电力仓库货位分配
Slotting Optimization in Automated Power Warehouse Using Improved Multi-Population Genetic Algorithm[J]. 智能电网, 2018, 08(06): 610-616. https://doi.org/10.12677/SG.2018.86068

参考文献