易燃品仓库群三维移动智慧巡检路径优化

郭凡 李东 许犇

摘 要：针对多个易燃品仓库的群巡检的智能滑块路径寻优问题，提出贪心遗传混合式路径优化算法，该算法将贪心策略融入到遗传算法操作过程，用作指导遗传选择操作进行搜索。首先建立仓库群巡检目标分配数学模型，其次设计一种基于贪心遗传混合式算法的三维移动巡检系统。对稀土金属库的规模不同的巡检点进行仿真，与常规的遗传算法和粒子群算法相比，平均巡检路径长度减少了15.2%，对103个巡检点巡检路径长度减少了6.1%.对1层库41个巡检点、2层库的51个巡检点、33层库的75个巡检点仿真结果表明，该方法避免了遗传算法的早熟问题，无论巡检的收敛速度还是巡检的最短路径均有明显改善。为保证安全，可在危险品大物资仓库推广使用，具有一定的应用价值和安全示范作用。

关键词：三维;贪心遗传算法;移动巡检;易燃品库;仓库群

中图分类号：TP 273+.5 文献标志码：ADOI：10.13800/j.cnki.xakjdxxb.2019.0123文章编号：1672-9315（2019）01-0160-08

Optimization of 3D mobile smart inspection path

for flammable goods warehouse group

GUO Fan1，LI Dong2，XU Ben2

（1.Graduate school，Xi’an University of Science and Technology，Xi’an 710054，China;

2.College of Electrical and Control Engineering，Xi’an University of Science and Technology，Xi’an 710054，China）

Abstract：Aim at flammable goods warehouse，a greedy genetic hybrid path optimization algorithm is proposed with Intelligent slider to solve the problem of searching the optimal path of warehouse group.The greedy strategy is integrated into the genetic algorithm，which is used as a guide for genetic selection in this algorithm.Firstly，the mathematical model for the distribution of warehouse inspection target is established.Secondly，a 3D mobile inspection system based on greedy genetic hybrid algorithm is designed to solve this problem.Next，different scale inspection points of rare earth metal libraries are simulated.Compared with the conventional genetic algorithm and the particle swarm algorithm，the average inspection path length is reduced by 15.2%，and the inspection path length of 103 inspection points is reduced by 6.1%.The simulation results of 41 inspection points in the 1st floor library，51 inspection points in the 2 layer library，and 75 inspection points in the 33 layer library show that the method can avoid the premature convergence，and regarding both the convergence speed of the inspection and the shortest path of the inspection，there is a significant improvement.The method has strong operability and high efficiency.It can be widely used in the warehouse group，which has certain application value and demonstration function for safety.

Key words：three dimension;greedy genetic algorithm;mobile inspection;flammable goods store;warehouse group

0 引 言

隨着科学技术的发展，危险化学品的使用量与存储量也急剧增加，加之危险化学品自身所具有的易爆、易燃、有毒、腐蚀、具有放射性等性质[1]，导致其在生产、经营、存储、运输、使用、废弃处置的过程中安全事故频发[2]。例如2015年8月12日，天津港“8·12”瑞海公司危险品仓库发生特别重大火灾爆炸事故。事故造成造成165人遇难，798人受伤[3]。2013年4月17日，美国德克萨斯州一家化工厂硝酸铵仓库着火，随即发生大爆炸。爆炸造成10栋建筑起火，70多栋住宅损毁，超过160人受伤，35人死亡[4]。从以上例子可以看出企业要在竞争日趋激烈的环境中发展壮大，必须要做好安全巡检工作并提高生各产环节的工作效率。而在仓库巡检过程中，如何花费最少的时间，以最短的路径巡检仓库所有存有货物的货位，这是仓库巡检目标分配问题中的一个重要研究内容。但是随着巡检滑块数目和待巡检点总数的增加，巡检分配复杂性成指数级增加，这使得巡检目标分配成为一个多参数，多约束的NP问题[5]，而对于多参数、多约束NP问题，常常采用穷举法[6]、分支界定法[7]、蚁群算法[8]、蜂群算法[9]、粒子群算法[10]、遗传算法[11]等求解，在这些算法中遗传算法得到的结果比较令人满意，然而当问题的规模增大时，优化搜索空间也会急剧增大，只使用遗传算法会导致很难搜索到最优解。因此，为了提高遗传算法的收敛速度和避免遗传算法早熟收敛，文中将贪心策略运用于遗传算法中，提出了贪心遗传混合算法（ greedy genetic hybrid path optimization algorithm，简称GGA）来解决仓库群三维移动巡检路径寻优问题。

