Solving a real-world multi-depot multi-period petrol replenishment problem with complex loading constraints

In this paper, we address a new variant of the petrol replenishment problem (PRP), which is a rich real-word multi-depot multi-period problem (MDMPPRP). We show that it is possible to solve this complex variant with an exact branch-and-price approach and some derived heuristics. On one side, this problem could be modeled as a set partitioning type problem with low to moderate density (the number of ones per column, i.e., clients to visit, is not large). Such problems have some nice polyhedral properties to consider for favoring integrality. In the other side, some complex handling rules apply due to the problem’s context. A natural way is to address them in the column generation subproblem as an elementary shortest path problem with resource constraints, which constitutes the major bottleneck. To succeed in this challenge, we need to design some sophisticated techniques i) for branching to profit from the polyhedral properties and ii) for solving the column generation subproblem. Direct use of on-the-shelf algorithms does not work, unfortunately. Numerical results on a real network (four depots, five types of petroleum products, four main groups of clients, heterogeneous fleet of highly compartmented tank trucks) prove the effectiveness and high potential of the proposed approach.