This paper has its focus on the vehicle routing problem (VRP) with he-terogeneous fleet multiple trips. Given the combinatorial nature of the problem, which practically precludes the exclusive use of mathematical programming methods, said exact, solution of real cases is typically done through heuristic methods. The real vehicle routing problems involve the use of different types of trucks and ,in some cases, support for multiple routes. As a contribution to this field of research, this paper describes an algorithm inspired on the Iterated Local Search heuristic applied on a real-life case problem, considering a hete-rogeneous fleet with optional multiple trips. The case study is based on a set of instances provided by a large European company, involving approximately 400 stores. Computational results show the effectiveness of the proposed algorithm, being able to reduce company expenses by up to 51100,00 EUR.