1 系统总体方案设计

基于贪心遗传混合式算法的智慧仓库群三维移动监控系统将RFID技术、无线传感网络（ZigBee）技术[12]、多传感器融合技术[13]、步进电机精确定位技术[14]、云计算技术[15-16]等有机结合，国内外的专家对物流系统，以及对环境的监控作了大量研究[17-25]，提供了参考。本设计主要由RFID读写模块、传感器感知模块、电机控制器、三维立体轨道和上位机等构成。

针对稀土材料库，参考云计算访问控制技术[15]，构架的硬件部分将电机应用在三维轨道上，与多个红外避障传感器及温湿度传感器，气体浓度传感器等结合组成精确定位检测装置，该装置固定在自动化立体库巡检滑块上，通过RFID读写模块以及检测传感器模块获取仓储物品的存储状态信息以及仓库内部温湿度，烟雾浓度等信息。软件部分通过ZigBee网络与硬件部分联系，将构建一个云仓储模式下的体系结构。将分布式的仓储资源整合集中至一个统一的信息资源库中，该系统的总体结构如图1所示。

2 云仓储三维移动巡检路径优化问题描述

在巡检滑块移动巡检过程中，其轨迹一般有2种形式：由若干节点构成的开放直线型巡检轨迹和由若干节点围成的封闭曲线式巡检轨迹，巡检轨迹的2种类型如图2所示。

为了便于问题的描述和遗传算法的编码，这里提出2个创新性的特殊定义：①将一个由若干节点围成的封闭式曲线轨迹可以看成一个可控点集合Zi，轨迹的每一个节点都是既可以进入又可以退出的点;②将巡检过程中距离被巡检点最近的4个待巡检点定义为染色体片段集合Mj。根据以上表述的封闭式曲线轨迹巡检点集合Zi及染色体片段集合Mj，参考对于封闭式路径优化问题的描述，文中对智慧仓库云的巡检路径优化问题描述如下

给定n个巡检点集合Zi（i=，…，n），从上述给定的可控点集合Zi（i=，…，n）中选取任意一个可控点Zm作为初始节点，从染色体片段集合Mj（j=，3，4）中寻找下一个巡检点，给定其中n是集合中可控点的个数。巡检点i与巡检点j之间的距离为dij，求一条遍历Zi中每个巡检点一次的路线（Z1，Z2，…，Zn），使得整体巡回路程最短。因此首先引入决策变量Xij，Xij表示巡检滑块是否从巡检点i进入到巡检点j，其取值为0或者1，1代表巡检滑块从巡检节点i进入巡检节点j，否则为0.由此可得式（1）

xij=1，巡检滑块从节点i直接进入节点j

0，其他为求得最优巡检路径，用dij表示巡检点i与巡检点j之间的距离，用tij表示巡检点i与巡检点j之间的时间，因此可定义目标函数为

而为了保证每个巡检点只巡检一次，定义约束条件为式（3）和式（4），式（3）保证每个巡检点只离开一次，式（4）保证每个巡检点只进入一次

满足搜寻上述搜寻条件的合适路径，就是所求的最优路径。文中采用贪心遗传混合式算法来解决仓库群三维移动巡检问题。

3 贪心遗传混合算法的巡检轨迹路径优化

