Evolutionary algorithms for the bi-objective adjacent only quadratic spanning tree
Sílvia Maria Diniz Monteiro Maia, Elizabeth Ferreira Gouvêa Goldbarg, Marco C. Goldbarg · International Journal of Innovative Computing and Applications · 2014
The adjacent only quadratic minimum spanning tree (AQMST) is a version of the minimum spanning tree problem in which, besides the traditional linear costs, is necessary to consider quadratic costs resulting from interactions between adjacent edges. AQMST is NP-hard and models real world problems on transportation and distribution networks. Although, in literature, the linear and the quadratic costs are added, in real applications, they may be conflicting. In this case, it may be interesting to consider costs separately and, thus, multi-objective optimisation provides a more realistic model. Evolutionary algorithms have shown to be effective techniques to deal with multi-objective problems and, in this paper, evolutionary algorithms are proposed to the bi-objective version of the AQMST. A computational experiment on 132 instances is reported and conclusions on the proposed techniques are drawn.