A hybrid ensemble approach for the Steiner tree problem in large graphs: A geographical application.

Abstract: Hybrid approaches are often recommended for dealing in an efficient manner with complex problems that require considerable computational time. In this study, we follow a similar approach consisting of combining spectral clustering and ant colony optimization in a two-stage algorithm for the purpose of efficiently solving the Steiner tree problem in large graphs. The idea of the two-stage approach, called ESC–IAC, is to apply a divide-and-conquer strategy which consists of breaking down the problem into sub-problems to find local solutions before combining them. In the first stage, graph segments (clusters) are generated using an ensemble spectral clustering method for enhancing the quality; whereas in the second step, parallel independent ant colonies are implemented to find local and global minima of the Steiner tree. To illustrate the efficiency and accuracy, ESC–IAC is applied in the context of a geographical application relying on real-world as well as artificial benchmarks. [Copyright &y& Elsevier]