Abstract: For the complex multi-objective scheduling problem of heterogeneous autonomous guided vehicle (MOSPHA-CP), considering both item correlation and priority constraints, a multi-objective optimization model was established. The model incorporated priority factors including penalty costs, customer credibility, order picking time requirements, item demand quantities, and customer grades. To efficiently solve this problem, an improved hybrid variable neighborhood search (HVNS) algorithm was proposed.A two-stage clustering combined with stochastic cost optimization mechanism was employed to generate high-quality initial solutions. A correlation-disruptive recombination mechanism was designed to perform neighborhood perturbations, and prevent the algorithm from premature convergence. Multiple neighborhood transformation operations were employed to execute a global search, and obtain higher-quality feasible solutions.Simulation experiments were conducted using IACO, GAVNS, and the improved HVNS algorithm.The effectiveness of the enhanced algorithm in solving MOSPHA-CP was validated by comparing performance metrics such as solution quality, convergence behavior, and Pareto front.The improved HVNS demonstrates a 30%–40% enhancement in solution quality compared to benchmark algorithms, while also exhibiting significant advantages in both convergence performance and Pareto front metrics, thereby validating its efficacy in solving MOSPHA-CP problems.