基于GA遗传算法的国家电网仓储分拣业务优化

金　鑫，于亮亮，金成明，张海全，粘中元JIN Xin，　YU Liang-liang，　JIN Cheng-ming，　ZHANG Hai-quan，　NIAN Zhong-yuan（. 中央财经大学 信息学院，北京 0008；.国网辽宁省电力有限公司信息通信分公司，沈阳 0006；.国网内蒙古东部电力有限公司信息通信分公司，呼和浩特 0000）

基于GA遗传算法的国家电网仓储分拣业务优化

金鑫1，于亮亮2，金成明2，张海全3，粘中元3
JIN Xin1，YU Liang-liang2，JIN Cheng-ming2，ZHANG Hai-quan3，NIAN Zhong-yuan3
（1. 中央财经大学 信息学院，北京 100081；2.国网辽宁省电力有限公司信息通信分公司，沈阳 110006；3.国网内蒙古东部电力有限公司信息通信分公司，呼和浩特 010020）

国家电网仓储业务的优化对于建立国网现代化物资管理体系、优化物资配送效率意义重大。为了提高仓储业务的工作效率，针对仓储业务中分拣环节存在的诸多问题，提出一种基于GA遗传算法的仓储分拣业务优化策略，通过建立仓储分拣业务模型，进行基于遗传算法的仓储分拣业务优化实验。实验结果表明，采用GA算法优化后，拣货时间、距离相较于优化前大为缩短，拣货工作效率得到显著提升，充分证明了本优化策略的可靠性。基于GA遗传算法的分拣业务优化策略，为国网仓储业务的优化提供了参考依据，为提高国网仓储运营效率，构建智能化仓储管理系统，建设现代化电网物资管理体系做了理论铺垫；同时，该策略对优化其他仓储类业务同样具有积极借鉴意义。

遗传算法；国家电网；仓储业务；分拣业务；优化

0　引言

国家电网对物资仓储的管理非常重视，尤其是仓储管理的信息化建设。根据国家电网关于仓储管理的相关规定，电网公司将以总部“虚拟仓库”为信息中心，自有仓储和供应商仓促相结合，构建中心库、区域库、周转库科学合理布局的智能化仓储网络。智能化库房是国网提倡构建的库房类型之一，其利用计算机、信息通信等方面的先进技术进行管理，提高了仓储配送能力和运营效率。管理和优化库区业务是国家电网打造精益高效物资管理体系的重要环节，货物的入库、分拣等业务都关联着电网物资的流动效率，尤其是分拣业务直接关联着后期物流配送环节和优化仓储业务。目前，物资管理分散、仓库利用率低是影响电力公司提高仓储管理水平的关键问题，鉴于此，合理优化仓储分拣业务，构建智能化仓储管理系统，对于建设现代化电网物资管理体系具有重大意义［1，2］。

实体库仓储的库区业务主要包括入库、上下架、分拣、盘点等内容，在整个物流体系中分拣业务是其中十分重要的一环。分拣作业的目的在于能够正确且迅速地集合用户所订购的物资产品，目前系统采取的分拣策略是完全顺序分拣作业策略，即：按照随机获取到的物资订单，除考虑拣货车的体积容量不进行任何优化，直接顺序组单由拣货人员拣取。该策略具有很大的随机性，若组单碰巧包含拣货位置集中的商品则拣货速度快，否则可能横跨多个区域拣货，造成拣货效率低下。除了分拣策略随机性问题外，货品储位未合理化存放、找不到货品或缺货率太高、无效走动等［3］问题同样会导致拣货效率低下。因此，利用合理高效的优化策略对仓储分拣业务问题进行优化亟待进行。

针对仓储业务中分拣环节存在的诸多问题，本研究以分拣业务为例，提出一种基于GA遗传算法的仓储业务优化策略，通过建立仓储分拣业务模型，进行基于遗传算法的仓储分拣业务优化实验。遗传算法在诸多行业中都有应用，其优点是在使用概率搜索技术的同时，进行解空间的多点搜索，避免了陷入局部最小值，增加了搜索的灵活性，提高了系统的计算速度［4～6］。本研究针对国家电网仓储分拣业务进行策略优化，旨在合理优化仓储分拣业务，提高国网仓储运营效率，为构建智能化仓储管理系统，建设现代化电网物资管理体系做铺垫。

1　基于GA算法的仓储分拣业务优化设计

1.1业务场景描述和优化建模

假设在某一个仓库内，共有s个摆放货物的货架（货架编号y=0，1，··，s-1）。其中，每两个货架为一组放置在一起，可捡取货物的一面朝外。两组货架之间有可供行走的通道，通道宽为h。每个货架长为b，宽为w，由n×m个大小相同的格子组成，每个格子都放有不同的货物，则第y个货架上的第z行第x列的货物的位置为（z，x，y），0＜z≤n，0＜x≤m。拣货员在横向方向上的速度为Vx，在纵向方向上的速度为Vy。货架摆放模型示意图如图1所示。

图1　货架摆放模型示意图

假设拣货员拿取同一列的货物的时间相同，那么在实际计算过程中，货物的编号可简化为（x，y）。假设tij为拣货员从货物i的位置到货物j的时间，dij是从货物i的位置到货物j的距离，则tij和dij的计算公式如下：

其中，xij和yij为货物i到货物j的横向和纵向距离，ya=y/2，yb=y%2。

拣货路径优化目标是拾取所有货物的时间和路径最小，因为所走路径和时间是线性正相关，所以可以组合描述如下：α，β是函数修正系数。

1.2基于GA遗传算法的模型优化求解

