基于RFID和遗传算法的实时炸药仓储优化操作*

付华伟，何小敏，许 亮,，李秀喜，黄志平

(1.广东工业大学自动化学院，广东 广州 510006；2.华南理工大学化学与化工学院，广东 广州 510640；3.广东振声科技股份有限公司，广东 梅州 514795)

基于RFID和遗传算法的实时炸药仓储优化操作*

付华伟1，何小敏1，许 亮1,3，李秀喜2，黄志平3

(1.广东工业大学自动化学院，广东 广州 510006；2.华南理工大学化学与化工学院，广东 广州 510640；3.广东振声科技股份有限公司，广东 梅州 514795)

针对炸药仓储过程管理的优化问题，提出基于RFID和遗传算法的在线炸药仓储优化操作方法，使炸药仓储管理过程更具高效化、信息化、安全化和智能化。利用RFID技术实时获取炸药仓库信息，提出了炸药仓库库位分区策略。通过对炸药仓储工作特点及要求分析，建立炸药仓储的优化数学模型，并运用遗传算法求解模型得到优化解。实验仿真结果表明，该方法能够提高仓库的空间利用率，优化炸药存取过程的行走路径，较好地解决了受炸药有效期等约束的优化操作问题。

炸药仓储；无线射频识别技术；库位分区；遗传算法

1 引言

随着我国经济建设的快速发展，工业炸药的需求量大大增高，民爆行业伴随着这种需求得到较大发展。文献[1]指出，由于民爆行业的特殊性，出于多种因素考虑，该行业一直受到监管部门的严格控制，在炸药的仓储管理方面更是有着严格要求。而在炸药仓储管理中货位的分配及优化问题一直是一个急需解决的难题。高效的货位动态分配优化算法将提升企业在炸药仓储管理方面的效率。实时货位优化分配对降低仓库中货品搬运的成本、提高仓库的空间利用率及货品出入库的效率具有非常重要的现实意义。

炸药作为一种特殊物品，在仓储过程中存在一些特殊要求，目前关于炸药仓储研究并不多。李宇等[2]提出了RFID(Radio Frequency IDentification)技术在雷管产品安全管理中的应用。陈媛等[3]研究了基于RFID和GPRS( General Packet Radio Service)技术的危险品物流系统模型研究。炸药的仓储是一个复杂货物存取过程，属于组合优化问题，炸药包装过程中不同规格炸药装箱质量是相同的，同种规格炸药存取量大，对于相同规格和相同生产日期的炸药要考虑集中存放。针对上述问题，本文首先利用RFID技术获得炸药仓库的实时信息；然后对仓库进行分区处理；最后利用遗传算法求解优化模型，实现炸药仓储操作优化。

2 问题提出

炸药产品在生产、流通和使用过程中，都需要临时存放到仓库。炸药产品进出仓库时，同时有多种因素需要考虑：

(1)炸药的有效性问题。在仓库存放的炸药时间不易太长，如果超过一定时间，此类产品就需要优先出库，即炸药产品出入库应该遵循先入先出的原则。

(2)如果生产的炸药超过库存容量，就需先把旧的炸药产品出库，然后再入库新产品，这就是操作上的倒库。

(3)为了便于取货，把出入库频率高的炸药放在距离出入库口较近的地方。

为简化问题，现在考虑一个仓库的存储操作，最主要的参数是炸药的规格、入库的时间、每种规格炸药的出入频率以及行走路径长度。优化的目标是：先入库先出库、出入库频繁的炸药尽量靠近出入库口，尽量缩短行走路径。本文采用基于遗传算法的权重系数变换法解决货位动态分配优化问题。

3 炸药仓库优化操作计算模型

以前，工业炸药仓库的管理都是依赖于人工经验，存在工作效率低下、工人劳动强度大、仓库资源管理没有预见性等问题。针对这些问题，炸药仓库可利用RFID技术对炸药产品实行跟踪、定位，采用RFID对货品的各种相关信息进行记录，使仓库管理系统具备了可实时查询和定位货品的功能，克服了出入库管理和盘点困难的缺点。同时，由于获得了炸药存储的实时信息，也为采用一些优化策略实现对仓储资源管理的优化决策提供可能，以实现对库位的优化分配。

张海军等[4,5]指出炸药仓库常用的货位分配策略有多种，分类随机存储是其中的一种。该分配策略的特点是每一种货品有固定的存放区域，但在存放区域内货位的分配是随机的，优点是提高货位使用效率，缺点是出入库管理和盘点困难,图1为炸药仓库平面示意图。

