This paper introduces a variant of the well-known Multi-Depot Periodic Vehicle Routing Problem, which is inspired by a real situation of a distribution company. The problem consists in determining the number of extra vehicles to rent, the assignment of vehicles to plants, and the routes between plants and distribution centers, while the transportation cost is minimized. We propose a mixed integer linear formulation and a Reactive Greedy Randomized Adaptive Search Procedure to solve the problem. Extensive computational results show that the proposed procedure provides high-quality solutions with an average gap lower than 2.5% from the computed lower bound.