We study the problem of locating production facilities and selecting production technology for hydrogen in Norway. Hydrogen demand is expected to increase over the next years but is also the main source of uncertainty. Further, hydrogen production costs highly depend on electricity prices, which are also uncertain.
We present a stochastic multi-stage multi-horizon formulation, which enables the modelling of strategic as well as operational uncertainty. The strategic uncertainty is related to increasing but uncertain future demand, while the operational uncertainty is related to uncertain future electricity costs directly affecting the operational costs. We consider two production technologies, which differ in production flexibility and costs, and allow for their combination at one location. Therefore, capacity expansion is modelled as the opening of a new facility. The objective is to minimize the expected sum of investment, production and distribution costs while satisfying customer demand.
We use Lagrangian relaxation to solve our problem. The lower bound is calculated by solving the linear relaxation of the Lagrangian subproblem. We implement a heuristic based on a restricted MIP approach to obtain a feasible solution. The results show that our solution method can find high-quality solutions for large problem instances with up to 150 operational scenarios.

Around the world, various decarbonization strategies are being evaluated to support countries meeting their net-zero emissions objectives. One of these decarbonization strategies is carbon capture and sequestration (CCS). In CCS, CO2 is captured at emitter sites (e.g. industrial plants) and transported to geological sequestration sites (e.g. saline aquifers, depleted oil fields), where it is injected underground for long-term storage (10,000+ years). Recent studies indicate that without CCS, countries may not be able to meet their net-zero carbon emissions objectives.

The deployment of CCS involves billions of dollars of investment and requires planning ahead for decades. For this reason, in this presentation, we focus on the multiperiod strategic planning of a pipeline-based CCS value chain. This problem combines characteristics of two classical problems in Operations Research: facility location and network design. Facility location decisions are related to the activation and operation of CO2 capture units at emitter sites, and the opening and operation of geological reservoirs. Network design characteristics consist of the activation and operation of the pipeline network.

To account for multiple potential sources of uncertainty, this problem may have to be solved thousands of times. Therefore, reaching high-quality solutions in a few minutes is important. Computational experiments show that commercial solvers struggle to attain these requirements. Adding further problem attributes such as multiple CO2 transportation modes may exacerbate this issue. To address this computational challenge, a novel slope scaling heuristic was previously introduced by Homsi, Ayotte-Sauvé, and Jena. This heuristic is based on existing work on single-period CCS problems and network design problems. It approximates the cost of design variables, has long-term memory search strategies, generates upper bounds with dynamic programming, and has a final improving phase where a restricted model is solved iteratively.

In this presentation, we provide updated results for the slope scaling heuristic along with additional performance insights. These new results show that the heuristic generates better solutions than CPLEX for most (58\%) experiments (average relative improvement of 10\%), at a fraction (10\%) of the CPU time. For the same fraction of CPU time, results also show the satisfactory performance of the heuristic when it underperforms CPLEX: the vast majority of SS solutions (95\%) have a relative cost that is at most 1\% larger than CPLEX.

Dynamic Facility Location and Network Design are a popular class of combinatorial optimization problems that provide the infrastructure necessary to satisfy customer demand. They have been applied to a large variety of planning contexts, where customer demand may have different interpretations, such as consumer goods, manufacturing components, transportation services, or medical relief items. Existing literature commonly assumes that customer demand quantities are defined independently for each time-period. In many planning contexts, however, unmet demand carries over to future time periods. Demand that is unmet for some time periods may therefore affect decisions of subsequent time periods.

In this talk, we discuss the implications of cumulative customer demand in two representative planning contexts for multi-period network design and facility location: humanitarian supply chains, where unmet demand for relief aid may result in a spread of disease, and therefore increases future demand; and temporary facility location, such as pop-up stores, where customer demand for necessary items gradually builds up until it is satisfied by a nearby facility. We discuss two principal types of cumulative demand propagation and their respective modeling in mathematical programming formulations. We show how a failure of modeling such behavior may result in severe economic underperformance, how the corresponding models can be modeled and solved efficiently, and how different problem characteristics impact the computational complexity.