Figure 1 Schematic diagram of warehouse storage图1 仓库存储示意图

由文献[6]可知，本文采用分类随机存储的方法，利用RFID技术获得炸药仓库的实时信息，然后利用遗传算法对这些数据信息进行处理，可以实现对炸药仓库库位的优化分配。

具体库位分区策略如下：

步骤1根据炸药的种类确定分区数目(例如有k种规格的炸药就把仓库分成k个区)。设仓库货位的长宽均匀，分别用a和b表示，仓储作业人员从原点(仓库的出入口)到某一货位的距离为dpq(货位在p行、q列)，所需时间为tpq，其中p、q为货格编码号。设某一时间值t(t为每个库区内行走标准时间，t的大小与分区数目有关),v为送货车辆行走速度，在水平方向和垂直方向相同。如果p行、q列货位满足下面公式(1)～公式(3)，则此货位位于k区：

(1)

(2)

(3)

步骤2经过步骤1得到的分区，可能各个区所包含的货位数目不相等。如果各区的货位数相差很大则需进行修正，修正的原则是“就近取多补少”，即如果某个区货位数较少，则从含货位数较多的相邻区取货位。

步骤3炸药的种类等于库区数目，计算出每种规格炸药的出入库频率。

步骤4建立权值矩阵，单位时间内送货车辆取放某种规格炸药的工作量与该货物的出入库频率、炸药存放的位置有关，将该货物的出入库频率乘以仓储作业人员到达存放位置所用时间作为权值因子，即：

(4)

其中，fk表示k区中的炸药出入库频率(这里的出入库频率指的是这个区中的炸药出入库频率)，sj表示仓储作业人员从原点到j区取放的距离(sj为j区所有货位到仓库出入口距离之和的平均值)。

考虑到仓库中保存时间不同的炸药要放在不同的位置,因此还要考虑炸药的出入库频率及货物保质期问题。我们把分成的k个区中每个区里炸药的保存时间记为Pk，因此可以得到一个炸药存储过程中的综合影响因子Wkj：

(5)

经过以上处理，炸药存放变为一个区内放入一类炸药，某一类炸药放入一个区后就不能再放入其他区，某一区放入一类炸药后也不能再放其他类的炸药，即变成为0-1指派问题，其数学模型如下:

目标函数：

(6)

约束条件：

(7)

(8)

其中,Xkj=1or0,k=1, 2,…,n；j=1, 2,…,n，n表示仓库分成的分区数，Xkj=1时k区放入j 类炸药，约束条件(7)表示一个区内只能放一类炸药，约束条件(68)表示一类炸药只能放在一个区内。

4 炸药仓储优化操作算法

基于遗传算法的炸药仓储优化算法如下所示：

步骤1编码。

由文献[7,8]可知，遗传算法应用的瓶颈之一是编码问题，本方案中采用实数编码顺序表达法。如果仓库分为15个区、存放15类规格的产品，采用顺序表达法时的某个染色体为[3 4 2 5 1 6 10 14 12 11 9 8 7 15]，该染色体表示第1个区放第3类炸药产品，第2个区放第4类炸药产品，依次类推。

步骤2适应度函数。

因为目标函数值为最小化问题，文中采用“限界构造法”，用一个适当的值cmax减去目标函数值。如货位分成n个区时， 适应度函数Fit(f(x))表示如下：

(9)

步骤3初始种群。

初始种群的产生和选择机制，根据分区的数目确定染色体的长度，初始种群的大小根据分区数目大小确定一个合适的值。假如分区数为15，即染色体长度为15，则可以选取产生初始种群数为40。选择过程采用转轮选择机制，适应度函数采用一个适当的值cmax减去目标函数值。

步骤4遗传算子交叉。

采用基于库区序列的编码，若使用单点交叉、双点交叉或多点交叉等常规方法，将会出现非法的染色体。为此，本文采用顺序交叉构建上述编码的交叉算子，染色体长度为15时交叉过程如下：

(1)在父代1(parent1)和父代2(parent2)中分别随机选择一段基因串(selectedsubsequence)，将这两段基因串复制到父代2和父代1的前面，于是得到两个新的染色体(parent12和parent21)。

(2)分别删除parent12 和parent21自添加了selectedsubsequence后重复的基因，得到所需的两个子代(offspring1和offspring2)。

步骤5变异。

