Facility location under uncertainty: a review.

1. Introduction

Facility location decisions are costly and difficult to reverse, and their impact spans a long time horizon. During the time when design decisions are in effect, any of the parameters of the problem (costs, demands, distances) may fluctuate widely. Parameter estimates may also be inaccurate due to poor measurements or to tasks inherent in the modeling process such as aggregating demands points and choosing a distance norm. Recognizing this, researchers have been developing models for facility location under uncertainty for several decades.

The two-stage nature of facility location problems (choose locations now, before we know what the future holds, and react once the uncertainty has been resolved, say, by assigning customers to facilities) has made these problems very attractive to researchers exploring approaches to decision making under uncertainty. A large number of these approaches have been applied to facility location problems.

This paper aims to illustrate the rich variety of approaches to optimization under uncertainty by examining their application to facility location problems. To this end, we have chosen to categorize papers first by their approach to uncertainty, and then by the nature of the facility location problem they discuss. A few of the measures we discuss have not, to the best of our knowledge, been applied to facility location problems. We include these measures in our survey because of their relationship to measures that we do discuss, or simply because of the novelty of their approaches. In these cases, we provide examples from the literature on capacity planning, network design, or other logistics problems that, similar to facility location, involve a strategic phase during which capital investments are made, followed by a tactical phase, with uncertainty being resolved between the two.

In the interest of brevity, we have opted not to discuss the large body of literature on facility location problems with congested facilities, which attempt to capture the possibility that a customer may need service from a facility that is occupied with another customer. Such models are commonly used in the siting of ambulances, fire stations, and other emergency services. They attempt to guarantee adequate service either by requiring redundant coverage (as in Daskin (1982, 1983), ReVelle and Hogan (1989), and Ball and Lin (1993)) or by explicitly considering the queuing aspect of the problem (as in Larson (1974, 1975), Berman et al. (1985), and Marianov and ReVelle (1996)). The reader is referred to the surveys by Daskin et al. (1988) and Berman and Krass (2002) for thorough discussions of these models. A related branch of literature considers models in which the facilities may be unable to provide service due to facility disruptions (Bundschuh et al., 2003; Berman et al., 2004; Snyder and Daskin, 2005), or link failures (Nel and Colbourn, 1990; Eiselt et al., 1992).

Throughout this paper we assume that the reader has some familiarity with deterministic facility location theory. For an introduction to this topic, the reader is referred to the texts by Daskin (1995), Dresner (1995), or Drezner and Hamacher (2002). Louveaux (1993) reviews models for stochastic (but not robust) facility location. See Owen and Daskin (1998) for a survey on strategic aspects of facility location, including both dynamic problems and problems under uncertainty. Brandeau and Chiu (1989), Louveaux (1993), Daskin and Owen (1999), and Current et al. (2002) review both deterministic and stochastic facility location. Nikulin (2004) provides an annotated bibliography of papers dealing with robust combinatorial optimization problems, including facility location. See Birge and Louveaux (1997) for a textbook treatment of stochastic programming theory. A summary of the papers cited in this article can be found in spreadsheet form on the author's website, www.lehigh.edu/~lvs2/research.html.

2. Decision making under uncertainty

Rosenhead et al. (1972) divide decision-making environments into three categories: (i) certainty; (ii) risk; and (iii) uncertainty. In certainty situations, all parameters are deterministic and known, whereas risk and uncertainty situations both involve randomness. In risk situations, there are uncertain parameters whose values are governed by probability distributions that are known by the decision maker. In uncertainty situations, parameters are uncertain, and furthermore, no information about probabilities is known. Problems in risk situations are known as stochastic optimization problems; a common goal is to optimize the expected value of some objective function. Problems under uncertainty are known as robust optimization problems and often attept to optimize the worst-case performance of the system.

The goal of both stochastic and robust optimization is to find a solution that will perform well under any possible realization of the random parameters. The definition of "performing well" varies from application to application, and choosing an appropriate performance measure is part of the modeling process. The random parameters can be either continuous or described by discrete scenarios. If probability information is known, uncertainty is described using a (continuous or discrete) probability distribution on the parameters. If no probability information is known, continuous parameters are generally restricted to lie in some prespecified intervals.

The scenario approach has two main drawbacks. One is that identifying scenarios (let alone assigning probabilities to them) is a daunting and difficult task; indeed, it is the focus of a large body of stochastic programming literature. The second disadvantage is that one generally wants to identify a relatively small number of scenarios for computational reasons, but this limits the range of future states under which decisions are evaluated. However, the scenario approach generally results in more tractable models, and furthermore, it has the advantage of allowing parameters to be statistically dependent, which is often not practical when parameters are described by continuous probability distributions (although there are exceptions). Dependence is often necessary to model reality, since, for example, demands are often correlated across time periods or geographical regions and costs are often correlated among suppliers.

Most of the stochastic and robust facility location problems discussed in this paper are NP-hard since they often have classical facility location problems, which are themselves NP-hard, as special cases. Min-expected-cost extensions of "minisum" models such as the P-Median Problem (PMP) (Hakimi, 1964) and the Uncapacitated Fixed-charge Location Problem (UFLP) (Balinski, 1965) (for example, those discussed in Section 3.2.1) are relatively easy to solve since they can often be treated as larger instances of deterministic problems, for which good algorithms exist despite their NP-hard nature. For example, a problem with 100 nodes and ten scenarios can be solved in approximately the time required to solve a deterministic problem with 1000 nodes (a minute or two using today's state-of-the-art algorithms on a desk top computer). On the other hand, problems with a minimax structure such as those described in Section 4.1 are more difficult to solve to optimality; today's best algorithms are able to solve problems perhaps an order of magnitude smaller than corresponding stochastic problems in the same amount of time. This discrepancy parallels the difference in difficulty between deterministic minisum and minimax problems. For example, relatively large instances of the UFLP and PMP may be solved quickly, but the P-center problem, which has a minimax structure, is generally solved by embedding a set-covering problem (which is itself NP-hard) inside a binary search routine.

We next discuss stochastic location problems, then turn our attention to robust location problems in Section 4.

3. Stochastic location problems

In this section, we discuss stochastic models for facility location. Many of these models have as an objective the minimization of the expected cost or maximization of the expected profit of the system. Others take a probabilistic approach: for example, maximizing the probability that the solution is in some sense "good". Some models are solved using algorithms designed specifically for the problem, whereas others are solved using more general Stochastic Programming (SP) techniques. In any SP problem, one must decide which decision variables are first stage and which are second stage; that is, which variables must be set now and which may be set after the uncertainty has been resolved. In stochastic location modeling, locations are generally first-stage decisions whereas assignments of customers to facilities are second-stage, i.e., recourse, decisions. (If both decisions occur in the first stage, most problems can be reduced easily to deterministic problems in which uncertain parameters are replaced by their means.)

3.1. The Hakimi property