In this paper, we solve a rich real-word Multi-Depot Multi-Period Petrol Replenishment Problem with a heuristic based on Branch-and-Price heuristic. The network consists of five distinct depots, a group of five private carriers with heterogeneous fleets of compartmented tank-trucks and five types of gas to replenish three main groups of clients on a weekly basis. Due to the hazardous nature of the products carried, some complex handling rules apply and are addressed in the column generation sub-problem as an Elementary Shortest Path Problem with Resource Constraints. Acceleration strategies are discussed. Numerical results on some real-world data show the effectiveness and high potential of the proposed approach.