Article ID Journal Published Year Pages File Type
494773 Applied Soft Computing 2016 14 Pages PDF
Abstract

•Ant colony optimization algorithm for the problem of partitioning graphs with supply and demand.•Very effective method manages to find optimal solutions in more that 50% of the test instances.•Average relative error of less than 0.5% when compared to known optimal solutions.•Method analyzed on general graphs, Halin graphs, series–parallel graphs and trees.

In this paper we focus on finding high quality solutions for the problem of maximum partitioning of graphs with supply and demand (MPGSD). There is a growing interest for the MPGSD due to its close connection to problems appearing in the field of electrical distribution systems, especially for the optimization of self-adequacy of interconnected microgrids. We propose an ant colony optimization algorithm for the problem. With the goal of further improving the algorithm we combine it with a previously developed correction procedure. In our computational experiments we evaluate the performance of the proposed algorithm on trees, 3-connected graphs, series–parallel graphs and general graphs. The tests show that the method manages to find optimal solutions for more than 50% of the problem instances, and has an average relative error of less than 0.5% when compared to known optimal solutions.

Graphical abstractFigure optionsDownload full-size imageDownload as PowerPoint slide

Related Topics
Physical Sciences and Engineering Computer Science Computer Science Applications
Authors
, , ,