Lots of packages are sorted quickly by using multiple automatic guided vehicles (AGVs) in the logistics sorting centers. With the consideration of power consumption and charging demand of the AGVs, how to determine the assignment of transferring packages to AGVs and the sequence of sorting tasks for each AGV is the key to the sorting operation. In order to solve the large-sized problem instances, this paper proposes a general variable neighborhood search (GVNS) algorithm to minimize the sorting operation makespan. The GVNS algorithm adopts traversal insertion heuristic to generate the initial solution, and uses ten neighborhood operator to obtain the neighbor solutions. Different scaled test instances are used to analyze the performance of the proposed GVNS. Compared with mixed integer programming model and constraint programming model, the GVNS performs better, in terms of solution time and solution quality. Moreover, the impacts of the sorting efficiency are also analyzed when considering the AGVs with different charging speed and different available quantity. This work is helpful to improve the efficiency of logistics sorting, enrich the research content of multi-AGV scheduling.