The vehicle routing problem is a classic combinatorial optimization problem that has been proven to be NP-hard. It is widely applied to the fields of transportation logistics and intelligent manufacturing. However， such problems usually assume the homogeneity of vehicles， making it difficult to characterize the differences in vehicles transportation capabilities for different types of commodities in practical scenarios. To address it， a new heterogeneous vehicle routing problem （HVRP） is proposed. By introducing commodity type attributes and vehicle transportation capability constraints， an integer programming model describing the vehicle-order matching relationship is constructed， with the objective of minimizing the total transportation distance. The service relationship between vehicles and customers is formally described by modeling the transport capability of different vehicle types for various product categories. To achieve efficient optimization of the HVRP， a variable step multi-neighborhood search （VSMNS） algorithm is proposed， along with a solution representation method that combines path encoding with linked-list structures. Finally， comparative experiments are conducted among VSMNS with genetic algorithms， hybrid genetic algorithms and artificial bee colony algorithms on 15 test cases. Experimental results show that not only the VSMNS achieves excellent performance in solution quality， but also its performance advantages become more significant as the problem scale increases. Ablation experiments further verify the contribution of each component in the algorithm， demonstrating the effectiveness and superiority of the designed local operators.