【作者】 马永杰；

【导师】 蒋兆远；

【作者基本信息】 兰州交通大学 ， 交通信息工程及控制， 2011， 博士

【摘要】 自动化仓储系统(AS/RS)是现代物流和CIMS中的重要环节,对现代企业的生产发挥着日益重要的作用。AS/RS是一个离散的、随机的、动态的、多因素、多目标的复杂系统,对AS/RS的智能化管理将导致复杂的系统优化问题。大型仓储系统作为自动化仓储系统的一个重要发展方向,具有控制更为复杂、优化效率要求更高等特点,而传统的优化方法求解过程不仅时间较长、成本较高,而且不易求得最优解。本文将快速遗传算法的理论研究,与首都国际机场大型货运站仓储系统工程项目相结合,以进一步完善大型仓储系统的智能化管理、提高系统整体效率为目标,开展了大型仓储系统优化方法的研究。该项研究,对于提高大型仓储系统的智能化水平,提高仓库的运行效率,降低运行成本,提高物流运营企业和设计研发企业的竞争力等方面,都具有重要的工程意义；对于如何获得高效、稳定、可靠的快速遗传算法,遗传算法如何更好地模拟复杂系统的适应性过程和进化行为、在优化问题求解中如何才能具备全局攻敛性、搜索效率如何评价、如何与其他算法结合、如何更好地适应工程的需要等遗传算法的主要研究方向上,都具有重要的理论价值。论文主要工作如下：(1)以首都国际机场大型货运站仓储系统为例,分析了AS/RS,特别是大型仓储系统的工作流程和特点,提出了智能控制的方向和内容,建立了大型仓储系统的优化模型,选择遗传算法作为主要的优化算法,提出了大型仓储系统优化的目标函数和约束条件。(2)设计了一种快速单目标约束遗传算法。该算法提出一种既利用不可行解扩大搜索范围、又不引入惩罚因子的约束处理方法；设计了一种具有“记忆”能力的交叉算子,能够阻止个体的“返祖”现象,避免了重复搜索,提高了搜索效率；设计了搜索步长和方向可变的非均匀变异算子,可以保证算法在前期的快速搜索能力和后期的最优解的保持能力；采用“精英”保持策略,将父代的最优个体合并到子代,使算法具有较强的鲁棒性。.性能分析表明,该算法为1阶快速收敛的遗传算法,收敛速度优于其它3种对照的遗传算法,而且参数的选择对于算法的收敛速度没有本质的影响,一般能很快找到全局最优解或近似最优解。(3)设计了一种快速多目标约束遗传算法。该算法提出一种能够从可行解空间和不可行解空间同时搜索(边界搜索)的交叉算子,将约束条件和目标结合在一起,引入一种新的偏序关系用于比较个体之间的优劣；提出一种新的Niche值计算方法作为维持群体均匀性的主要动力,并采用已搜索解集避免了算法的重复搜索。采用Markov链作为分析工具,证明了算法的收敛性。仿真结果表明,与同类进化算法相比,该算法能够快速收敛到Pareto前沿,并能很好地维持群体的多样性。(4)采用遗传算法,进行自动化仓库的货位和拣选路径的优化。在AS/RS中,提出了基于随机存储策略的库区分配优化、货位分配优化、行驶时间优化的优化控制目标,采用罚函数法对堆垛机的容量和行驶速度、多任务作业周期中先存后取、由近及远存储、由远及近出库等约束条件进行处理。利用遗传算法,在已经存储一定数量的货物的大型自动化仓库中,求出了动态货位分配和拣选路径优化的Pareto最优解。实验表明,该方法能够很好地满足立体仓库优化控制的工程实际需要。(5)进行AS/RS中堆垛机动态待命位的研究。由存储时间优先的出库策略确定了m个可能的访问点{Pi|i=1,...,m},由随机存储策略得到了这m个可能的访问点分别具有的流通率{Ii|i=1,...,m},证明了这m个可能的访问点属于格拉斯曼空间。利用多质点重心法,通过格拉斯曼空间到仿射空间的映射,求出了堆垛机动态待命位。计算结果表明,该方法总体性能优于已有的研究结果。(6)在上述研究的基础上,分析了该大型仓储系统的性能。利用遗传算法确定了自动化仓库的动态拣选路径,采用多质点重心法获得了堆垛机的动态待命位,之后,利用堆垛机的加速和减速曲线,得到堆垛机在自动化仓库中的平均作业时间,最终获得该大型仓储系统的出入库能力,并分析了货位分配、拣选路径优化和堆垛机的动态待命位对提高出入库能力的贡献,从而也体现了本文研究的工程价值。本文的研究结果,已经在首都国际机场大型货运站仓储系统工程项目中部分使用,并取得了良好的优化效果。更多还原

