Heuristics for the multi-depot petrol station replenishment problem with time windows

► We provide a mathematical formulation of the problem considered. ► We present a brief review of the literature related to petrol station replenishment. ► A heuristic approach is proposed to solve real-life instances of the problem. ► A large numerical experience to assess the performance of the heuristic is reported. ► We show that the proposed heuristic outperforms published single-depot heuristics.