Abstract: To address the complex multi-objective heterogeneous autonomous guided vehicle (AGV) scheduling problem (MOSPHA-CP) with constraints related to cargo association and cargo priority, a mathematical model was established considering factors such as default costs, customer reputation, picking time requirements, quantity of cargo required, and customer levels. An improved hybrid variable neighborhood search (HVNS) algorithm was proposed to solve this problem.The HVNS algorithm generated a better initial solution by combining a two-stage clustering approach with a stochastic cost-optimal mechanism. A relevance-based disruption and reorganization mechanism was designed to perform neighborhood perturbations and prevente the algorithm from premature convergence. Multiple neighborhood transformation operations were employed to execute a global search, aiming to obtain higher-quality feasible solutions. The improved HVNS algorithm and IACO and GAVNS algorithms were employed to conduct simulation experiments, and performance indicators such as solving speed, solution quality, and Pareto front were compared and analyzed to verify the effectiveness of the improved algorithm in solving MOSPHA-CP problems. The results show that the improved HVNS algorithm can effectively improve the performance of solution quality by 30%-40% compared to other algorithms, and its convergence and Pareto front indicators are significantly better than those of the compared algorithms. It is an effective method for solving the MOSPHA-CP.