Some Heuristic Methods for Discrete Facility Location with Uncertain Demands

Published in International Series in Operations Research & Management Science, 2023


In this chapter, we delve into discrete facility location problems with inherent uncertainty, with a particular emphasis on cases where the service demand of each customer is governed by a Bernoulli distribution. Such problems are aptly modeled as a two-stage stochastic programming construct.

The initial stage dictates the decision to open a particular set of facilities while tentatively assigning customers to these open facilities. The subsequent stage deals with the precise assignment of customers to open plants, taking into account the possible realizations of customer demands. The primary goal revolves around minimizing the total cost: an amalgamation of the first-stage decision and the expected cost of subsequent recourse actions.

Real-world application of this problem poses a challenge since accurately evaluating the recourse function can become computationally intensive. This chapter elucidates the implementation of specific heuristics to mitigate this challenge. Both GRASP and Path Relinking are discussed in-depth as foundational components of a heuristic solution approach for the problem at hand.

Furthermore, we introduce mathematical programming formulations especially tailored for situations where uncertainties can be represented using a predefined set of scenarios. Such formulations find their applicability within a Sample Average Approximation algorithm framework. The chapter concludes with a detailed analysis and discussion on the computational experiments and their numerical outcomes.

Download the full chapter here

Authors & Affiliations

  • Maria Albareda-Sambola
    Department of Mathematics
    Universidad Nacional del Sur (UNS) – CONICET
    Bahía Blanca, Argentina

  • Elena Fernández
    Instituto de Ciencias Matemáticas

  • Francisco Saldanha-da-Gama
    Institute of Applied Dynamics
    Friedrich-Alexander-Universität Erlangen-Nürnberg