Multi-AGV Task Scheduling And Routing In Automated Sorting System

The rapid development of e-commerce has led to a sharp increase in the number of express packages.In order to achieve efficient and accurate logistics operations,logistics companies have established automated sorting systems.Automated guided vehicle(AGV)is the core tool of the sorting system.How to perform task scheduling and routing for multiple AGVs is the key to the high quality and stable operation of the sorting system.The collaborative optimization of task scheduling and routing can significantly improve the sorting efficiency.Therefore,this dissertation studies the collaborative optimization problem of multi-AGV task scheduling and routing in the automated sorting system.The main work and contributions can be summarized as follows:(1)Aiming at the offline task scheduling and routing problem of single-load AGV with known package information,a mixed integer linear programming model is established with the goal of minimizing the maximum handling completion time,and an improved differential evolution algorithm(IDEA)is proposed based on the problem characteristics.In the algorithm,the real number coding strategy is used to represent the task scheduling scheme,and the dynamic differential evolution strategy is used to improve the convergence speed.Furthermore,a conflict-free routing algorithm is proposed,which is introduced into the decoding scheme of IEDA to search the optimal route and solve the conflicts between multiple AGVs,so as to realize the offline collaborative optimization of task scheduling and routing.Simulation experiments verify the effectiveness of the IEDA,and analyze its collaborative optimization effect.(2)Aiming at the online task scheduling and routing problem of single-load AGV with dynamic arrival of packages,a mixed integer linear programming model is established with the goal of minimizing the weighted total handling completion time.According to the characteristics of online environment,an online collaborative optimization algorithm combining the advantages of centralized decision-making and decentralized decision-making strategies is proposed.The algorithm coordinates the global information of the system in real time through centralized decision-making strategy and treats each AGV as an agent.Each AGV actively receives real-time information and determines handling tasks and conflict-free routes autonomously based on the decentralized decision-making strategy.Task scheduling decision and routing decision are carried out at the same time,and dynamically adjusted according to the real-time situation of the system,so as to realize the online collaborative optimization of task scheduling and routing.Simulation experiments compare the performance of different scheduling rules,and verify the effectiveness of the proposed algorithm.(3)The research object is extended to multi-load AGV,and the collaborative optimization of offline task scheduling and routing is studied.A mixed integer linear programming model is established with the goal of minimizing the maximum handling time and a clustering-collaborative evolutionary algorithm(CCEA)is proposed based on the problem characteristics.The algorithm first clusters the packages into several package groups,so that the packages contained in each group can 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 algorithm(CGA)was designed to assign and sort the divided groups,and the conflict-free routing algorithm is introduced into the decoding scheme of the CGA to achieve the offline collaborative optimization of multi-load AGVs task scheduling and routing.Simulation experiments verify the effectiveness and stability of the proposed algorithm,and analyze the key parameters.(4)Further considering the battery charging and the difference of package sorting time window,the online task scheduling and routing problems of multi-load AGVs are studied.A mixed integer linear programming model is established with the goal of minimizing the weighted sum of package delay cost and AGV operating cost,and an online collaborative optimization algorithm based on multi-attribute indicators(OCOAM)is proposed,which also combines the centralized decision-making and decentralized decision-making strategies,OCOAM considers a variety of attribute indicators of the system through centralized decision-making,and dynamically adjusts the attribute weight according to the real-time state of the system.In order to support the decentralized decision-making of multi-load AGVs,a progressive charging algorithm,an online task scheduling algorithm for multi-load AGVs,and an online routing algorithm for multi-load AGVs are designed to realize the online collaborative optimization of AGV charging,task scheduling and routing.The simulation experiments show that the OCOAM is effective in solving the studied problem.