Heuristics for a multi-period facility location problem with delayed demand satisfaction

Christophe Sauvey, Teresa Melo, Isabel Correia

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


We investigate a recently introduced extension of the multi-period facility location problem that considers service-differentiated customer segments. Accordingly, some customers require their demands to be met on time, whereas other customers accept delayed deliveries as long as lateness does not exceed a pre-specified threshold. In this case, late shipments can occur at most once over the delivery lead time, i.e. an order cannot be split over several time periods. At the beginning of the multi-period planning horizon, a number of facilities are in place with given capacities. A finite set of potential facility sites with multiple capacity levels is also available. The objective is to find the optimal locations and the opening, resp. closing, schedule for new, resp. existing, facilities that provide sufficient capacity to satisfy all customer demands at minimum cost. In this paper, we propose four heuristics that construct initial solutions to this problem and subsequently explore their neighborhoods via different local improvement mechanisms. Computational results with randomly generated instances demonstrate the effectiveness of the proposed heuristics. While a general-purpose mixed-integer programming solver fails to find feasible solutions to some instances within a given time limit, the heuristics provide good solutions to all instances already during the constructive phase and in significantly shorter computing times. During the improvement phase, the solution quality is further enhanced. For more than one-fourth of the instances, the heuristic solutions outperform the best feasible solutions identified by the solver.

Original languageEnglish
Article number106171
JournalComputers & Industrial Engineering
Publication statusPublished - 1 Jan 2020


  • Constructive heuristics
  • Delivery lateness
  • Facility location
  • Local improvements
  • Multi-period


Dive into the research topics of 'Heuristics for a multi-period facility location problem with delayed demand satisfaction'. Together they form a unique fingerprint.

Cite this