变异算子主要有倒位、插入、移位、互换等。这里采用简单的互换操作，即首先在父体中随机地选择两个基因位，然后将该两点的基因进行交换。例如，有父体(5 9 10 1 2 3 4 6 7 | 8 11 12 13 | 14 15)，染色体截断位置如串中的‘|’所示，则将7和14交换，交换后的后代为(5 9 10 1 2 3 4 6 14 8 11 12 13 7 15)。

5 实验及结果分析

5.1 问题描述

某乳化炸药仓库有8行16列10层共1 280个库位，如图1所示(距离装卸口最近的为第1行，从上往下依次为1到16列)。本文对炸药仓库分区优化只考虑仓库的行和列，不考虑仓库库位的层数(同种规格炸药考虑集中存放，不同规格炸药装箱质量相同，因此对货架高度影响不明显)。然后开始对仓库进行分区，分区时遵循上文中的一些分区原则。

假设该仓库中存储的乳化炸药规格有15种，直径分别为16mm、32mm、50mm、60mm、70mm、80mm、90mm、100mm、110mm、120mm、130mm、140mm、150mm、160mm和180mm，把这15种规格的炸药分成15类，每种规格为一类，分别编号1～15。因此，仓库也要分成15个区，编号1～15。由于每类炸药的保存时间长短不同，每类炸药的保存时间用Pk表示，单位为月。每类炸药的出入库频率为fk，单位为吨(计算每天出入库量)。各个区距离出入口的平均距离为sj，单位为米(每个分区距离出入口距离)。根据上面的步骤以及实际情况得出保存时间系数Pk、出入库频率fk、各库区离出入口的距离sj；经计算统计分析出Pk、fk的值如表1所示。

Table 1 Save time of different explosive Pk andthe frequency of the ins and outs fk表1 不同规格的炸药对应的保存时间Pk以及出入库频率fk

sj(j=1..15)取值为14;23;28;33;36;40;43;46;49;53;56;66;67;71;80;然后，把保存时间系数Pk、出入库频率fk和各库区距离出入口的距离sj代入公式(7)和公式(8)表示的式两个约束条件中。Poon T C等[9]指出，遗传算法最终寻优结果和它的交叉率和变异率有着紧密的联系，所以要采用不同交叉率、变异率组合，判断在不同的交叉率和变异率时遗传算法寻找到的目标函数最优值。

5.2 实验仿真

本文采用Matlab 7.1根据实际的情况进行四组比较：交叉率Pc=0.8，变异率Pm=0.2；交叉率Pc=0.8，变异率Pm=0.1；交叉率Pc=0.9，变异率Pm=0.2；交叉率Pc=0.9，变异率Pm=0.1。

(1)当Pc=0.8，Pm=0.2，MAXGEN=200时实验结果如下:得出一条最优的染色体Chrom=(15 10 12 13 14 6 8 4 9 11 2 7 1 5 3)，即15类炸药放入15个库区的顺序是，第一个库区放第15类炸药，第二个库区放第10类炸药，以此类推。同时，可以得出一个目标函数最优值Y=15333，如图2所示。

Figure 2 Optimal solution of the objective function and performance tracking with Pc=0.8 and Pm=0.2图2 Pc=0.8,Pm=0.2时目标函数最优解及性能跟踪

(2)当Pm=0.8,Pc=0.1,MAXGEN=200时实验结果如下：得出一条最优的染色体Chrom=(15 12 11 13 14 3 9 5 8 10 2 7 1 6 4),即15类炸药放入15个库区的顺序是,第一个库区放第15类炸药，第二个库区放第12类炸药，以此类推。同时，可以得出一个目标函数最优值Y=15329，如图3所示。

Figure 3 Optimal solution of the objective function and performance tracking with Pc=0.8 and Pm=0.1图3 Pc=0.8,Pm=0.1时目标函数最优解及性能跟踪

(3)当Pm=0.9,Pc=0.2,MAXGEN=200时实验结果如下：得出一条最优的染色体Chrom=(15 11 12 13 14 5 9 3 7 10 2 8 1 6 4)，即15类炸药放入15个库区的顺序是,第一个库区放第15类炸药，第二个库区放第11类炸药，以此类推。同时，可以得出一个目标函数最优值Y=15309，如图4所示。

Figure 4 Optimal solution of the objective function and performance tracking with Pc=0.9 and Pm=0.2图4 Pc=0.9,Pm=0.2时目标函数最优解及性能跟踪

