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

•We consider the optimal PMU placement problem and give a hybrid two-phase algorithm.•We perform the algorithm on the IEEE power systems and demonstrate its effectiveness.•We also consider a theoretical model and provide lower bounds on the number of PMUs.•The algorithm can achieve the optimum in the theoretical model of the power systems.

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.