The Multi-period Petrol Station Replenishment Problem: Formulation and Solution Methods

Luke Boers, Bilge Atasoy*, G. Homem de Almeida Correia, Rudy R. Negenborn

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

5 Downloads (Pure)


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.

Original languageEnglish
Title of host publicationComputational Logistics
Subtitle of host publicationProceedings of the 11th International Conference, ICCL 2020
EditorsEduardo Lalla-Ruiz, Martijn Mes, Stefan Voß
Place of PublicationCham, Switzerland
ISBN (Electronic)978-3-030-59747-4
ISBN (Print)978-3-030-59746-7
Publication statusPublished - 2020
Event11th International Conference on Computational Logistics, ICCL 2020 - Enschede, Netherlands
Duration: 28 Sep 202030 Sep 2020

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference11th International Conference on Computational Logistics, ICCL 2020

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.


  • Decomposition heuristic
  • Inventory routing
  • Petrol Station Replenishment
  • Simultaneous dry run inventory policy


Dive into the research topics of 'The Multi-period Petrol Station Replenishment Problem: Formulation and Solution Methods'. Together they form a unique fingerprint.

Cite this