Abstract
We present a “rich” Petrol Station Replenishment Problem (PSRP) with real-life characteristics that represents the complexities involved in actual operations. The planning is optimised over multiple days and therefore, the new variant can be classified as the Multi-Period Petrol Station Replenishment Problem (MP-PSRP). A Mixed Integer Linear Programming (MILP) formulation is developed and a decomposition heuristic is proposed as a solution algorithm, which is evaluated with a case study from a real-life petrol distributor in Denmark. To determine delivery quantities, the heuristic uses the newly introduced simultaneous dry run inventory policy. A procedure is applied to improve the initial solution. A commercial solver is able to find feasible solutions only for instances with up to 20 stations and 7 days for the MILP model where optimality is guaranteed for instances up to 10 stations and 5 days. The heuristic on the other hand provides feasible solutions for the full case study of 59 stations and 14 days, within a time limit of 2 h.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Al-Hinai, N., Triki, C.: A two-level evolutionary algorithm for solving the petrol station replenishment problem with periodicity constraints and service choice. Ann. Oper. Res. 286(1), 325–350 (2018)
Archetti, C., Speranza, M.G.: A survey on matheuristics for routing problems. EURO J. Comput. Optim. 2(4), 223–246 (2014)
Azi, N., Gendreau, M., Potvin, J.Y.: An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles. Eur. J. Oper. Res. 202(3), 756–763 (2010)
Benantar, A., Ouafi, R., Boukachour, J.: A petrol station replenishment problem: new variant and formulation. Logist. Res. 9(1), 1–18 (2016)
Brown, G.G., Graves, G.W.: Real-time dispatch of petroleum tank trucks. Manag. Sci. 27(1), 19–32 (1981)
Caceres-Cruz, J., Arias, P., Guimarans, D., Riera, D., Juan, A.: Rich vehicle routing problem: survey. ACM Comput. Surv. 47(2), 1–28 (2014)
Coelho, L.C., Cordeau, J.F., Laporte, G.: Thirty years of inventory routing. Transp. Sci. 48(1), 1–19 (2014)
Coelho, L.C., Laporte, G.: Classification, models and exact algorithms for multi-compartment delivery problems. Eur. J. Oper. Res. 242(3), 854–864 (2015)
Cordeau, J.F., Laganà, D., Musmanno, R., Vocaturo, F.: A decomposition-based heuristic for the multiple-product inventory-routing problem. Comput. Oper. Res. 55, 153–166 (2015)
Cornillier, F., Boctor, F.F., Laporte, G., Renaud, J.: An exact algorithm for the petrol station replenishment problem. J. Oper. Res. Soc. 59(5), 607–615 (2007)
Cornillier, F., Boctor, F., Renaud, J.: Heuristics for the multi-depot petrol station replenishment problem with time windows. Eur. J. Oper. Res. 220(2), 361–369 (2012)
Cornillier, F., Boctor, F.F., Laporte, G., Renaud, J.: A heuristic for the multi-period petrol station replenishment problem. Eur. J. Oper. Res. 191(2), 295–305 (2008)
Derigs, U., Gottlieb, J., Kalkoff, J., Piesche, M., Rothlauf, F.: Vehicle routing with compartment: applications, modeling and heuristics. OR Spectr. 33(4), 885–914 (2011)
LLC Gurobi Optimization: Gurobi Optimizer Reference Manual (2019). http://www.gurobi.com
Kazemi, Y., Szmerekovsky, J.: Modeling downstream petroleum supply chain: the importance of multi-mode transportation to strategic planning strategic planning. Transp. Res. Part E: Logist. Transp. Rev. 83, 111–125 (2015)
Li, K., Chen, B., Sivakumar, A.I., Wu, Y.: An inventory-routing problem with the objective of travel time minimization. Eur. J. Oper. Res. 236(3), 936–945 (2014)
Macedo, R., Alves, C., De Carvalho, J.M., Clautiaux, F., Hanafi, S.: Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model. Eur. J. Oper. Res. 214(3), 536–545 (2011)
Ng, W.L., Leung, S.C., Lam, J.K., Pan, S.W.: Petrol delivery tanker assignment and routing: a case study in Hong Kong. J. Oper. Res. Soc. 59(9), 1191–1200 (2008)
Popović, D., Bjelić, N., Radivojević, G.: Simulation approach to analyse deterministic IRP solution of the stochastic fuel delivery problem. Proc. Soc. Behav. Sci. 20, 273–282 (2011)
Popović, D., Vidović, M., Radivojević, G.: Variable neighborhood search heuristic for the inventory routing problem in fuel delivery. Expert Syst. Appl. 39(18), 13390–13398 (2012)
Triki, C., Al-hinai, N., Kaabachi, I., Krichen, S.: An optimization framework for combining the petroleum replenishment problem with the optimal bidding in combinatorial auctions. Int. J. Supply Oper. Manag. 3(2), 1318–1331 (2016)
Triki, C.: Solution methods for the periodic petrol station. J. Eng. Res. 10(2), 69–77 (2013)
Vidović, M., Popović, D., Ratković, B.: Mixed integer and heuristics model for the inventory routing problem in fuel delivery. Int. J. Prod. Econ. Part C 147, 593–604 (2014)
Acknowledgements
We are grateful for the support of AMCS B.V. by providing the case study data, especially Jelmer Brandt and Kristian Milo Hauge with valuable contributions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Boers, L., Atasoy, B., Correia, G., Negenborn, R.R. (2020). The Multi-period Petrol Station Replenishment Problem: Formulation and Solution Methods. In: Lalla-Ruiz, E., Mes, M., Voß, S. (eds) Computational Logistics. ICCL 2020. Lecture Notes in Computer Science(), vol 12433. Springer, Cham. https://doi.org/10.1007/978-3-030-59747-4_39
Download citation
DOI: https://doi.org/10.1007/978-3-030-59747-4_39
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-59746-7
Online ISBN: 978-3-030-59747-4
eBook Packages: Computer ScienceComputer Science (R0)