A branch-and-Benders-cut algorithm for a bi-objective stochastic facility location problem

Facility location problems play an important role in long-term public infrastructure planning. Prominent examples concern the location of fire departments, schools, post offices, or hospitals. They are not only relevant in public (or former public) infrastructure planning decisions in “regular” planning situations: they are also of concern in the context of emergency planning, e.g., relief goods distribution in the aftermath of a disaster or preparation for slow onset disasters such as droughts. In many of these contexts, accurate demand figures are not available; assumed demand values rely on estimates, while their actual realizations depend, e.g., on the severity of the slow onset disaster, the demographic population development in an urban district, etc. Since facility location decisions are usually long-term investments, the uncertainty involved in the demand figures should already be taken into account at the planning stage.

Another important issue is that facility location problems often involve several objectives. On the one hand, client-oriented objectives should be optimized. For example, in cases where it is not possible to satisfy the demand to 100 percent, the total covered demand should be as high as possible. On the other hand, cost considerations also play a role. This implies that decision makers face a trade-off between client-oriented and cost-oriented goals. Instead of combining these two usually conflicting measures into one objective function, it is advisable to elucidate their trade-off relationship. Such an approach provides valuable information to the involved stakeholders and allows for better informed decisions. Following this line of thought, in this paper, we model a bi-objective stochastic facility location problem that considers cost and coverage as two competing but concurrently analyzed objectives. Our concept of analysis is that of Pareto efficiency. Furthermore, we incorporate stochastic information on possible realizations of the considered demand figures in the form of scenarios sampled from probability distributions.

Motivated by recent advances in exact methods for multi-objective integer programming, we solve this problem by combining a recently developed bi-objective branch-and-bound algorithm (Parragh and Tricoire 2019) with the L-shaped method (Van Slyke and Wets 1969), which applies Benders decomposition (Benders 1962) to two-stage stochastic programming problems. We evaluate several enhancements, such as partial decomposition, and we compare the resulting approach to using a deterministic equivalent formulation within the same branch-and-bound framework.

This paper is organized as follows. In Sect. 2, we give a short overview of related work in the field of bi-objective (stochastic) facility location. In Sect. 3, we define the bi-objective stochastic facility location problem (BOSFLP) that is subject to investigation in this paper and we discuss L-shaped-based decomposition approaches of the proposed model. In Sect. 4, we explain how we integrate the proposed decomposition schemes into the bi-objective branch-and-bound framework. A computational study comparing the different approaches is reported in Sect. 5, and Sect. 6 concludes the paper and provides directions for future research.

Our problem is a stochastic extension of a bi-objective maximal covering location problem (MCLP). The MCLP has been introduced in Church and ReVelle (1974). It consists in finding locations for a set of p facilities in such a way that a maximum population can be served within a pre-defined service distance. In this classical formulation, the number of opened facilities is a measure of cost, while the total population that can be served is a measure of demand coverage. Thus, cost occurs in a constraint, whereas the objective represents covered demand. It is natural to extend this problem to a bi-objective covering location problem (CLP) where both cost (to be minimized) and covered demand (to be maximized) are objectives. Indeed, bi-objective CLPs of this kind have been studied in several papers, see, e.g. Bhaskaran and Turnquist (1990), Harewood (2002), Villegas et al. (2006), or Gutjahr and Dzubur (2016a); for further articles, we refer to Farahani et al. (2010).

Another strand of literature relevant in the present context addresses bi-objective covering tour problems (CTPs). One of the oldest CTP models, the maximal covering tour problem (MCTP) introduced by Current and Schilling (1994) is actually a bi-objective problem. A fixed number of nodes have to be selected out of the nodes of a given transportation network; then a tour visiting these selected nodes must be determined. The objectives are minimization of the total tour length (a measure of cost) and maximization of the total demand that is satisfied within some pre-specified distance from a visited node (a measure of demand coverage).