3.1 GGA算法的流程

巡检轨迹路径优化实际上是优化巡检滑块遍历所有有货物的货位即待巡检点。针对遗传算法在应用过程出现的收敛速度过慢，以及早熟收敛问题，文中提出了贪心遗传混合式算法，遗传算法被应用于个体中的全局搜索，而贪心算法在染色体中施行局部探寻。利用贪心算法来指导遗传算子进行操作，该方法规定了遗传算法的搜索方向，使得子代群体能在此方向前进，快速搜索到其它高质量的区域，也就是说，该方法将全局搜索改进成局部搜索，在相同条件下可提高优化巡检的速度。贪心遗传混合式算法（GGA）的流程如图3所示。

3.2 贪心遺传混合算法实现步骤

3.2.1 编码并构建基因库

任何一条哈密尔顿回路均是由无向带权图的所有顶点编号组成的一个排列，设对n个待巡检点编号并标记为i（i=，…，n），则由n个编号组成的全排列就是所有可能的巡检轨迹路径，那么最短的哈密尔顿回路即最优巡检路径肯定也包含其中，每一个数字是一个待巡检节点的编号，代表染色体的一个基因。每个染色体由n个基因组成，代表一条巡检路径，如（1，3，5，4，2）表示由初始位置1出发，依次经过巡检节点3→5→4→2，最后回到初始位置1的一条巡检路径。从距离1巡检节点最近的m个巡检节点按距离大小依次排序并编码，组成n×m阶矩阵构成“基因库”Qn×m，Qij元素（对应式（1）中Xij）为距离i点和第j点近的巡检节点编码，Qim为第i行元素为距离i巡检节点较近的m个巡检点的编码，Qi1，Qi2，Qi3元素分别为与i巡检节点最近、第二近和第三近的巡检节点，以此类推，排在前k位的巡检节点构成“染色体片段”，其中k

3.2.2 GGA的适应度值和操作概率

定义GGA的适应度值计算如式（5），定义贪心遗传概率如式（6）所示。

式中 p（i）为概率;fit（i）为当前的适应度值;n为巡检点个数，个;

dij（i）为当前巡检点i和巡检点j间路径的长度，m.据式（6）计算贪心遗传概率决定下一步执行哪种贪心操作。

3.2.3 初始种群生成或贪心选择

从初始巡检节点开始出发，从“基因库”Zi中第i行优先选择距离该巡检节点较近的巡检节点 Zj作为下一个巡检节点，再从第j行元素中选择较近的巡检节点并编码k，依次类推，在寻找下一个巡检节点l，最后遍历所有巡检节点，如果“基因库”中的巡检节点已在前面的编码选择中出现过，就随机生成另一个没有出现过的巡检节点。按照“基因库”生成的初始种群是从当前阶段看来最优解构成的集合，是一种贪心选择的策略。而按照这种方法生成的染色体片段，具有可定义长短，适应性好等特点。

3.2.4 贪心交叉

简单的遗传算法进化机制是通过保留优良的个体，使整个种群的性能得到提高，从而一步步的进行搜索，文中在进化过程中引入贪心策略，确定了个体的进化方向，降低了随机误差。交叉是通过组合父代双亲的优秀基因，生成更好的可行解，贪心交叉选择父代的第一个巡检节点，然后在双方父代中对比剩下的巡检节点，选择距离较短的巡检节点，继续进行巡检，如果该节点已在巡检过程中出现过，则选择另外一个较近的巡检节点，贪心交叉利用局部信息指导遗传进化选择，通过贪心交叉后的个体局部性能优秀。

3.2.5 贪心变异

在经过上一步贪心交叉选择出来的个体，并不能保证收敛于局部最优解，因此在其基础上引入贪心变异操作，运用相邻两节点交换的局部寻优方法，希望能找到局部最优解，如果交换的基因改进了算法的结果，就接受此交换，否则不进行交换，因此，贪心变异是一个局部改善和调整的过程。

