Using Lagrangian relaxation to locate hydrogen production facilities under uncertain demand: a case study from Norway

Hydrogen is considered a solution to decarbonize the transportation sector, an important step to meet the requirements of the Paris agreement. Even though hydrogen demand is expected to increase over the next years, the exact demand level over time remains a main source of uncertainty. We study the problem of where and when to locate hydrogen production plants to satisfy uncertain future customer demand. We formulate our problem as a two-stage stochastic multi-period facility location and capacity expansion problem. The first-stage decisions are related to the location and initial capacity of the production plants and have to be taken before customer demand is known. They involve selecting a modular capacity with a piecewise linear, convex short-term cost function for the chosen capacity level. In the second stage, decisions regarding capacity expansion and demand allocation are taken. Given the complexity of the formulation, we solve the problem using a Lagrangian decomposition heuristic. Our method is capable of finding solutions of sufficiently high quality within a few hours, even for instances too large for commercial solvers. We apply our model to a case from Norway and design the corresponding hydrogen infrastructure for the transportation sector.