Other multi-objective CTP formulations can be found in the following papers: Jozefowiez et al. (2007) deal with a bi-objective CTP where the first objective is, as in the original problem, the minimization of the total tour length while the second objective function of the MCTP is replaced by minimizing the largest distance between a node of some given set and the nearest visited node. Doerner et al. (2007) develop a three-objective CTP model for mobile health care units in a developing country. Nolz et al. (2010) study a multi-objective CTP addressing the problem of delivery of drinking water to the affected population in a post-disaster situation.

Most importantly for the present work, Tricoire et al. (2012) generalize the bi-objective CTP to the stochastic case by assuming uncertainty on demand. The aim is to support the choice of distribution centers (DCs) for relief commodities and of delivery tours supplying the DCs from a central depot. Demand in population nodes is assumed as uncertain and modeled stochastically. DCs have fixed given capacities, as well as vehicles. The model considers two objective functions: The first objective is cost (more precisely, the sum of opening costs for DCs and of transportation costs), and the second is expected uncovered demand. Contrary to basic covering tour models supposing a fixed distance threshold, uncovered demand is defined by the more general model assumption that the percentage of individuals who are able and willing to go to the nearest DC can be represented by a nonincreasing function of the distance to this DC. Both the demand of those individuals who stay at home and the demand of those individuals who are not supplied in a DC because of DC capacity and/or vehicle capacity limits contribute to the total uncovered demand. Because of the uncertainty on the actual demand, total uncovered demand is a random variable, the expected value of which defines the second objective function to be minimized.

The problem investigated in the present paper generalizes the bi-objective CLP to a stochastic bi-objective problem by considering demand as uncertain and modelling it by a probability distribution, in an analogous way as in Tricoire et al. (2012). Alternatively, the investigated problem can also be derived from a CTP by omitting the routing decisions and generalizing the resulting bi-objective location problem again to the stochastic case. From the viewpoint of the latter consideration, the current model can be seen as related to the special case of the problem of Tricoire et al. (2012) obtained by neglecting routing costs. However, the current model builds on refined assumptions concerning the decision structure of the two-stage stochastic program which makes the second-stage optimization problem nontrivial, contrary to Tricoire et al. (2012) where the second-stage optimization problem can be solved by elementary calculations. Thus, the main novelty of the proposed bi-objective location problem compared to existing models is that it defines a covering location model containing a proper two-step stochastic program (which is not reducible to a single stage) within a bi-objective optimization frame based on the determination of Pareto-optimal sets.

Multi-objective stochastic optimization (MOSO) problems, though of eminent importance for diverse practical applications, are investigated in a more limited number of publications, compared to the vast amount of literature both on multi-objective optimization and on stochastic optimization; for surveys on MOSO, we refer the reader to Caballero et al. (2004), Abdelaziz (2012), and Gutjahr and Pichler (2016c). Of special relevance for our present work are multi-objective two-stage stochastic programming models where the “multicriteria” solution concept is that of the determination of Pareto-efficient solutions, and where the first-stage decision contains integer decision variables. Most papers in this area assume that one of the two objectives only depends on the first-stage decision, whereas the other objective depends on the decisions in both stages. This holds also for Tricoire et al. (2012). Let us give three other examples: Fonseca et al. (2010) present a two-stage stochastic bi-objective mixed integer program for reverse logistics, with strategic decisions on location and function of diverse collection and recovery centers in the first stage, and tactical decisions on the flow of disposal from clients to centers or between centers in the second stage. The first objective is expected total cost, which depends both on the first-stage and second-stage decision, whereas the second objective, the obnoxious effect on the environment, only depends on the first-stage decision. Stochasticity is associated with waste generation and with transportation costs. Cardona-Valdés et al. (2011) deal with decisions on the location of DCs and on transportation flows in a two-echelon production distribution network. Uncertainty holds with respect to the demand. The first objective represents expected costs, whereas the second objective expresses the sum of the maximum lead times from plants to customers. The authors model the random distribution by scenarios and solve the two-stage programming model by the L-shaped method, a technique that we will also use in our present work. Ghaderi and Burdett (2019), finally, present a two-stage stochastic model for strategically transporting and routing hazardous material. They consider two objective functions, where the first one represents fixed costs for transfer yard locations, and the second one captures exposure risk and transportation costs. Again, the first objective only depends on the strategic decision in the first stage. Basically, the authors follow a weighted-sum approach, but also Pareto-optimal solutions are reported and visualized.

