An efficient hybrid heuristic for the transmission expansion planning under uncertainty

We address the stochastic transmission expansion planning (STEP) problem under uncertainty in renewable generation capacity and demand. STEP’s objective is to minimize total transmission investment and generation costs. To tackle the computational challenges posed by large-scale systems, we propose a heuristic strategy that combines the progressive hedging (PH) algorithm for scenario-wise decomposition with an integrated approach for solving the resulting subproblems. The latter combines a destroy-and-repair operator, a beam search procedure, and a mixed-integer programming solver. The proposed framework is evaluated on large-scale systems from the literature with up to 10,000 nodes, adapted to stochastic scenarios using parameters from the California test system (CATS). Compared with a non-trivial baseline algorithm that includes the same integrated approach, the proposed PH-based method consistently improved solution quality for the six systems considered (including CATS), achieving an average cost improvement of 5.28% within a 2-hour time limit.