Some Heuristic Methods for Discrete Facility Location with Uncertain Demands

In this chapter, we consider discrete facility location problems with uncertainty and focus on the case where the service demand of each customer follows a Bernoulli distribution. This problem can be modeled as a two-stage stochastic programming problem where the first stage determines a set of facilities to open together with a tentative allocation of customers to open facilities, and the second stage builds the actual assignment of customers to open plants for each possible realization of the customers’ demands. The objective is to minimize the sum of the cost of the first-stage decision plus the expected cost of the recourse action. Given that, in practice, the exact evaluation of the recourse function becomes computationally unaffordable, we illustrate the application of possible heuristics. We discuss GRASP and Path Relinking as the building blocks of a heuristic solution method for the considered problem. We also present mathematical programing formulations for the case where uncertainty is expressed by means of a given set of scenarios, which can be embedded in a Sample Average Approximation algorithm. Numerical results from computational experiments are discussed and analyzed.