Title: Evolutionary algorithms for the bi-objective adjacent only quadratic spanning tree

Authors: Sílvia Maria Diniz Monteiro Maia; Elizabeth Ferreira Gouvêa Goldbarg; Marco César Goldbarg

Addresses: Department of Informatics and Applied Mathematics, Federal University of Rio Grande do Norte, Natal, 59078-970, Brazil ' Department of Informatics and Applied Mathematics, Federal University of Rio Grande do Norte, Natal, 59078-970, Brazil ' Department of Informatics and Applied Mathematics, Federal University of Rio Grande do Norte, Natal, 59078-970, Brazil

Abstract: 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.

Keywords: bi-objective AQMST; adjacent only quadratic MST; minimum spanning tree; evolutionary algorithms; multi-objective optimisation; quadratic costs; adjacent edges; modelling.

DOI: 10.1504/IJICA.2014.066493

International Journal of Innovative Computing and Applications, 2014 Vol.6 No.2, pp.63 - 72

Received: 01 Aug 2014
Accepted: 01 Aug 2014
Published online: 31 Dec 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article