We consider a real case study of a vehicle routing problem with a heterogeneous fleet and time windows (HFVRPTW) for a franchise company bottling Coca-Cola products in Colombia. This study aims to determine the routes to be performed to fulfill the demand of the customers by using a heterogeneous fleet and considering soft time windows. The objective is to minimize the distance traveled by the performed routes. We propose a two-phase heuristic algorithm. In the proposed approach, after generating an initial solution by a hybrid heuristic on the initial phase (first phase), a granular tabu search is applied during the improvement phase (second phase). Two additional procedures are considered to help that the algorithm could escape from local optimum, given that during a given number of iterations there has been no improvement. Computational experiments on real instances show that the proposed algorithm is able to obtain high-quality solutions within a short computing time compared to the results found by the software that the company currently uses to plan the daily routes.