3.2.6 移民操作

移民是指每隔数代就像种群中加入新的个体，前一代的种群里，排在末尾5%～15%的个体被随机产生的基因所代替，剩下的个体按照遗传操作优胜劣汰，进化过程后期，通过移民操作，增大移民个体数量，有利于跳出局部极值。虽然移民操作使种群总体性能有所下降，但是可预防早熟收敛。

3.2.7 终止算法

在遗传进化过程中无法用传统的方法来判断算法的收敛性，因而也就很难来终止搜索，文中通过采用遗传迭代停止条件，即首先设定最大进化迭代次数为N次，连续N次迭代后，如最终解没有改善，则停止搜索。

4 GGA算法仿真验证

4.1 巡检点均在一层的仿真

本实验的实验研究平台及货位如图4所示。图4（a）为稀土金属库外;图4（b）为库内部。

为了验证遗传贪心算法（GGA）在稀土金属巡检滑块移动巡检过程中算法的有效性，本实验选用稀土金属库的规模分别为14，51，103个巡检点的3个实例进行实验，并与基本遗传算法的求解情况进行对比，利用GGA算法及GA算法对上述3种情况分别进行60次独立实验，种群规模S=200，最大迭代次数i=500次，实验结果见表1.

经过对GA算法和GGA算法的对比，结果表明，GGA算法的巡检路径长度比GA算法平均路径长度减少了15.2%，对103个巡检点路径长度减少了6.1%;随着巡检点的增加，迭代次数减少的比率越高，巡检点路径长度减少的比率越小。文中提出的GGA算法比GA算法具有更快的收敛速度，克服了GA算法收敛速度慢的缺点。 为了验证算法的实用性，以甘肃稀土新材料有限责任公司自动化仓库群为例，该公司有5个大型物资仓库，每个仓库由2排，6层（每层20个货位），34列组成，共8 160个货位。以该公司物流中心某货架的一次巡检为依据，该次巡检过程中共41个待巡检货位，待巡检货物的货位坐标信息见表2.

应用贪心遗传算法，粒子群算法，贪心遗传算法对其巡检路径进行仿真，迭代次数均取200次，遗传算法及贪心遗传混合式算法种群个体为200个，在贪心选择后，交叉概率为0.6左右，变异率为0.1左右，对GGA算法巡检过程进行仿真，如图5所示。41个货位分布图如图5（a）所示，GGA算法路径规划图如图5（b）所示，GGA算法迭代（适应度值）曲线如图5（c）所示。

由表3可知，迭代到75次，GGA出现最优路径，最优路径为380.36 m，且路径平稳。

为了验证贪心遗传混合式算法的有效性，通过仿真实验将本次实验结果与粒子群算法，遗传算法结果相比较，粒子群算法（Particle swarm algorithm）优化路径结果如圖6（a）所示，遗传算法优化路径如图6（b）所示。

3种路径优化算法距离随迭代次数变化的数据结果对比见表4.从表4中可以看出，在同等条件下遗传贪心算法在75次就已经迭代收敛，粒子群算法也在200多次就开始迭代收敛，而普通遗传算法在300次左右才迭代收敛，因此可以看出贪心遗传算法在收敛速度较粒子群算法，普通遗传算法快，所以文中的遗传贪心算法迭代收敛速度方面明显优于遗传算法及粒子群算法。

4.2 多层立体库的巡检仿真

为了进一步验证文中提出的GGA算法的有效性，下面对图4的多层稀土材料库的货物进行巡检仿真，图7（a）为对稀土材料库的4，5层50个巡检点优化路径仿真;图7（b）为对稀土新材料库的4，5，6层75个巡检点优化路径仿真。

表5和表6分别列出了2层库和3层库的GGA算法的迭代收敛次数，从而可见，对2层库50个巡检点在172次迭代收敛到最短路径;对3层库75个巡检点在232次迭代收敛到最短路径;随着立体库层数和巡检点的增加，3层库与2层库巡检比较，增加25个巡检点后最优路径仅增加48.59 m.

