In this paper, we study the Periodic Petrol Station Replenishment Problem (PPSRP), an important real problem relative to logistics in the fuel oil distribution. It consists, under suitable assumptions and subject to certain operational constraints, of determining the fuel oil procurement plans of a set of petrol stations and planning the delivering routes of petrol products to the stations along a certain planning horizon. The considered problem belongs to the class of Inventory Routing Problems (IRP), of which it is a particularization. In particular, it draws its concepts from two different classes of distribution problems, the Periodic Vehicle Routing Problem (PVRP) and the Petrol Station Replenishment Problem (PSRP). We provide a mathematical formulation of the problem, and due to the large size of the real instances which in general an oil company has to deal with we heuristically solve it. We propose different heuristic strategies based on a common partitioning-then-routing paradigm, and in order to assess their performances we test them on a set of scenarios coming from Italian fuel oil distribution real cases and compare the results with those obtained by using other known heuristic approaches.