Some Heuristic Methods for Discrete Facility Location with Uncertain Demands

Abstract

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
  España

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