A slope scaling heuristic for the multi-period strategic planning of carbon capture and storage

Around the world, efforts are currently underway to implement various decarbonization strategies to meet net-zero emissions objectives. This includes carbon capture and storage (CCS), which involves capturing CO 2 at emitter sites, and transporting it to geological reservoirs, where it is to be injected underground for long-term storage. In this work, we focus on the multi-period strategic planning of a CCS value chain involving pipeline CO 2 transportation. From an Operations Research standpoint, this problem exhibits the characteristics of combined facility location and network design. To account for multiple scenarios of input parameters ( e.g. market and geological variability), this problem has to be solved hundreds or thousands of times. Thus, reaching high-quality solutions quickly is crucial. As commercial solvers struggle to provide high-quality solutions under these time constraints, we propose a slope scaling heuristic based on previous work on single-period CCS planning and network design. This new heuristic approximates the cost of design variables, generates upper bounds via dynamic programming, uses a long-term memory search strategy, and includes a final improvement phase where a restricted model is solved. Computational experiments show that the proposed heuristic generates better solutions than CPLEX for most instances considered, at a fraction of the computational time.