基于多种群遗传算法的多AGV调度
|
摘要
针对多辆自动导引运输车在实际场景中的调度问题,为提高车间作业系统的效率,文中以AGV运行时间最短为目标,将多种群遗传算法引入到两阶段路径规划策略。先离线生成最短路径库缩减问题规模,降低在线调度的运算负担。当离线路径库不能满足调度要求时,再通过多种群遗传算法在离线路径库的基础上进行全局的路径规划。初步实验证明,该策略较好地提高了AGV调度系统的效率和鲁棒性,是一种能适用于不同地图的通用调度策略。
Direct at the scheduling problem of several automated guided vehicles in real scene,multi group genetic algorithm is introduced to the two-stage path planning strategy to improve the efficiency of the workshop operation system,which aims at the shortest run time of AGV. First,the shortest path library is generated in the off-line phase,which is used to reduce the scale of the problem,and then reduce the computing burden of online scheduling.When the off-line path library cannot meet the requirements of scheduling,the global path planning is carried out on the basis of the off-line path library,by invoke the multi-population genetic algorithm. The preliminary experiments show that this strategy has well improved the efficiency and robustness of AGV scheduling system,and it is a general scheduling strategy suitable for different maps.
Direct at the scheduling problem of several automated guided vehicles in real scene,multi group genetic algorithm is introduced to the two-stage path planning strategy to improve the efficiency of the workshop operation system,which aims at the shortest run time of AGV. First,the shortest path library is generated in the off-line phase,which is used to reduce the scale of the problem,and then reduce the computing burden of online scheduling.When the off-line path library cannot meet the requirements of scheduling,the global path planning is carried out on the basis of the off-line path library,by invoke the multi-population genetic algorithm. The preliminary experiments show that this strategy has well improved the efficiency and robustness of AGV scheduling system,and it is a general scheduling strategy suitable for different maps.
引文
[1] Corréa A I,Langevin A,Rousseau L M. Scheduling and routing of automated guided vehicles:A hybrid approach[J].Computers&Operations Research,2007,34(6):1688-1707.
[2] Smolic-Rocak N,Bogdan S,Kovacic Z,et al. Time-windows based dynamic routing in Multi-AGVs systems[J].IEEE Transactions on Automation Science&Engineering,2010,7(1):151-155.
[3]白帅福.基于混合区域控制模型的多AGV系统调度研究[D].南京:南京航空航天大学,2011.
[4]张峥炜,陈波,陈卫东.时间窗约束下的AGV动态路径规划[J].微型电脑应用,2016,32(11):46-49.
[5]刘国栋,曲道奎,张雷.多AGV调度系统中的两阶段动态路径规划[J].机器人,2005,27(3):210-214.
[6]李伟光,苏霞.基于改进A*算法的AGV路径规划[J].现代制造工程,2015(10):33-36.
[7] Lee J H,Lee B H,Choi M H. A real-time traffic control scheme of multiple AGV systems for collision free minimum time motion:a routing table approach[J]. IEEE Transactions on Systems,Man and Cybernetics Part A:Systems and Humans,1988,28(3):347-358.
[8]程传奇,郝向阳,李建胜,等.融合改进A~*算法和动态窗口法的全局动态路径规划[J].西安交通大学学报,2017,51(11):137-143.
[9]贺丽娜,楼佩煌,钱晓明,等.基于时间窗的自动导引车无碰撞路径规划[J].计算机集成制造系统,2010,16(12):2630-2634.
[10]张超勇,饶运清,李培根,等.求解作业车间调度问题的一种改进遗传算法[J].计算机集成制造系统,2004,10(8):966-970.
[11]李运霞,杜娟,孙王路.基于多种群遗传算法的路径柔性车间调度问题[J].组合机床与自动化加工技术,2014(3):152-155.
[12]叶宏雄.遗传算法种群跃迁现象分析及其应用[D].广州:华南理工大学,2014.
[13]汪民乐.遗传算法的收敛性研究[J].计算技术与自动化,2015(1):58-62.
[14]王雷,李明,蔡劲草,等.改进遗传算法在移动机器人路径规划中的应用研究[J].机械科学与技术,2017,36(5):711-716.
[15]Liu J,Wang Z,Xu Q,et al. Path scheduling for Multi-AGVs system based on two-staged traffic scheduling scheme and genetic algorithm[J]. Journal of Computational Methods in Sciences and Engineering,2015,15(2):163-169.
[2] Smolic-Rocak N,Bogdan S,Kovacic Z,et al. Time-windows based dynamic routing in Multi-AGVs systems[J].IEEE Transactions on Automation Science&Engineering,2010,7(1):151-155.
[3]白帅福.基于混合区域控制模型的多AGV系统调度研究[D].南京:南京航空航天大学,2011.
[4]张峥炜,陈波,陈卫东.时间窗约束下的AGV动态路径规划[J].微型电脑应用,2016,32(11):46-49.
[5]刘国栋,曲道奎,张雷.多AGV调度系统中的两阶段动态路径规划[J].机器人,2005,27(3):210-214.
[6]李伟光,苏霞.基于改进A*算法的AGV路径规划[J].现代制造工程,2015(10):33-36.
[7] Lee J H,Lee B H,Choi M H. A real-time traffic control scheme of multiple AGV systems for collision free minimum time motion:a routing table approach[J]. IEEE Transactions on Systems,Man and Cybernetics Part A:Systems and Humans,1988,28(3):347-358.
[8]程传奇,郝向阳,李建胜,等.融合改进A~*算法和动态窗口法的全局动态路径规划[J].西安交通大学学报,2017,51(11):137-143.
[9]贺丽娜,楼佩煌,钱晓明,等.基于时间窗的自动导引车无碰撞路径规划[J].计算机集成制造系统,2010,16(12):2630-2634.
[10]张超勇,饶运清,李培根,等.求解作业车间调度问题的一种改进遗传算法[J].计算机集成制造系统,2004,10(8):966-970.
[11]李运霞,杜娟,孙王路.基于多种群遗传算法的路径柔性车间调度问题[J].组合机床与自动化加工技术,2014(3):152-155.
[12]叶宏雄.遗传算法种群跃迁现象分析及其应用[D].广州:华南理工大学,2014.
[13]汪民乐.遗传算法的收敛性研究[J].计算技术与自动化,2015(1):58-62.
[14]王雷,李明,蔡劲草,等.改进遗传算法在移动机器人路径规划中的应用研究[J].机械科学与技术,2017,36(5):711-716.
[15]Liu J,Wang Z,Xu Q,et al. Path scheduling for Multi-AGVs system based on two-staged traffic scheduling scheme and genetic algorithm[J]. Journal of Computational Methods in Sciences and Engineering,2015,15(2):163-169.