This paper describes a planning problem faced by a fast-growing petroleum company in West Africa. The problem is a complex variant of the petrol station replenishment problem. It integrates the truck loading problem and the inventory routing problem. We tackle this problem in two steps. In the first step, we use Branch-and-Price to solve the weekly case where each petrol station can be visited more than once each week within the horizon. In the second step, we use Benders decomposition to solve up to four months horizon. Numerical results on a real network with up to four depots, four types of petrol products, four main groups of petrol stations, and a heterogeneous fleet of highly compartmented tank trucks prove the effectiveness and high potential of the proposed approach. They also highlight optimization's impact on Africa and the petrol station replenishment practice on the continent.