The truck loading and inventory routing problems are the two most important decisions made by companies replenishing petrol stations. This paper investigates a complex petrol station replenishment problem (PSRP) that integrates the truck loading problem (TLP) and the inventory routing problem (IRP). We introduce a compact mixed-integer linear programming formulation for the problem. Given its complexity, the compact formulation cannot be solved by general-purpose solvers, even for small instances. Driven by a decoupling intuition, we develop an exact two-phase solution approach that combines Benders decomposition and column generation. In the first phase, we solve the relaxed (integrality) Benders subproblems using column generation until the inventory levels stabilize. In the second phase, we solve the Benders subproblems using column generation embedded in a branch-and-bound framework. We enhance our approach with acceleration strategies, including warm-start, parallelism, a hashing technique, and a primal diving heuristic. Extensive computational results using real-world instances from a geographical zone in West Africa highlight the strength of our approach. We reach near-optimal solutions in all these instances and note that acceleration strategies significantly boost the performance of our two-phase method. We generate several managerial insights that highlight our approach's benefits.