In the multi-period petrol station replenishment problem (MPSRP) the aim is to optimize the delivery of several petroleum products to a set of petrol stations over a given planning horizon. One must determine, for each day of the planning horizon, how much of each product should be delivered to each station, how to load these products into vehicle compartments, and how to plan vehicle routes. The objective is to maximize the total profit equal to the revenue, minus the sum of routing costs and of regular and overtime costs. This article describes a heuristic for the MPSRP. It contains a route construction and truck loading procedures, a route packing procedure, and two procedures enabling the anticipation or the postponement of deliveries. The heuristic was extensively tested on randomly generated data and compared to a previously published algorithm. Computational results confirm the efficiency of the proposed methodology. © 2007 Elsevier B.V. All rights reserved.