2014,50(9)
1 引言
随着信息化的深入,许多企业建立了自动化立体仓库
系统(Automated Storage and Retrieval System,AS/RS),
用于对生产物料和产品进行集中化的管理和配送。和
传统仓库相比,AS/RS 实现了货物存储的立体化、自动
化和智能化。而自动化搬运系统在其中扮演了重要角
色。常用的自动化搬运设备有堆垛机、传送带(轮)和自
动导 航小 车(Automatic Guided Vehicle,AGV)等 。 不
同规模的仓库会根据功能需求采用不同的搬运设备组
合。随着柔性制造需求的不断增长,AS/RS 与企业生产
环节逐渐相互融合,出现了集成生产的 AS/RS 系统。在
集成生产环境中,AGV是连接仓库和生产车间的重要纽
AGV作业调度模型及改进的 DE 算法研究
杨锋英
1
,刘会超
2
YANG Fengyin g
1
, LIU Huichao
2
1.黄淮学院 信息工程学院,河南 驻马店 463000
2.黄淮学院 网络信息管理中心,河南 驻马店 463000
1.School of Information Engineering, Huanghuai University, Zhumadian, Henan 463000, China
2.Center of Network Info rmation Management, Huanghuai University, Zhumadi an, Henan 463000, China
YANG Fen gying, LIU Huichao. Research on AGV job scheduling model and improved differential evolution algo-
rith m. Computer Engineering a nd Applications, 2014, 50(9):225-230.
Abstract:The optimization of AGV j ob scheduling problem is crucial to the efficiency of AS/RS. The static o ptimization
model of AGV jo b scheduling problem is established by some necessary simplification. It can be found that the AGV job
scheduling problem is actually a kind of constrained multiple TSP p roblem, and belongs to the typical NP-complete problem.
Therefore, there is no certainty algorithm now to solve the problem perfectly in polynomial time. To solve t his problem,
this paper proposes an improved differential evolut ion algorithm, whi ch includes a two fragment coding method and some
improved DE op erators in order to adapt to the characteristics of AGV job scheduling probl em. In addition, a population
diversity enhancem ent mechanism which is bas ed on i ndividual survival time is also propose d to enhanc e the search capa-
bility of the algorithm, and to p revent the algorithm from falling int o the loca l optimum. Simulation experiments show that
the algo rithm can greatly improve the scheduling efficiency of the AGV job scheduling problem, and the concerned improve-
ment mechanisms of the algorithm are proved to be effective.
Key words:Automatic Guided Vehicle(AGV); Job scheduling; differential evolution; intelligent algorithm; multiple Traveling
Salesmen Pro blem(TSP)
摘 要:AGV 作业调度问题的求解结果对 AS/RS 的运行效率具有重要影响。通过必要的简化,建立了 AGV 作业调
度问题的静态优化模型。可知静态 AGV 作业调度问题实质是一种带约束的多重 T SP 问题,属于典型的 NP 完全问
题,目前还不存在可在多项式时间内求解的确定算法。提出了一种改进的差分演化算法用于求解该问题。为了适
应 AGV 作业调度问题的特点,新算法设计了新的两段编码方法,对多个 DE 算子进行了改造。还提出了基于生存时
间的种群多样性增强机制,用于增强算法的搜索能力,避免陷入局部最优。仿真实验显示,该算法可以有效提高
AGV 作业调度的效率,验证了相关改进机制的有效性。
关键词:自动导航小车;作业调度;差分演化;智能算法;多重旅行商问题
文献标志码:A 中图分类号:TP301. 6 doi:10.3778/j.issn.1002-8331.1309-0055
基金项目:河南省科技攻关计划项目(No .112102210383)。
作者简介:杨锋英(1979—),女,讲师,研究领域为云计算、计算机网络、智能计算;刘会超(1982—),男,博士生,讲师,研究领域为
智能计算、云计算。E-mail:ziying661@163.com
收稿日期:2013-09-05 修回日期:2013-11-15 文章编号:1002-8331(2 014)09-0225-06
C omputer Engineering and Applicati ons 计算机工程与应用
225