Our problem has a structure similar to the models cited above: while the covered demand depends on the decisions in both stages, the cost objective is already determined by the first-stage decision. This allows the development of an efficient solution algorithm. Contrary to Tricoire et al. (2012), we will not apply an \(\varepsilon \)-constraint method for the determination of Pareto-efficient solutions, but use instead a more recent method developed in Parragh and Tricoire (2019).

There is a body of literature on two-stage humanitarian logistics with location decisions in the first stage and demand satisfaction in the second stage; they differ on how they handle and combine the objectives on cost and coverage. Balcik and Beamon (2008) consider the maximisation of coverage, under budget constraints. Rawls and Turnquist (2010) combine all considered costs (facility location and size, commodity acquisition, stocking decision, shipment, inventory) in a weighted sum, together with a penalty cost for unused material. Alem et al. (2016) consider four different models, which correspond to four different ways to handle uncertainty. In all four models the budget is a constraint. The first model is similar to that of Rawls and Turnquist (2010). Their second model aims to obtain the best worst-case deviation from optimality across all considered scenarios, while their third and fourth model consider a weighted sum of costs plus a weighted measure of risk. Tofighi et al. (2016) use an interactive method to elicit preference from a decision maker, considering a number of measures of cost. However the uncovered demand is aggregated with inventory cost in one objective. A tri-objective second-stage problem is tackled using the weighted augmented \(\varepsilon \)-constraint method. Interestingly, none of these methods formally investigate the tradeoff between cost and coverage in a multi-objective fashion: either they focus on coverage as the single objective, or they aggregate coverage as another form of cost and add a weight (or penalty) to it.

Finally, let us also mention that the humanitarian logistics literature, which tackles facility location problems under high uncertainty and multiple objectives, also has been relatively prolific with regards to multi-objective stochastic optimization models and corresponding solution techniques (cf. Gutjahr and Nolz (2016b)). Let us give two examples of papers using both Pareto optimization and two-stage stochastic programs. Khorsi et al. (2013) propose a bi-objective model with objectives “weighted unsatisfied demand” and “expected cost”. Discrete scenarios from a set of possible disaster situations are applied to represent uncertainty. The \(\varepsilon \)-constraint method is used to solve the model. Rath et al. (2016) deal with the uncertain accessibility of transportation links and develop a two-stage stochastic programming model where in the first stage decisions on the locations of distribution centers have to be made, and in the second stage (based on current information on road availability) the transportation flows have to be organized. Objective functions are expected total cost and expected covered demand. The structure of the two-stage stochastic program is different from that in the current paper insofar as both objectives depend on both first-stage and second-stage decision variables, which requires specific (and computationally less efficient) solution techniques. For general information on humanitarian logistics, the reader is referred to the standard textbook by Tomasini and Van Wassenhove (2009). Two-stage stochastic programing approaches to this field (in a single-objective context) are reviewed in Grass and Fischer (2016). A good recent example for the application of Benders decomposition to a stochastic model for humanitarian relief network design is Elçi and Noyan (2018).

For an overview on facility location in general, we refer the reader to Hamacher and Drezner (2002). Standard textbooks on multi-objective optimization and on stochastic programming are Ehrgott (2005) and Birge and Louveaux (2011), respectively.

