A MILP-based heuristic algorithm for transmission expansion planning problems

Resumen

In the last years, a lot of effort was placed into approximated or relaxed models and heuristic and metaheuristic algorithms to solve complex problems, mainly with non-linear and non-convex natures, in a reasonable time. On one hand, approximated/relaxed mathematical models often provide convergence guarantees and allow the problem to be solved to global optimality. On the other hand, there is no guarantee that the optimal solution of the modified problem is even feasible in the original one. In contrast with that, the metaheuristic algorithms lack mathematical proof for optimality, but as the obtained solutions can be tested against the original problem, the feasibility can be ensured. In this sense, this work brings a new method combining exact solutions from a Mixed-Integer-Linear-Problem (MILP) Transmission Expansion Planning (TEP) model and stochastic solutions from metaheuristic algorithms to solve the non-linear and non-convex TEP problem. We identify the issues that came up with the linear approximations and metaheuristics procedures and we introduce a MILP-Based Heuristic (MBH) algorithm to overcome these issues. We demonstrate our method on a single-stage TEP with the RTS 24 nodes and on a multi-stage TEP with the IEEE 118 nodes test system. The AC TEP solution was obtained using Evolutionary Computation, while the DC TEP solution was obtained using a commercial solver. From the simulations results, the novel MBH method was able to reduce in 42% and in 85% the investment cost from an evolutionary computation solution for the single-stage and multi-stage TEP, respectively.

Publicación
Electric Power Systems Research
J. Manuel Colmenar
J. Manuel Colmenar
Artificial Intelligence Professor

Mis intereses de investigación se centran en las metaheurísticas aplicadas a problemas de optimización. He trabajado en diferentes problemas de optimización combinatoria aplicando algoritmos trajectoriales como GRASP o VNS. Además, estoy muy interesado en las aplicaciones de la Evolución Gramatical, específicamente en el dominio de los modelos y la predicción, como alternativa a los enfoques de aprendizaje automático.