5 结 论

1）云仓储三维移动巡检系统，可实现巡检滑块在危险场合代替人工巡检，避免了安全隐患的发生，并可提高巡检效率;

2）针对立体仓库三维移动巡检过程中存在的路径优化问题，提出贪心遗传混合式路径优化算法，提出“可控点”集合及染色体片段集合的概念，将可控点集合作为遗传算法的基因库，通过贪心策略选择出染色体片段，这种染色体片段具有可定义长短。该方法规定了遗传算法的搜索方向，使得子代群体能在此方向前进，快速搜索到其它高质量的区域;

3）利用稀土金属库规模不同的巡检点的仿真结果与一般的遗传算法相比，平均路径长度减少了15.2%，对103个巡检点路径长度减少了6.1%;以规模为41个巡检点仿真结果验证，文中GGA算法迭代75次是收敛380.36 m.随着巡检点的增加，迭代次数减少的比率越高，巡检点路径长度减少的比率越小，均比传统遗传算法及粒子群算法具有较明显的优势;

4）针对稀土材料库的2层50个巡检点和3层75个巡检点的仿真表明，文中GGA算法同样适应多层立体库的巡检。该方法在相同参数下的巡检路径最短，收敛速度更快。

参考文献（References）：

[1] 孙 猛，吴宗之，张宏元.危险化学品公路运输事故原因分析与对策[J].中国安全科学学报，2013（8）：151-155.SUN Meng，WU Zong zhi，ZHANG Hong yuan.Cause analysis and countermeasures for road transportation accidents of dangerous chemicals[J].Chinese Journal of Safety Science，2013（8）：151-155.

[2]Rey，Tseng，Chun Pin.Hazard management and risk design by optimal statistical analysis[J].Journal of Natural Hazards，2012，64：1707-1716.

[3]丁柏铨.浅议重大公共危机事件中新闻发言人的发言与舆论的关系[J].新闻大学，2013（4）：52-56.

DING Bo quan.The relationship between the speeches of the spokespersons and the public opinions in the major public crisis events[J].Journalism University，2013（4）：52-56.

[4]赵东风，韩丰磊，徐建军.警惕化学品“活性”危害[J].劳动保护，2016（11）：104-107.ZHAO Dong feng，HAN Feng lei，XU Jian jun.Be wary of chemical “activity” hazards[J].Labor Protection，2016（11）：104-107.

[5]LU Gang，HAO Ping.Recognition of CAPTCHA based on weighted template matching and supervised learning[J].Computer and Modernization，2010（12）：40-43.

[6]Hassanzadeh R，Mahdavi I，Mahdavi Amiri N，et al.A genetic algorithm forsolving fuzzy shortest path problems with mixed fuzzy arc lengths[J].Mathematical and Computer Modelling，2013，57（1）：84-99.

[7]Tanackov Ilija，Jankovi，Zdenko;Sremac，Sinia，et al.Risk distribution of dangerous goods in logistics subsystems[J].Journal of Loss Prevention in the Process Industries，2018，54（3）：373-383.

[8]Layeb Abdesslem，Benayad Zeyneb.A novel firefly algorithm based ant colony optimization for solving combinatorial optimization problems[J].International Journal of Computer Science and Applications，2014，11（2）：19-37.

[9]Kawata Yuko，Azuma Hiroyuki.Some approaches for optimizing CO2 storage system with water production in a heterogeneous reservoir using particle swarm optimization algorithm[J].Energy Procedia，2017，114（1）：4775-4786.

[10]李依桐，林 燕.基于混合粒子群算法的云計算任务调度研究[J].计算技术与自动化，2014，33（1）：73-77.LI Yi tong，LIN Yan.Research on cloud computing task scheduling based on hybrid particle swarm optimization[J].Computing Technology and Automation，2014，33（1）：73-77.

