Evolutionary algorithms for the bi-objective adjacent only quadratic spanning tree. (23rd December 2014) - Maia, Sílvia Maria Diniz Monteiro
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.