Guided by a real case, this paper efficiently proposes a new metaheuristic algorithm based on Simulated Annealing to solve the Heterogeneous Vehicle Routing Problem with Time Windows to deliver fresh meat in urban environments. Our proposal generates an initial feasible solution using a hybrid heuristic based on the well-known Travelling Salesman Problem (TSP) solution and, subsequently, refining it through a Simulated Annealing (SA). We have tested the efficiency of the proposed approach in a company case study related to the planning of the transportation of a regional distribution center meat company to customers within the urban and rural perimeter of Bogotá, Colombia. The main goal is to reach a service level of 97% while reducing operational costs and several routes (used vehicles). The results show that the proposed approach finds better routes than the current ones regarding costs and service level within short computing times. The proposed scheme promises to solve the refrigerated vehicle routing problem.