This work deals with a variant of Heterogeneous Vehicle Routing Problem (HVRP) in the context of hazardous materials (HazMat) transportation. The objective is to determine the set of routes that minimizes the total routing risk. This function is considered as dependent of the vehicle load and the population exposure to an incident when the vehicle is traversing a path connecting two customers. As the total routing risk is a nonlinear function, a piece-wise linear approximation is used. An algorithm composed by a local search procedure, a perturbation movement, and a probabilistic acceptance criterion was implemented. The local search procedure utilizes six different inter-route neighborhood structures. Two are the building blocks for evaluating and implementing all the neighborhoods: concatenation of two routes and splitting of a route. The six neighborhoods are explored exhaustively and the evaluation of resulting routes is performed in constant time. The number of feasible solutions that can be reached from an initial solution, and the total relative improvement are defined as neighborhood characteristics. Three different neighborhood ordering were applied to solve some instances of the HVRP for HazMat transportation with unlimited fleet and fixed costs: random neighborhood ordering, increasing value of the total relative improvement, and decreasing value of the total relative improvement. The results obtained are competitive in terms of computational efficiency and solution quality in comparison to those found using a mixed integer linear programming solver.