General variable neighborhood search for the multi-AGV scheduling problem with sorting operations

Abstract

To solve the intractable multiple automatic guided vehicles (AGVs) scheduling problem encountered in the sorting processes of the logistics sorting centers,a large-scale AGV scheduling problem was studied on the basis of considering the sorting time windows and charging requirements.A general variable neighborhood search (GVNS) algorithm was proposed to minimize the makespan of the sorting operations,in which the assignment of transferring packages to AGVs and the sequence of sorting tasks for each AGV were determined.The traversal insertion heuristic was developed to generate the initial solution of the developed algorithm to ensure the constraint of time windows.Ten neighborhood operators were designed to optimize the initial solution for the iteration of the algorithm.Different sized test instances were compared,and the impacts of AGV charging rate and quantity configuration on sorting efficiency were analyzed.The results show that the GVNS algorithm is superior in computing time and solution performance.It can obtain the approximate optimal solution in a short time.The average computing time of GVNS is only [BF]532.78[BFQ] s，which is obviously better than the mixed integer and constraint programming models;when the number of packages is 100,the most suitable number of AGVs is 14.Therefore,GVNS can effectively solve the large-scale and multi-AGV scheduling problem with charging demand and hard time window,improve the efficiency of logistics sorting,and help enterprises find the scientific and reasonable AGV configuration scheme.[HQ]

Keywords

• logistics system management; sorting operation; automatic guided vehicle; scheduling; charging demand; vari-able neighborhood search