(4)当Pm=0.9,Pc=0.1,MAXGEN=200时实验结果如下：得出一条最优的染色体Chrom=(15 10 11 12 14 6 9 5 7 13 1 4 2 8 3)，即15类炸药放入15个库区的顺序是,第一个库区放第15类炸药，第二个库区放第10类炸药，以此类推。同时，可以得出一个目标函数最优值Y=15528，如图5所示。

Figure 5 Optimal solution of the objective function and performance tracking with Pc=0.9 and Pm=0.1图5 Pc=0. 9,Pm=0.1时目标函数最优解及性能跟踪

5.3 实验结果分析

在Matlab7.1下运行时，上面四组实验在寻优到最优结果的时间都很短，可以忽略不计，所以不考虑运行时间的影响，现在只考虑目标函数最优值Y。从图2～图5可以看出，每次进化不到200代时就可以寻优到最优解，把最大进化代数定为MAXGEN=200，同时选取的代沟GGAP=0.9。通过对不同的Pc、Pm取值，对目标函数值Y进行比较，比较结果如表2所示。

Table 2 Different crossing rate and mutation ratecorrespond to the objective function value表2 不同交叉率、变异率对应目标函数值

从表2可以看出，在交叉率Pc=0.9、变异率Pm=0.2的情况下，遗传算法找到最优解值15 309，这时对应的染色体为Chrom=(15 11 12 13 14 5 9 3 7 10 2 8 1 6 4)，即分好的15类炸药放入对应的15个区的顺序为，第一类炸药放入第15区，第三类炸药放入第12区，这样以此类推，把15类炸药放入对应的15个区中。这15类炸药分别代表15种规格的炸药，这样就可以优化出15种规格炸药分别放入15个库区的顺序，即直径分别为16 mm、32 mm、50 mm、60 mm、70 mm、80 mm、90 mm、100 mm、110 mm、120 mm、130 mm、140 mm、150 mm、160 mm、180 mm的炸药分别放入15、11、12、13、14、5、9、3、7、10、2、8、1、6、4区。

根据上文中的公式(1)～公式(3)式可以确定每个分区包含的库位在平面上所在的具体行和列，例如，图1中距离出入口最近的为1区，距离出入口最远的为15区，1区和15区的每个库位在图1中的位置用行和列标注出来，如库位(2,1)表示第2行第1列。根据分析认为16 mm规格的炸药放在15区，150 mm规格的炸药放在第1区。

从实验分析上来看，利用遗传算法能够为每种规格的炸药快速地找到对应的库位分区，使同种规格的炸药能够集中存储在同一库区，同时满足出入库频率高的炸药存储在离仓库口近的位置原则。

6 结束语

本文通过对炸药仓储工作特点及要求分析，建立了炸药仓储的优化数学模型，最后以某乳化炸药仓库为例，运用本仓库现有炸药仓储过程中的一些实际参数，用遗传算法对模型进行求解。实验仿真结果验证该方法的可行性，能够在一定程度上提高仓库的空间利用率，优化炸药存取过程的行走路径，较好地解决了受炸药有效期等约束的优化操作问题。本文研究中数据规模较小，随着数据规模的扩大将出现组合爆炸，利用遗传算法高效随机搜索与高效并行更能体现优越性。本文在考虑炸药仓储路径时只考虑了一个炸药仓库在二维平面上的路径，对于多仓库三维空间炸药仓储优化问题有待进一步研究。

[1] Sun Yong-bo,Zhong Feng.Current situation and development prospects of production equipment of emulsion explosives[J]Blasting,2010, 27(3):94-96.(in Chinese)

[2] Li Yu.RFID technology in detonator product safety steward of the application of the principle[D].Beijing:Beijing University of Science and Technology,2008.(in Chinese)

[3] Chen Yuan, Zhang Jing, Huang Li-feng. Study on dangerous goods logistics model based on RFID and GPRS[J]. Packaging Engineering, 2008,29(5):78-80.(in Chinese)

[4] Zhang Hai-jun,Yue Pu-xiu,Zhu Jie.A realization of optimal order-picking for irregular multi-layered warehouse[C]∥Proc of International Seminar on Business and Information, 2008:28-32.

[5] Zhang Hai-jun,Liu Bing-wu.A new genetic algorithm for order-picking of irregular warehouse[C]∥Proc of International Conference on Environmental Science and Information Application Technology, 2009:121-124.

[6] Zhang G Q, Lai K K.Combining path relinking and genetic algorithms for the multiple-level warehouse layout problem[J]. European Journal of Operational Research, 2004,29(9):413-425.

