Simulated Annealing algorithm using the Node-depth Phylogenetic structure for the Degree-Constrained Minimum Spanning Tree problem

The degree-constrained minimum spanning tree problem (DCMST) is an NP-hard optimization problem defined on connected weighted graphs. It consists of computing a minimum-cost spanning tree of the graph whose nodes have degrees smaller or equal to a predefined constant D. This paper proposes a new heuristic algorithm for solving DCMST, namely the Node-depth Phylogenetic-based Simulated Annealing heuristic (NPE-SA). The proposed algorithm implements the classic Simulated Annealing (SA) metaheuristic using the Node-depth Phylogenetic-based Encoding (NPE), a powerful data structure for indirectly representing spanning trees. Computational experiments performed on two sets of classic instances from the literature demonstrate that NPE-SA outperforms the best metaheuristic from the literature when solving the proposed DCMST instances. Furthermore, it outperforms the Node-depth Phylogenetic-based CLONALG heuristic, another heuristic that implements the NPE data structure.