Efficient Multi-start with Path Relinking Search Strategy for Transmission System Expansion Planning

Transmission expansion planning is a complex problem that deals with the selection of new transmission lines that guarantee meeting future demand/generation and technical limits with the minimal investment cost. The transmission expansion planning problem has been solved through approaches and techniques aimed at reducing the computational effort required for its solution. Nevertheless, finding the optimal solution or even good-quality solutions for large-scale transmission systems is still challenging. In that context, an efficient multi-start with path relinking search strategy for the transmission expansion planning problem is proposed. The proposed strategy has two phases: constructive phase and local search. In the former, the multi-start applies a diversification process to guide the search along different regions to obtain good-quality solutions. Then, the local search phase executes an intensive search in the neighborhood of the best feasible solutions found in the constructive phase. The intensification process is performed in two steps: application of the Villasana-Garver-Salon algorithm in the best solutions after consecutive removal of transmission lines and path relinking using elite solution pairs. Tests performed using data from four systems show the efficiency of the proposed search strategy. Thus, the optimal solutions were obtained with a very low computational effort.