[7] Lam C H Y, Choy K L,Ho G T S.A hybrid case—GA-based decision support model for warehouse operation in fulfilling cross-border orders[J]. Expert Systems with Applications, 2012,39(8):7015-7028.

[8] Pang Long,Lu Jin-gui.Order picking optimization of automated warehouses based on the colony genetic algorithm[J].Computer Engineering & Science,2012,34(3):148-151.(in Chinese)

[9] Poon T C, Choy K L,Chan F T S, et al. A real time warehouse operation planning system for small batch replenishment problems in production environment[J].Expert Systems with Applications, 2011,38(1):8524-8537.

附中文参考文献：

[1] 孙永波,仲峰.乳化炸药生产设备现状与发展方向[J].爆破,2010,27(3):94-96.

[2] 李宇.RFID技术在雷管产品安全管理中的应用[D].北京:北京理工大学,2008.

[3] 陈媛,张静,黄丽丰.基于RFID和GPRS技术的危险品物流系统模型研究[J].包装工程,2008,29(5),78-80.

[8] 庞龙,陆金贵.基于蚁群遗传算法的自动化立体仓库拣选路径优化[J].计算机工程与科学,2012,34(3):148-151.

FUHua-wei,born in 1987,MS candidate,his research interests include intelligent control, and information processing technology.

何小敏(1961-),女,广东广州人，硕士，副教授，研究方向为计算机应用和物联网技术。E-mail:teacher_smc@163.com

HEXiao-min,born in 1961,MS,associate professor,her research interests include computer application, and Internet of things technology.

许亮(1971-),男,甘肃白银人，博士，讲师，研究方向为RFID及无线传感器网络。E-mail:celiangxu@gdut.edu.cn

XULiang,born in 1971,PhD,lecturer,his research interests include RFID and wireless sensor network.

李秀喜(1966-),男,湖南吉首人，博士，副研究员，研究方向为化工过程的控制与优化。E-mail:cexxli@scut.edu.cn

LIXiu-xi,born in 1966,PhD,associate research fellow,his research interest includes chemical process control and optimization.

黄志平(1958-),男,广东梅州人，高级工程师，研究方向为民爆器材行业信息化。E-mail:490659481@qq.com

HUANGZhi-ping,born in 1958,senior engineer,his research interest includes the industrial equipment industry informatization.

Aoptimizedreal-timeoperationforexplosivesstoragebasedonRFIDandgeneticalgorithm

FU Hua-wei1，HE Xiao-min1，XU Liang1,3，LI Xiu-xi2,HUANG Zhi-ping3

(1.Faculty of Automation,Guangdong University of Technology,Guangzhou 510006;2.School of Chemistry and Chemical Engineering,South China University of Technology,Guangzhou 510640;3.Gaungdong Zhengsheng Science and Technology Co. Ltd.,Meizhou 514795,China)

Aiming at optimization problems of management of explosive storage, an optimized on-line operation method of explosives storage based on the Radio Frequency IDentification (RFID) technology and genetic algorithm is proposed, making management of explosives storage more efficient, informatization, secure, intelligent. The information of explosives warehouse are acquired by RFID real-time technology, and an assignment strategy for location of explosive warehouse is proposed. The mathematical model of explosives storage optimization is constructed through analyzing operation characteristics of explosives storage and requirements, and the complicated model is solved by the genetic algorithm. The simulation results show that the proposed method can improve utilization rate of warehouse space, and optimize the walking path in the process of taking and putting the explosives, as well as solve the operating problems under the constraint condition, such as a validity of explosives.

explosives storage;radio frequency identification technology;storage location assignment;genetic algorithm

2012-08-13;

：2012-12-04

国家科技支撑计划课题(2012BAK13B02)；广东省重大科技专项(2012A080104012)；广东省绿色化学产品技术重点实验室项目

1007-130X(2014)02-0286-06

TP273.4

：A

10.3969/j.issn.1007-130X.2014.02.016

付华伟(1987-),男,河南信阳人，硕士生，研究方向为智能控制和信息处理技术。E-mail:328341683@qq.com

通信地址：510006 广东省广州市广州大学城外环西路100号广东工业大学工学二号馆自动化学院309室Address:Room 309,Faculty of Automation II Pavilion,Guangdong University of Technology,100 Outer Ring Rd West,Guangzhou University City,Guangzhou 510006,Guangdong,P.R.China