AGV作业调度模型及改进的DE算法研究

Research on AGV job scheduling model and improved differential evolution algorithm

AGV作业调度问题的求解结果对AS/RS的运行效率具有重要影响。通过必要的简化,建立了AGV作业调度问题的静态优化模型。可知静态AGV作业调度问题实质是一种带约束的多重TSP问题,属于典型的NP完全问题,目前还不存在可在多项式时间内求解的确定算法。提出了一种改进的差分演化算法用于求解该问题。为了适应AGV作业调度问题的特点,新算法设计了新的两段编码方法,对多个DE算子进行了改造。还提出了基于生存时间的种群多样性增强机制,用于增强算法的搜索能力,避免陷入局部最优。仿真实验显示,该算法可以有效提高AGV作业调度的效率,验证了相关改进机制的有效性。

The optimization of AGV job scheduling problem is crucial to the efficiency of AS/RS. The static optimization model of AGV job 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 problem, 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 this problem, this paper proposes an improved differential evolution algorithm, which includes a two fragment coding method and some improved DE operators in order to adapt to the characteristics of AGV job scheduling problem. In addition, a population diversity enhancement mechanism which is based on individual survival time is also proposed to enhance the search capa-bility of the algorithm, and to prevent the algorithm from falling into the local optimum. Simulation experiments show that the algorithm 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.