Hibridização de algoritmos exatos e meta-heurísticas para o problema da árvore geradora quadrática em adjacência de arestas biobjetivo

Abstract

The Minimum Spanning Tree Problem (MST) consists of, given a finite non-directed graph G = (V, E) with |V| = n and |E| = m, weighted by edges, find an acyclic and connected spanning subgraph so that the sum of the weights of the edges is minimal. This is a classic problem of combinatorial optimization that can be solved optimally in polynomial time. The Quadratic Minimum Spanning Tree Problem (QMST) is a generalization of MST in which quadratic costs associated with the interaction of each pair of edges are present. The linear and quadratic costs are summed to make up the total cost of the resulting spanning tree. Since only adjacent edge interactions are considered, the problem is called the Adjacency-Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-Hard problems that attempt to model real problems involving the design of transport and distribution networks. For example, in the transportation of petroleum and its derivatives. Transportation takes place through pipes, which have connection interfaces between them. Thus, the cost of transporting oil and its derivatives from one pipeline to another may depend on the nature of their interfaces. Although in the mono-objective version, linear and quadratic costs are summed up, but in real applications such costs can be conflicting, which makes it more interesting to consider them independently. In this sense, multiobjective optimization seems to provide a more realistic model for the problems of QMST and AQMST, giving rise to the Biobjective Adjacency-Only Quadratic Spanning Tree Problem (bi-AQST). In the formulation by the biobjective perspective it is considered the fact that linear and quadratic costs can assume conflicting situations. In general, bi-AQST can be solved from exact strategies and (meta) heuristics, but both approaches have drawbacks. The exact one can take an inadmissible computational time, whereas the heuristics will not always find the optimal solution of the problem. Thus, a third approach is to combine these methods in order to minimize the disadvantages of each approach, this being the study carried out in this work.