Abstract
Capacity planning involves high-stakes decisions under uncertainty, often requiring a balance between immediate investment and future flexibility. This paper examines the value of risk-averse multistage stochastic programming (MSP) compared to simpler two-stage models. We provide analytical bounds for the value of multistage solutions ($VMS_R$) and introduce an approximation algorithm that is both computationally efficient and asymptotically optimal. Our findings reveal that while multistage models offer significant flexibility, their relative advantage can diminish with extreme risk-aversion. The proposed framework is validated through synthetic tests and a case study on electric vehicle charging infrastructure.
Introduction
In infrastructure and supply chain management, capacity planning—deciding when and where to build facilities—is a critical challenge. Planners must choose between "here-and-now" decisions based on forecasts (Two-Stage) or dynamic, "wait-and-see" expansions as demand evolves (Multistage). While multistage stochastic programming captures this flexibility, it is computationally intensive (NP-hard) and often focuses on risk-neutral objectives. This research addresses the gap by quantifying the value of multistage flexibility under risk-averse preferences, providing tools to determine when the added complexity of MSP is justified.
Methodology
The authors model the capacity planning problem using scenario trees to represent uncertain demand trajectories over time. To incorporate risk-aversion, they utilize Expected Conditional Risk Measures (ECRMs) based on Conditional Value-at-Risk (CVaR), ensuring time-consistency in risk preferences.
The methodological framework includes:
- Analytical Bounds: Derivation of tight lower and upper bounds for $VMS_R$, allowing planners to estimate the benefits of MSP without solving the full problem.
- Approximation Algorithm (AA): An iterative decomposition algorithm that exploits problem substructure. It is proven to be asymptotically optimal as the market expands.
- Decision Support: A flowchart utilizing the derived bounds to guide practitioners in choosing between two-stage and multistage models.
The study evaluates these methods using synthetic grid networks (up to 20 facilities) and a real-world case study involving the expansion of Electric Vehicle (EV) charging stations across 49 US cities, considering realistic maintenance costs and growth patterns.
Key Insights and Results
The research yields several critical insights into the dynamics of capacity planning:
- Risk vs. Flexibility: Interestingly, increased risk-aversion can decrease the gap between two-stage and multistage models. Extreme risk-aversion leads to more conservative behavior in MSP, mirroring the "here-and-now" caution of two-stage models to avoid worst-case outcomes.
- The Power of Dependence: The value of multistage planning is highest when demand is stagewise-dependent (e.g., current high demand predicts future high demand).
- Computational Performance: The proposed Approximation Algorithm (AA) outperformed standard solvers like Gurobi, finding high-quality solutions in seconds where solvers often timed out. In the EV case study, the AA achieved an approximation ratio of 1.00004, effectively matching the optimal solution.
- Maintenance Costs: Period-wise maintenance costs are identified as a primary driver of the multistage advantage, as they penalize premature over-building.
Conclusion
This work provides a rigorous toolkit for evaluating the trade-offs between risk and flexibility in capacity planning. By providing tight analytical bounds and an efficient approximation algorithm, the authors make complex multistage models more accessible for practical application. Future research may explore distributional robustness to account for forecast uncertainty and hybrid "adaptive two-stage" models to further balance simplicity with flexibility.
Full Paper Citation: Yu, X., & Shen, S. (2024). On the Value of Risk-Averse Multistage Stochastic Programming in Capacity Planning. Forthcoming in INFORMS Journal on Computing. Source Code Available on GitHub
Summary updated