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

Abderrahman Bani, Issmail El Hallaoui, Ayoub Insa Corréa and Adil Tahir

European Journal of Operational Research, 2023, vol. 311, issue 1, 154-172

Abstract: 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.

Keywords: OR In developing countries; Mathematical programming; Branch-and-price; Petrol replenishment; Multi-compartment vehicle routing; Multi-depot multi-period vehicle routing; Heterogeneous fleet of vehicles (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723002989
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:311:y:2023:i:1:p:154-172

DOI: 10.1016/j.ejor.2023.04.016

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().