Arquitetura híbrida multiagente AMAM aplicada ao problema p-Hub Centro

Abstract

Esta Dissertação estuda duas variantes do Problema pHub Centro (pHCP), denominadas Problema pHub Centro não Capacitado de Múltiplas Alocações (UMApHCP) e o Problema pHub Centro Capacitado de Múltiplas Alocações (CMApHCP). Inicialmente, a descrição destas variantes é apresentada, incluindo suas caracterizações, modelos matemáticos e uma revisão bibliográfica do estado da arte associado. Em seguida, introduz-se a fundamentação teórica necessária para o desenvolvimento dessa dissertação. Como se trata de problemas NP-Difíceis, esta dissertação utilizou-se, além de modelos de programação matemática, de técnicas heurísticas e metaheurísticas. A implementação destas últimas é realizada usando-se um estrutura híbrida multiagente denominada Framework AMAM. O Framework AMAM possui capacidade de hibridização de metaheurísticas através da abordagem multiagente. O espaço de busca de cada agente deste é o próprio espaço de busca do problema, possibilitando flexibilidade para tratar problemas distintos. A ação do agente no espaço de busca é autônoma e permite a execução simultânea de vários agentes, de forma cooperativa. Esta dissertação propõe três propostas de resolução, implementadas no Framework AMAM, para a solução dos problemas abordados, além da solução via programação matemática. A primeira proposta, para a resolução do UMApHCP, consiste em um método híbrido, que combina a fase de construção da metaheurística GRASP com um Algoritmo Genético. A segunda proposta, também para a resolução do UMApHCP, substitui, na primeira proposta, o algoritmo genético pela metaheurística ILS. A terceira proposta, para a solução do problema CMApHCP, utiliza a metaheurística VNS e a heurística de busca local VND, combinada com a fase de construção da metaheurística GRASP. Estas propostas foram avaliadas por meio de testes computacionais em conjuntos de instâncias disponíveis na literatura. Os resultados obtidos foram satisfatórios e comprovam a eficiência do Framework AMAM, além de mostrar que a utilização de sistemas multiagente é eficaz na resolução de problemas de otimização.

This dissertation addresses two variants of the pHub Center Problem (pHCP), called Uncapacitated Multiple Allocation pHub Center Problem (UMApHCP) and Capacitated Multiple Allocation pHub Center Problem (CMApHCP). First, the description of these variants is presented, including their characterizations, mathematical models, and a bibliographic review concerning the associated state-of-the-art. Following, the necessary theoretical foundation for the development of this work is revised. As these are NP-Hard problems, in addition to mathematical programming models, this work uses heuristic and metaheuristic techniques for solving them. The implementation of the heuristic and metaheuristics used a hybrid multi-agent structure called the AMAM Framework. The AMAM Framework can hybridize metaheuristics through the multi-agent approach. The search space for each agent in this framework is the problem search space, allowing flexibility to deal with different problems. The agents in the search space are autonomous, allowing the simultaneous and cooperative execution of several agents. This work proposes three resolution proposals, implemented in the AMAM Framework, for the solution of the addressed problems, in addition to the solution via mathematical programming. The first proposal, used for solving the UMApHCP problem, was a hybrid method, which combined the construction phase of the GRASP metaheuristic with a genetic algorithm. The second proposal replaces the genetic algorithm with the ILS metaheuristic in the first proposal. The third proposal, for solving the CMApHCP problem, also a hybrid method, combined the construction phase of the GRASP metaheuristic with the VNS metaheuristic and the VND local search heuristic. These proposals were evaluated using computational tests on instance sets available in the literature. The results obtained were satisfactory and proved the efficiency of the AMAM Framework, and, besides, showed that the use of multi-agent systems is effective in solving optimization problems.