In the bi-objective stochastic facility location problem (BOSFLP) considered in this article, the demand at each node \(i \in V\) is uncertain. By the random variable \(W_i\), we denote the demand at node i. At each node j, a facility may be built. A facility at node j has a capacity \(\gamma _j\) and operating costs \(c_j\). Furthermore, facilities that are farther than a certain maximum distance \(d_{max}\) from a demand point cannot cover it. In order to take this aspect into account, we consider the set \(A = \{(i,j)| i,j \in V, d_{ij} \le d_{max} \}\) of possible assignments (i, j), where \(d_{ij}\) denotes the distance of demand node i from a potential facility at node j. The two considered goals are to minimize the total costs for operating facilities and to maximize the expected covered demand. We transform the second objective into a minimization one by multiplying it by \(-1\). We assume further that the facility opening decision has to be taken ”here-and-now” while the coverage of demand points by facilities can be decided once the demand is realized. These decisions are ”wait-and-see” decisions. The resulting two-stage decision problem can be approached using two-stage stochastic programming. The optimal solution value of the second-stage problem under first-stage decisions z and random variable \(\xi \) is denoted \(Q(z, \xi )\). A table giving an overview of the employed notation throughout the paper is given in Appendix A. We note that the demand at a node can be covered by a facility if that facility is open in the first stage, and as much as the capacity at that facility allows it. Partial coverage and split coverage are both possible, so for instance 60% of the demand of a population node can be covered by an open facility while 30% of that same demand is covered by another facility and 10% remain uncovered.

Using the following decision variables,we formulate the BOSFLP as a two-stage stochastic program:Second stage:subject to:Objective function (1) minimizes the total facility opening costs. Objective function (2) maximizes the expected covered demand. In order to obtain two minimization objectives, objective (2) has been multiplied by \((-1)\). The first stage model only comprises one set of constraints which require that all \(z_j\) variables may only take values 0 or 1. The second stage model consists of the objective function given in (4), representing the negative value of the total covered demand, and a number of constraints which determine the maximum possible coverage given a first stage solution. Constraints (5) link coverage variables \(u_j\) with assignment variables \(y_{ij}\): the covered demand at node j cannot be larger than the actual demand assigned to this node. Constraints (6) make sure that the capacity of facility j is not exceeded. Constraints (7) guarantee that a demand node can only be assigned to a facility if the respective facility is open. Finally, constraints (8) ensure that any part of the demand at i is only covered at most once. The variables \(z_j\) are first-stage decision variables whereas the variables \(y_{ij}\) are second-stage decision variables, i.e., the latter variables depend on the realizations of the demand values; that is, \(y_{ij}=y_{ij}(\xi )\). Similarly, \(u_j=u_j(\xi )\) and \(W_i=W_i(\xi )\).

It should be noted that in our model, the decision maker is assumed as risk-neutral with respect to the covered demand, which implies that she only considers its expected value as a quantification of the second objective function.

Since the true demand distribution is too complex to be handled computationally within the optimization model, we resort to a scenario-based approach. The purpose of such an approach is to approximate the considered probability distribution by a discrete distribution on a (not too large) set of specific scenarios. As described in detail in Shapiro and Philpott (2007), a possible way to identify scenarios is sample average approximation (SAA); this method has also been applied in Ghaderi and Burdett (2019). SAA consists in generating a sample N of independent random realizations from the given distribution by Monte-Carlo simulation. Each realization can then be conceived as a scenario with assigned probability 1/|N|, and the expected value turns into an average over scenarios. Using an additional index \(\nu \) to denote a given scenario for the variables of the second stage problem, we obtain the following expanded model:subject to:Our aim is the determination of the set of Pareto-optimal solutions of the problem above, i.e., of all solutions that cannot be improved in one of the two objectives without a deterioration in the other objective.

Instead of considering a set of scenarios with equal probabilities \(p_\nu = 1/|N|\), the model above can also be generalized to arbitrary probabilities \(p_\nu > 0\) with \(\sum _{\nu \in N} p_\nu = 1\) in a straightforward way.