[11]Asta Shahriar，zcan Ender.A tensor analysis improved genetic algorithm for online bin packing[C]//Proceedings of the 2015 Genetic and Evolutionary Computation Conference，2015（11）：799-806

[12]LI Jian qiang，ZHANG Shen peng，YANG Lei.Accurate RFID localization algorithm with particle swarm optimization based on reference tags[J].Intelligent Fuzzy System，2016，31（5）：2697-2706.

[13]蔡益红.多特征融合的道路车辆检测方法[J].计算技术与自动化，2013，33（1）：98-102.CAI Yi hong.Multi feature fusion road vehicle detection method[J].Computing Technology and Automation，2013，33（1）：98-102.

[14]田子建，李宗伟.基于电磁波及超声波联合测距的井下定位方法[J].北京理工大学学报，2014，34（5）：26-29.TIAN Zi jian，LI Zong wei.Downhole positioning method based on electromagnetic wave and ultrasonic combined ranging[J].Journal of Beijing Institute of Technology，2014，34（5）：26-29.

[15]王于丁，杨家海，徐 聪，等.云计算访问控制技术研究综述[J].软件学报，2015，25（5）：1129-1149.WANG Yu ding，YANG Jia hai，XU Cong，et al.A survey of cloud computing access control technology[J].Journal of Software，2015，25（5）：1129-1149.

[16]陈 显，侯媛彬，宋柏佑.等.基于步进电机的小型三维运动物流系统设计[J].西安科技大学学报，2016，36（6）：868-874.CHEN Xian，HOU Yuan bin，SONG Bai you，et al.Design of small 3D movement logistics system based on stepper motors[J].Journal of Xi’an University of Science and Technology，2016，36（6）：868-874.

[17]沈 捷.快消品企业仓储管理系统的设计与实施[D].南昌：江西财经大学，2017.SHEN Jie.Design and implementation of storage management system for fast consumption enterprises[D].Nanchang：Jiangxi University of Finance and Economics，2017.

[18]林以成.基于 GPRS 技术的仓库监控系统[J].仪表技术与传感器，2018（8）：103-104.

LIN Yi cheng.Warehouse monitoring system based on GPRS technology[J].Instrument Technique and Sensor，2018（8）：103-104.

[19]馬殷元.物流装备控制和监控系统关键技术研究[D].兰州：兰州交通大学，2017.

MA Yin yuan.Research on key technologies of logistics equipment control and monitoring system[D].Lanzhou：Lanzhou Jiaotong University，2017.

[20]毕文俊.电信行业数据仓库数据质量管理系统设计与实现[D].北京：中国科学院大学，2017.

BI Wen jun.

Design and implementation of data quality management system for data warehouse in telecom industry[D].Beijing：University of Chinese Academy of Sciences，2017.

[21]Raitis Apsalons，Gennady Gromov.Methodology of evaluation of the impact of picking area location on the total costs of warehouse[J].Transport and Telecommunication Journal，2017，31（10）：332-344.

[22]李志宾.自动化立体仓库调度优化问题研究[D].太原：中北大学，2017.LI Zhi bin.Research on the scheduling optimization of automated stereo warehouse[D].Taiyuan：North Central University，2017.

[23]Theofania Tsironi，Peter Ronnow，Marianna Giannoglou.Developing suitable smart TTI labels to match specific monitoring requirements：the case of Vibrio spp.growth during transportation of oysters[J].Food Control，2016，41（6）：51-56.

[24]Holden R，Xu B，Greening P，et al.Towards a common measure of greenhouse gas related logistics activity using data envelopment analysis[J].Transportation Research Part A，2016，6（1）：105-119.

[25]Behmel S，Damour M，Ludwig R，et al.Water quality monitoring strategies：a review and future perspectives[J].Science of the Total Environment，2016，235（6）：1312-1329.