Abstract
We consider a multi-period capacitated facility location problem over a finite time horizon under uncertain demand in each period. We formulate a multistage stochastic integer program using a scenario tree representation of the uncertainty, and compare it with a two-stage approach that decides which facilities to open for all periods up front. In the multistage model, in each stage, after realizing the demand, a decision maker optimizes facility locations and product flows from open facilities to demand sites, with the goal of minimizing certain measures of the future random cost associated with locating facilities and satisfying demand. Using expected conditional risk measures (ECRMs), we provide tight lower bounds for the gaps between optimal objective values of risk-averse multistage models and their two-stage counterparts. Moreover, two approximation algorithms are proposed to efficiently solve risk-averse two-stage and multistage stochastic programs, whose approximation ratios are independent of the underlying stochastic process, structure of the scenario tree, number of stages, and risk-preference-related parameters. We conduct numerical studies using both randomly generated and real-world network instances to demonstrate the tightness of the analytical bounds and computational efficacy of the proposed approximation algorithms. We also provide managerial insights for guiding locating facilities with risk aversion in practice, based on various types of uncertainty cases and parameter settings.
Introduction
Strategic facility location—deciding where to build warehouses, hospitals, or car-sharing stations—is a critical challenge when both future demand and available budgets are uncertain. This paper quantifies the financial and risk-reduction benefits of flexibility in long-term infrastructure planning by comparing "plan-it-all-now" (two-stage) versus "adapt-as-you-go" (multistage) models. The "Value of Multistage Stochastic Programming" (VMS) represents the cost savings gained by waiting for information to be revealed before making further commitments.
Methodology: Modeling Adaptivity and Risk
The researchers model uncertainty using scenario trees, where each node represents a possible state of the world at a specific time. This allows for a time-consistent approach to risk-averse decision-making through Expected Conditional Risk Measures (ECRMs), such as Conditional Value-at-Risk.
To address the computational complexity of multistage integer programs, the authors propose approximation algorithms that solve linear relaxations and substructure problems. These algorithms are designed to be efficient even as the scale of the problem increases. Furthermore, the paper incorporates prioritization, where a decision-maker ranks potential sites to maintain consistency across different budget realizations.
Key Insights and Results
- Adaptivity in Correlated Markets: The VMS is significantly higher when demand is "stagewise dependent," meaning current demand levels strongly signal future trends.
- The "Expanding Market" Advantage: The proposed approximation algorithms are asymptotically optimal as the market grows, making them highly effective for large-scale urban planning or business expansion.
- Computational Efficiency: The introduction of "prioritization cuts"—mathematical constraints that prune the search space—reduced solve times for complex models from over an hour to just a few minutes.
- Risk Profile: Out-of-sample testing demonstrated that multistage solutions consistently produced lower 95th-percentile costs than two-stage solutions, proving their superiority in hedging against "black swan" demand spikes.
Conclusion
This framework provides a robust tool for multistage, risk-averse facility location planning. By deriving tight analytical bounds and efficient algorithms, the authors offer a practical path for managers to balance the need for long-term consistency with the financial benefits of adaptivity. Future work may explore distributionally robust optimization to handle cases where the underlying probability distributions of demand are themselves uncertain.
Summary updated