<p>The 3-Path Vertex Cover Problem is an NP-complete problem in the field of combinatorial optimization. To overcome the problem of the Artificial Bee C olony algorithm (ABC) easily getting stuck in local optima, the paper proposes an improved Variable Neighborhood Search Artificial Bee Colony algorithm (VNSABC) by combining the Variable Neighborhood Search algorithm (VNS) with ABC. The proposed method uses opposition-based initialization to improve the quality of the initial solution. During the onlooker bee phase, a framework of VNSABC is constructed to optimize the formula for generating candidate solutions and to form a set of neighborhood structures by using three neighborhood actions for searching and expanding the solution space. Twelve instance graphs of different sizes from public platforms verify the effectiveness of the algorithm. Comparative experiments were conducted with the ABC, the improved Artificial Bee Colony algorithm (IABC), and the Particle Swarm Optimization-enhanced Artificial Bee Colony algorithm (PSOABC). Under identical initial parameters, it was found that the VNSABC outperformed the other algorithms in solving the 3-Path Vertex Cover Problem, yielding superior 3-path vertex cover numbers. Finally, statistical tests demonstrate the feasibility and effectiveness of the proposed algorithm.</p>