Abstract: 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.

Key words: automated sorting warehouse, automated guided vehicle, online collaborative scheduling, task dispatching, routing planing

摘要： 针对实时动态环境下自动化分拣仓库中多自动导引小车(AGV)任务指派和路径规划的协同调度问题,以最小化加权总搬运完成时间为目标建立了混合整数线性规划模型,并提出一种集中与分散决策相结合的在线协同调度算法。算法通过集中决策实时统筹仓库系统的全局信息,并将AGV视为具有决策能力的智能体(Agent),基于分散决策策略,由各AGV自主接收实时仓库信息并确定搬运任务和行走路径。为支持AGV决策,设计了基于优先规则的指派算法和基于栅格阻塞度的路径规划算法,实现了多AGV任务指派和路径规划的协同优化,并解决了多AGV间的冲突和拥堵。通过不同规模的仿真实验验证了所提算法的有效性。

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