Hybrid search for the optimal PMU placement problem on a power grid

With increasing global concerns regarding energy management, the concept of the smart grid has become a particularly important interdisciplinary research topic. In order to continually monitor a power utility system and efficiently observe all of the states of electric nodes and branches on a smart grid, placing PMUs (phasor measurement units) at selected nodes on the grid can monitor the operation conditions of the entire power grid. This study investigates methods for minimizing the high installation costs of PMUs, in order to monitor the entire system using a set of PMUs according to the power observation rules. Notably, this problem of monitoring a power grid can be transformed into the OPP (optimal PMU placement) problem. The objective is to simultaneously minimize the number of PMUs and ensure the complete observability of the whole power grid. This combinatorial optimization problem has been shown to be NP-complete. In this paper, we propose a hybrid two-phase algorithm for this problem. The first phase of the algorithm quickly identifies a set of candidate locations of PMUs based on a graph-theoretic decomposition approach for the power domination problem in tree-type graphs. Then, we use a local search heuristic method to derive the minimum number of PMUs in the second phase. In addition to the practical model, this study also considers the ideal model, in which all load nodes are assumed to be zero injection. The numerical studies on various IEEE power test systems demonstrate the superior performance of the proposed algorithm in both the models in regard to computational time and solution quality. In particular, in the ideal model, the number of PMUs required for the test systems can be significantly reduced. We also provide theoretical lower bounds on the number of installed PMUs in the ideal model and show that the derived solution can achieve the bound of the test systems.