O problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree Problem (QMST) is a version of the Minimum Spanning Tree Problem in which, besides the traditional linear costs, there is a quadratic structure of costs. This quadratic structure models interaction effects between pairs of edges. Linear and quadratic costs are added up to constitute the total cost of the spanning tree, which must be minimized. When these interactions are restricted to adjacent edges, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). AQMST and QMST are NP-hard problems that model several problems of transport and distribution networks design. In general, AQMST arises as a more suitable model for real problems. Although, in literature, linear and quadratic costs are added, in real applications, they may be conflicting. In this case, it may be interesting to consider these costs separately. In this sense, Multiobjective Optimization provides a more realistic model for QMST and AQMST. A review of the state-of-the-art, so far, was not able to find papers regarding these problems under a biobjective point of view. Thus, the objective of this Thesis is the development of exact and heuristic algorithms for the Biobjective Adjacent Only Quadratic Spanning Tree Problem (bi-AQST). In order to do so, as theoretical foundation, other NP-hard problems directly related to bi-AQST are discussed: the QMST and AQMST problems. Bracktracking and branch-and-bound exact algorithms are proposed to the target problem of this investigation. The heuristic algorithms developed are: Pareto Local Search, Tabu Search with ejection chain, Transgenetic Algorithm, NSGA-II and a hybridization of the two last-mentioned proposals called NSTA. The proposed algorithms are compared to each other through performance analysis regarding computational experiments with instances adapted from the QMST literature. With regard to exact algorithms, the analysis considers, in particular, the execution time. In case of the heuristic algorithms, besides execution time, the quality of the generated approximation sets is evaluated. Quality indicators are used to assess such information. Appropriate statistical tools are used to measure the performance of exact and heuristic algorithms. Considering the set of instances adopted as well as the criteria of execution time and quality of the generated approximation set, the experiments showed that the Tabu Search with ejection chain approach obtained the best results and the transgenetic algorithm ranked second. The PLS algorithm obtained good quality solutions, but at a very high computational time compared to the other (meta)heuristics, getting the third place. NSTA and NSGA-II algorithms got the last positions

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

O problema da Árvore Geradora Mínima Quadrática (AGMQ) é uma versão do problema da Árvore Geradora Mínima na qual se considera, além dos custos lineares tradicionais, uma estrutura de custos quadrática. Tal estrutura quadrática modela efeitos de interação entre pares de arestas. Os custos lineares e quadráticos são somados para compor o custo total da árvore geradora, que deve ser minimizado. Quando as interações são restritas às arestas adjacentes, o problema é denominado Árvore Geradora Mínima Quadrática em Adjacência de Arestas (AGMQA). A AGMQA e a AGMQ são problemas NP-difíceis que modelam diversos problemas de projeto de redes de transporte e distribuição. Em geral, a AGMQA emerge como um modelo mais apropriado para a modelagem de problemas reais. Embora, na literatura, os custos lineares e quadráticos sejam somados, em aplicações reais, os custos linear e quadrático podem ser conflitantes. Neste caso, seria mais interessante considerar os custos separadamente. Neste sentido, a Otimização Multiobjetivo provê uma modelagem mais realista para os problemas da AGMQ e da AGMQA. Uma revisão do estado da arte, até o momento, não foi capaz de encontrar qualquer trabalho que investigue esses problemas sob um ponto de vista biobjetivo. O objetivo desta Tese é, pois, o desenvolvimento de algoritmos exatos e heurísticos para o Problema Biobjetivo da Árvore Geradora Quadrática em Adjacência de Arestas (AGQA-bi). Para tanto, como fundamentação teórica, discutem-se outros problemas NP-difíceis diretamente relacionados à AGQA-bi, a saber: AGMQ e AGMQA. Algoritmos exatos backtracking e branch-and-bound são propostos para o problema-alvo desta investigação. Os algoritmos heurísticos desenvolvidos são: busca local Pareto Local Search, Busca Tabu com ejection chain, Algoritmo Transgenético, NSGA-II e uma hibridização das duas últimas propostas mencionadas denominada NSTA. Os algoritmos propostos são comparados entre si por meio da análise de seus desempenhos em experimentos computacionais com casos de teste adaptados da literatura da AGMQ. No que se refere aos algoritmos exatos, a análise considera, em especial, o tempo de execução. No caso dos algoritmos heurísticos, além do tempo de execução, a qualidade do conjunto de aproximação gerado é avaliada. Indicadores de qualidade são empregados para aferir tal informação. Ferramentas estatísticas apropriadas são usadas na análise de desempenho dos algoritmos exatos e heurísticos. Para o conjunto de instâncias utilizado e considerando os critérios de qualidade dos conjuntos de aproximação gerados e tempo de execução dos algoritmos, os experimentos mostraram que o algoritmo de Busca Tabu com ejection chain obteve melhores resultados e que o algoritmo transgenético ficou em segundo lugar. A busca local PLS obteve soluções de qualidade, mas a um tempo computacional muito alto se comparado às outras (meta)heurísticas. Nesse sentido, ocupa a terceira colocação. Por fim, ficaram os algoritmos NSTA e NSGAII