【Abstract】 Automated storage and retrieval systems (hereafter, "AS/RS") have been a significant link in modern logistics and CIMS and have been playing an increasingly role in the production of modern enterprise. AS/RS is defined as a complex system with the discrete, random, dynamic, multi-factor and multi-objective characteristics. To realize the intelligent management for AS/RS leads to the complex optimization problems. As an important development for the automated warehousing system (AS/RS), the large warehouse systems are the kinds of systems which need more complex control strategies and higher optimize efficiency requirements. The traditional optimization methods for solving these problems require longer time, higher costs and more difficult to obtain the optimal solution.In this thesis, the optimization-methods researches of AS/RS are carried out by combining the theoretical research of fast genetic algorithms (hereafter, "GA") with the large warehouse system of institute of electrical and mechanical project of Beijing capital international airport in order to improve the intelligent management and the overall system efficiency of the large warehouse. The study has an important engineering significance for improving the intelligence level of the large warehouse system, increasing the warehouse efficiency, reducing the operating costs and improving the competitiveness of logistics operations, research and development enterprise. The important theoretical values of the research lie on the main research objectives of genetic algorithms, such as how to obtain an efficient, stable, fast and reliable GA, how to better simulate the adaptive process and evolution behavior of the complex systems, how to reach a global convergence in solving optimization problem, how to assess the search efficiency, how to combine with other algorithms and how to better meet the engineering needs.The main contents of the thesis are as follows:1. To take the catering automated warehouse of Beijing Capital International Airport as the example, the AS/RS workflow and characteristic are analyzed, especially for the large warehouse system. Then, the direction and content about intelligent control parts are proposed and the optimization models of the large warehouse system are established. In addition, GA is adopted as the main optimization algorithm with the optimization objective functions and the constraints of the large warehouse system.2. A fast single-objective constrained GA is designed. The constraint handling method of the algorithm is proposed by using infeasible solutions to expand the search scope and it can avoid the introduction of the penalty factor as well. Meanwhile, we designed a kind of "remember" cross-operator that could prevent the phenomenon of individual’s "atavism" avoid the repeated search and improve the efficiency of search. The mutation operators with the various step length and direction are developed to ensure the quick search capabilities in the early period and the retention capacity of the optimal solution in the later period. The elitism strategy is used to make the best individuals of the parent to pass down to their offspring. Thus, the algorithm has strong robustness. The performance analyses show that the algorithm is a first-order and fast convergence GA, which has the convergence rate three times over the other genetic algorithms. As for the convergence rate, it will be no influence with the different choice of parameters. Thus, this algorithm could find the global optimal solution after the fifth iterations.3. A fast multi-objective constrained GA is proposed. A kind of crossover operator that could simultaneously search from the feasible solution space to the infeasible solution space is designed. Combining the constraint conditions with the objectives, a new partial-order relation for comparing the merits among the individuals is introduced. Thus, a new Niche computation method for maintaining the diversity of population is suggested and the repeated search is avoided using the searched solution space. To use Markov chains as an anal tical tool, the convergence of the algorithm is proved. The simulation results show that this algorithm could rapidly converge at global Pareto solutions and maintain the diversity of population comparing with the current MOEAs.4. Genetic algorithms are adopted to optimize the cargo space and the picking-up path of the automated warehouse. For an AS/RS, the optimal control objectives, such as the optimal warehouse assignments, the optimal locations assignments and the optimal travel time, are proposed based on a stochastic storage strategy. To use the penalty function methods, the constraints conditions are handled including the capacity and the travel speed of storage/retrieval machines (SRMs), the rules of SRMs in a multi-command cycle such as storage first and retrieval last, storage from near to far and retrieval from far to near. The optimal Pareto solution of the dynamic location assignment and the optimal picking-up path were obtained by using GA in the large automated warehouse, in which some spaces have been already occupied. The experiments show that the methods proposed in the thesis could meet the practical engineering needs of the optimal control warehouse.5. The dynamic standby position of stacker is studied in the AS/RS. According to the library strategy of the storage time priority, m possible access points{Pi|i=1,..., m} are determined. The flow rates of those points are determined using random storage strategy one by one. Meanwhile, it has been proved that m possible access points were the parts of Glassman space. The dynamic standby position of stacker is solved by using multi-particle center of gravity method, which are the mapping from Glassman space to affine space. The results show that the overall performances of the proposed methods are superior to the existing research results. 6. Based on the above research results, the performances of a large storage system are analyzed. Dynamically selecting of the cargo space is determined by means of GA in automated warehouse and the dynamic standby position of stacker is obtained by using multi-particle center of gravity method. Moreover, we found the average operating time of the stacker in the automatic warehouse by the use of the acceleration and deceleration curves and obtained the storage capacity of the automatic warehouse ultimately. By then, the contribution of the improvement of out of storage capacity the location assignment, the optimal picking-up path and the dynamic standby position were analyzed. Accordingly, the results reflect the engineering value of this research project.The research results of the thesis have been partly implemented in the large warehouse system of Institute of Electrical and Mechanical project of Beijing Capital International Airport with the excellent optimization effect.更多还原