自动分拣仓库中多载量AGV调度与路径规划算法  

Multi-load AGVs scheduling and routing algorithm in automatic sorting warehouse

作　　者：余娜娜 李铁克[2,3] 张文新[2,3] 袁帅鹏 张卓伦 王柏琳[2,3] YU Nana;LI Tieke;ZHANG Wenxin;YUAN Shuaipeng;ZHANG Zhuolun;WANG Bailin;+(School of Management Engineering,Zhengzhou University of Aeronautics,Zhengzhou 450046,China;School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China;Engineering Research Center of MES Technology for Iron&Steel Production,Ministry of Education,Beijing 100083,China)

机构地区：[1]郑州航空工业管理学院管理工程学院,河南郑州450046 [2]北京科技大学经济管理学院,北京100083 [3]钢铁生产制造执行系统技术教育部工程研究中心,北京100083

出　　处：《计算机集成制造系统》2024年第4期1458-1471,共14页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(72301026,71231001);教育部人文社会科学研究青年基金资助项目(17YJC630143);北京市自然科学基金资助项目(9174038);中央高校基本科研业务费资助项目(FRF-BD-20-16A);河南省科技攻关资助项目(242102220039)。

摘　　要：在自动分拣仓库中,多载量自动导引小车(AGV)具有强运输能力,但其多载量特征也增加了调度与路径规划的复杂性。针对多载量AGV调度与路径规划的协同优化问题,以最小化最大搬运完成时间为目标,建立了该问题的混合整数线性规划模型,并提出一种聚类协同优化算法。算法首先定义了包裹相似度,设计聚类算法划分包裹组,使每个包裹组可由多载量AGV在一次作业中完成分拣;进而针对问题的多决策特征,设计协同进化遗传算法对包裹组进行指派和排序,并将无冲突路径规划算法引入到协同进化遗传算法的解码方案中,用以搜索最优路径并解决多AGV路径冲突,从而实现了多载量AGV调度与路径规划的协同优化。通过不同问题规模的仿真实验验证了所提算法的高效性和稳定性。In an automatic sorting warehouse,the multi-load AGV has strong transportation capacity,but its multi-load characteristic also increases the complexity of scheduling and routing.Aiming at the collaborative optimization problem of multi-load AGVs scheduling and routing,a mixed integer linear programming model was established with the goal of minimizing the maximum handling completion time.Then,a Clustering-Collaborative Optimization Algorithm(CCOA)was proposed.Firstly,the package similarity was defined,and a clustering algorithm was designed to divide the packages into several groups,so that the packages contained in each group could be sorted by a multi-load AGV in one operation trip.Furthermore,according to the multi-decision characteristics of the problem,a Co-evolutionary Genetic Glgorithm(CGA)was designed to assign and sort the divided groups,and the conflict-free routing algorithm designed was embedded in CGA to search the optimal route and resolve the conflicts between multiple AGVs,so as to achieve the collaborative optimization of multi-load AGVs scheduling and routing.Extensive simulation experiments with different problem scales were carried out to verify the efficiency and stability of the proposed algorithm.

关 键 词：多载量自动导引小车 调度 路径规划 协同优化 自动分拣仓库 

分 类 号：TP29[自动化与计算机技术—检测技术与自动化装置]