Since we will solve the BOSFLP by means of a bi-objective branch-and-bound algorithm, we have to solve the linear relaxation of model (11)–(19) to compute lower bounds (see Sect. 4). For efficiently solving the linear relaxation, especially with a large number of scenarios, the well known L-shaped method, as introduced by Van Slyke and Wets (1969), is used. In the L-shaped method, the problem is decomposed into a so-called master problem (incorporating the first stage variables and constraints) and one subproblem per scenario. The information from the subproblems is included into the master problem by means of an additional variable reflecting the value of the second objective and by cutting planes, which are derived from iteratively solving the master problem and each of the scenario subproblems. In the case where the optimal solution to the master problem does not result in a feasible solution to the subproblem(s), a feasibility cut has to be added to the master. In the case where the expected value of the second objective is underestimated, an optimality cut is added to the master problem. If no additional cut has to be added, the procedure terminates and the optimal solution to the linear relaxation has been found. In the case of complete recourse, as is the case for our problem, only optimality cuts have to be added: a solution to the first stage problem will always allow a feasible solution to the second stage problem. (This holds for our problem, since no matter which facility opening decision is taken, setting all second stage variables, \(y_{ij}^{\nu }\) and \(u_j^{\nu }\), to zero produces a feasible solution, see constraints (14) and (15).) For an example of the L-shaped method, we refer to Birge and Louveaux (2011).

In the following, we shall specify:Using variable \(\theta \) to represent the second stage objective, we obtain the following master linear program (LP):subject to:where \(- \sum \limits _{i \in V} \max \limits _{\nu \in N} \{ W^{\nu }_i \}\) provides a valid bound on \(\theta \), since \(Q(z,\xi ) = \min \limits _{u} \left( - \sum \limits _{j \in V} u_j\right) \ge - \sum \limits _{i \in V} \max \limits _{\nu \in N} \{ W^{\nu }_i \}\).

How the bi-objective nature of the problem is addressed is discussed in detail in Sect. 4. It requires the computation of lower bound sets which rely on iteratively solving single objective weighted sum problems. In that context and for a given set of weights, to determine if the obtained solution to the master weighted-sum LP is optimal, we check if optimality cuts have to be added. We denote by \(z_j^l\) and \(\theta ^l\) the variable values obtained from solving the master LP in iteration l, and we solve for each \(\nu \in N\) the following model:subject to:Let \(\mathcal {Q}(z) = {\mathbf {E}}_{\xi }Q(z,\xi )\). If \(\mathcal {Q}(z^l) \le \theta ^l\), we terminate: optimality has been reached. Otherwise, we generate an optimality cut. Optimality cuts rely on dual information. To write the dual of the above model (24)–(30), we denote by \(\lambda _j\) the dual variables of constraints (25), by \(\pi _j\) the dual variables of constraints (26), by \(\sigma _{ij}\) the dual variables of constraints (27), and by \(\delta _i\) the dual variables of constraints (28):subject to:We denote by \(\pi ^{\nu ,l}_j = \pi _j(\xi ^{\nu },z^l)\), \(\sigma ^{\nu ,l}_{ij} = \sigma _{ij}(\xi ^{\nu },z^l)\), and \(\delta ^{\nu ,l}_i = \delta _i(\xi ^{\nu },z^l)\) the dual variable values for a given scenario \(\nu \), and by \(Q(z^l, \xi ^{\nu }) = - \sum _{j \in V} \pi _j^{\nu ,l}\gamma _j z_j^l - \sum _{(i,j) \in A} \sigma _{ij}^{\nu ,l} W_{i}^{\nu } z_j^l - \sum _{i \in V} W_{i}^{\nu } \delta _i^{\nu ,l}\) the objective function value. Then, the optimality cut for scenario \(\nu \) is of the following form (Van Slyke and Wets 1969):Rearranging the terms, we obtainFinally, combining over all scenarios, we obtain the optimality cut for the expected second stage objective function (with \(\bar{\pi }_j^{l} = 1/|N| \sum _{\nu } \pi _j^{\nu ,l}\) and \(\bar{\sigma }_{ij}^{l} =1/|N| \sum _{\nu } \sigma _{ij}^{\nu ,l} W_{i}^{\nu }\)):Alternatively, instead of adding one optimality cut per iteration, we can also add one cut per scenario. In order to do so, a separate variable \(\theta ^{\nu }\) for each scenario \(\nu \) has to be used, resulting in the following master LP:subject to:Then, we check each subproblem and add a cut of the form (39) in the case where \(\theta ^{\nu ,l} < Q(z^l,\xi ^{\nu })\). In the case where all scenarios are checked and no additional cut has to be added, optimality has been reached.