遗传算法模拟自然选择，将自然界的遗传进化理念运用到解决实际工程问题中。所谓自然选择通过优胜劣汰的方式使得逐代进行遗传进化，从而最终存活下来的物种具有最佳适应性。在具体实现上，先进行遗传算法种群初始化编码，将问题解集初始化，接着对种群进行遗传算法基本操作，计算个体适应度值。最后循环操作直至找到相对最优适应度值对应的个体即为问题的最优解。遗传算法基本操作包括：选择、交叉、变异。

求解优化目标的算法操作主要包括遗传算法中包含的种群编码、遗传操作、适应度计算等。

1）遗传编码与适应度函数

在求解上述优化问题时，多采用遍历货物的次序排列进行编码。例如编码123456表示自货物序号1开始，依次拾取货物2，3，4，5，6，最后返回出发点1。由于在可行解群体的初始化、交叉操作、变异操作均隐含求解的合法性约束条件，所以适应度函数取目标函数的倒数，即f=1/Z，无惩罚函数。

2）遗传算法操作

遗传算法操作主要包括：选择、交叉和变异。

交叉操作：第k个染色体ak和第l个染色体al在j位的交叉操作方法如下：

式中，b是［0，1］间的随机数。

变异操作：选取第i个体的第j个基因aij进行变异的操作方法如下：

式中，amax为基因aij的上界；amin为基因aij的下界；为一个随机数；g为当前迭代次数；Gmax是最大进化次数；r为［0，1］间的随机数。

遗传算法的优点是在使用概率搜索技术的同时，进行解空间的多点搜索，增加了搜索的灵活性，避免了陷入局部最小值；此外，遗传算法具有并行计算的特点，可通过大规模并行计算来提高计算速度。

2　仓储拣货业务优化仿真实验

2.1仿真实验数据准备

随机产生30个货物（编号为i=1，2，…，30），第i个货物为（xi，yi）。将所有的货物分为3组，拣货员需要往返3次才能取到所有货物。拣货员每次往返都从原点出发，依次拿取某一组中的货物，然后返回原点。假设所有货物都已包装，体积固定设为1；推车的体积为10。因此，拣货员每次至多拿取10个货物就要返回原处（0，0）。

根据前述的实验假设，列出如下所示的已知数据常量表和随机生成的货物数据表。

2.2实验计算与结果分析

基于前述的假设和仿真数据，本研究分别计算了优化前、顺序优化、GA遗传算法优化的结果，结果如表3所示。表中列出了优化的拣货路径和所需消耗的时间和路程。

1）未优化（优化前）的计算结果

根据前述tij和dij的计算公式，对于随机生成的30件货物全部货物捡取完毕的时间和距离分别为：时间=673，距离=1216。

2）顺序优化求解

所谓顺序优化是将待拣的货物分为三组，每组中拣货员从初始位置（0，1）从近到远拣货，此种方式与当前实际采用的拣货方式类似。采用顺序优化后的结果为：时间=448，距离=846。

3）GA优化求解

GA算法将问题的求解过程看成一个在候选解空间寻找满足问题要求的解或近似解的搜索过程，GA算法求解最优化问题的计算效率比较高、适用范围相当广。基于上一节中提出的优化策略，采用GA遗传算法进行优化求解。在GA求解中，我们设置种群规模为4，交叉率为0.99，变异率为0.01，适应度函数为f=1/ （0.08t+0.01d）。通过GA求解，GA第一代的求解结果为：时间=345，距离=618；GA第5代的求解结果为：时间=293，距离=538。

表1　常量数据

表2　随机生成的货物数据

表3　拣货过程的优化

根据前述计算结果，得到图2所示优化结果。

图2　优化前后效果比较

从图2可以直观看出，采用GA遗传算法优化后，拣货时间、距离相较于优化前大为缩短，拣货工作效率得到显著提高，充分证明了本优化策略的可靠性。

3　结论

针对仓储业务中分拣环节存在的诸多问题，本研究以分拣业务为例，提出一种基于GA遗传算法的仓储业务优化策略，通过建立仓储分拣业务模型，进行基于遗传算法的仓储分拣业务优化实验。实验结果显示：优化前t=673，d=1216；顺序优化后，t=448，d=846；GA遗传算法优化一代后，t=345，d=618。结果表明，采用GA算法优化后，拣货时间、距离相较于优化前大为缩短，拣货工作效率得到显著提升，充分证明了本研究优化策略的可靠性。基于GA遗传算法的分拣业务优化策略，为国网仓储业务的优化提出了参考依据，为提高国网仓储运营效率，构建智能化仓储管理系统，建设现代化电网物资管理体系做好了理论铺垫；同时，该策略对优化其他仓储类业务同样具有积极借鉴意义。

［1］ 李怀湘.仓储管理实务［M］.北京:北京大学出版社，2011:35-37.

［2］ 史建伟.浅析电力企业物资仓储的优化管理［J］.城市建设理论研究（电子版），2015.10.

［3］ 芦迁琨.国网冀北电力有限公司仓储配送管理优化［J］.现代商贸工业，2014，26（7）:168-168.

［4］ 陈国良，等.遗传算法机器应用［M］.北京:人民邮电出版社，2001:137-149.

［5］ 金鑫，潘宜安，吴靖.基于优化GA-BP神经网络的金融产品营销预测［J］.通信学报，2014，（Z2）:20-25.

［6］ 苏晨，李成义.基于遗传算法和BP神经网络的服装销售预测［J］.经营与管理，2012，2:052.

The optimization of state grid storage sorting based on Genetic Algorithm

F252；TP315

A

1009-0134（2016）06-0127-04

2016-04-25

国家自然科学基金（U1509214）；国网科技部项目（SGTYHT/14-JS-188）

金鑫（1974 -），男，教授，博士，研究方向为商务智能。