自动化分拣仓库中多自动导引小车在线协同调度算法  

Multi-AGV online collaborative scheduling algorithm in automated sorting warehouse

作　　者：余娜娜 李铁克[1,2] 王柏琳[1,2] YU Nana;LI Tieke;WANG Bailin(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]北京科技大学经济管理学院,北京100083 [2]钢铁生产制造执行系统技术教育部工程研究中心,北京100083

出　　处：《计算机集成制造系统》2022年第11期3340-3353,共14页Computer Integrated Manufacturing Systems

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

摘　　要：针对实时动态环境下自动化分拣仓库中多自动导引小车(AGV)任务指派和路径规划的协同调度问题,以最小化加权总搬运完成时间为目标建立了混合整数线性规划模型,并提出一种集中与分散决策相结合的在线协同调度算法。算法通过集中决策实时统筹仓库系统的全局信息,并将AGV视为具有决策能力的智能体(Agent),基于分散决策策略,由各AGV自主接收实时仓库信息并确定搬运任务和行走路径。为支持AGV决策,设计了基于优先规则的指派算法和基于栅格阻塞度的路径规划算法,实现了多AGV任务指派和路径规划的协同优化,并解决了多AGV间的冲突和拥堵。通过不同规模的仿真实验验证了所提算法的有效性。Aiming at the collaborative scheduling problem of multi-Automated Guided Vehicle(AGV)task dispatching and routing in automated sorting warehouse under the real-time dynamic environment,a mixed integer linear programming model for minimizing the weighted total handling completion time was established,and an online collaborative scheduling algorithm combining the advantages of centralized decision-making and decentralized decision-making strategies named Multi-AGV Online Collaborative Scheduling Algorithm(MAOCSA)was proposed.The algorithm coordinated the global information of the warehouse system in real time through centralized decision-making strategy and treats each AGV as an agent.The real-time warehouse information and determines handling tasks and conflict-free routes were received by each AGV autonomously based on the decentralized decision-making strategy.To support AGV decision-making,a dispatching algorithm based on priority rules and a conflict-free routing algorithm based on Grid Blocking Degree(GBD)was designed,which realized the collaborative optimization of multi-AGV task dispatching and routing,and solved the conflict and congestion among multiple AGVs.Extensive computational experiments with various problem scales were carried out,and the results showed that the MAOCSA was effective in solving the studied problem.

关 键 词：自动化分拣仓库 自动导引小车 在线协同调度 任务指派 路径规划 

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