The Heterogeneous Fixed Fleet Vehicle Routing Problem (HFFVRP) is a variant of the conventional Vehicle Routing Problem (VRP). Compared with VRP, HFFVRP considers a fixed size of fleet with different types and variable costs of vehicles. There are three steps in our proposed metaheuristics. At first, we adopted the route-first cluster-second method considering average cost of used full loading vehicle types to construct the initial solution. And then used cross exchange, 2-opt* US, 2-opt and Or-opt to improve the initial solution. Finally, we applied restart threshold accepting to escape the constraint of local optimal solution. We compared our best results with Best Known Solutions (BKS) of HFFVRP benchmark instances. It showed that our proposed methods have generated 5 solutions reaching BKS. The average deviation of all the tested instances is 0.75%.