Abstract: The heterogeneous electric vehicle routing problem with time windows (HEVRPTW) was studied by comprehensively considering factors such as customer demand differences, vehicle heterogeneity, and charging constraints. A mixed-integer programming model aimed at minimizing total travel costs was constructed. A hybrid variable neighborhood search (HVNS) algorithm incorporating a hierarchical clustering mechanism was proposed for solution. The hierarchical clustering mechanism was utilized to spatially partition customer nodes, and a greedy algorithm was integrated to generate initial solutions. In the local search phase, multiple neighborhood operators, including single-point insertion, two-point exchange, two-segment exchange, and 2-opt, were combined. A charging station optimization strategy was introduced to enhance route selection. Simulation experiments were conducted based on standard test cases, and comparisons were made with the Gurobi solver and genetic algorithm (GA). Sensitivity analyses were performed on key parameters such as battery capacity, charging time, time window width, and vehicle number. The results show that the HVNS is able to obtain high-quality solutions comparable to Gurobi in a shorter time, which verifies the correctness of the model and its superior performance in solving problems of different scales. Compared with GA, the HVNS achieves a 10%–20% improvement in solution quality while demonstrating better stability and convergence. Through parameter optimization, the optimal configuration is determined (with a battery capacity of 150 kWh, charging time of 45 min, time window width of 90 min, and vehicle number of 8), achieving a balance between total travel cost minimization and customer satisfaction maximization. The findings confirm that the HVNS is an effective method for solving the HEVRPTW, providing a scientific decision-support tool for logistics enterprises in optimizing electric vehicle routing.