In order to solve the BOSFLP, we integrate L-shaped based cut generation into the recently introduced bi-objective branch-and-bound framework of Parragh and Tricoire (2019). In what follows, we first describe the key ingredients of the branch-and-bound framework and thereafter how we combine it with the L-shaped method.

The previously described algorithms have been implemented using Python and Gurobi 8. The algorithms are run on a cluster with Xeon E5-2650v2 CPUs at 2.6 GHz. Each job is allocated 8 GB of memory and two hours of CPU effort. Multi-threading is disabled in Gurobi.

In what follows, we first give an overview of the considered benchmark instances. Thereafter, we compare the different methods and we discuss the obtained results.

We have defined a bi-objective facility location problem (BOSFLP), which considers both a deterministic objective (cost minimization) and a stochastic one (population coverage maximization), where the value of the second objective is evaluated by sample average approximation. The aim of the BOSFLP is to determine the set of efficient solutions using the Pareto approach, but aiming for good approximations with regard to the stochastic objective means considering large samples of random realizations, which makes using the expanded model directly impractical. We decomposed the original problem using Benders decomposition (L-shaped method) in a bi-objective branch-and-bound (BIOBAB) algorithm. This is, to the best of our knowledge, the first time that Benders decomposition has been integrated into a bi-objective branch-and-bound algorithm.

We also implemented several known improvements to the L-shaped method, and adapted them to the bi-objective context. Among all settings, we observed that generating Benders cuts only at the root node and at integer solutions speeds up the search considerably. The developed strategy for integrating cutting plane generation into the lower bound set algorithm generalizes to any type of cut and thus paves the way for the development of general purpose bi-objective branch-and-cut algorithms relying on bound sets. We also observed that valid inequalities on bounds for sample-dependent values of the stochastic objective bring a significant improvement. In both cases, experimental observations were significant enough to justify making these recommendations permanent, at least in the context of the BOSFLP.

Research perspectives include the incorporation of additional enhancements into the L-shaped method. Crainic et al. (2016) propose to use more sophisticated partial decomposition strategies, such as the clustering-mean strategy in which similar scenarios are clustered and a good representative from each cluster is incorporated into the master program, or the convex hull strategy, where scenarios that include other scenarios in their convex hull are integrated in the master program. Magnanti and Wong (1981) suggest improvements based on the notion of Pareto optimal cuts, a concept which has also been successfully employed by Adulyasak et al. (2015). The literature on the single-objective L-shaped method is abundant, and there are still lessons to be learnt in applying these techniques to the bi-objective context. Moreover, as illustrated by Tricoire et al. (2012), in the bi-objective context there is potential for improvements that rely on the interaction of the two objectives; one of our future goals is to develop bi-objective specific improvements for Benders decomposition techniques.

An important issue of future research is an extension of the chosen stochastic programming approach assuming a known probability distribution of the uncertain parameters to the consideration of ambiguity, i.e., uncertainty on the stochastic model itself (cf. Pflug and Wozabal 2007). In the application context of the present paper, this will be of particular interest for a treatment of man-made (or partially man-made) disasters.