Aplicação de heurísticas para solucionar cenários de média escala do problema do mochileiro viajante

Abstract

Nesta dissertação é apresentado o Problema do Mochileiro Viajante, sendo este um problema multicomponente composto da combinação de outros dois problemas bastante conhecidos e estudados pela comunidade acadêmica: o Problema do Caixeiro Viajante e o Problema da Mochila. Todo problema multicomponente possui duas características importantes: combinação e interdependência. A combinação existe porque um problema multicomponente deve ser composto de dois ou mais problemas individuais de otimização. A interdependência ocorre quando a combinação desses subproblemas torna- os capazes de afetar o resultado um do outro, como consequência, se forem resolvidos separadamente e suas melhores soluções individuais colocadas em união, não levarão, necessariamente, à melhor solução para o problema completo. Na definição do problema aqui tratado, a interdependência age através do impacto no tempo para percorrer a rota escolhida conforme diversos itens, com pesos específicos, são coletados (ou não) nas cidades onde estão localizados. Esse problema foi proposto através de uma discussão teórica sobre a distância encontrada entre os problemas enfrentados pelas indústrias e corporações, por vezes compostos por diversos subproblemas, e a maneira como, em geral, os pesquisadores tentam solucioná-los individualmente, impossibilitando assim uma visão maior do cenário onde se encontram e no impacto do relacionamento entre eles. Neste trabalho são realizados diversos estudos sobre a maneira como a interdependência dos componentes do PMV afeta o espaço de busca do mesmo, havendo propostas de heurísticas para solucioná-lo apenas com base em seus dados de entrada e de uma meta-heurística capaz de iniciar uma busca com uma solução inicial previamente fornecida e melhorá-la significativamente através de uma exploração de parte desse espaço de busca, sendo o percurso dessa exploração guiado por outra heurística que usa conhecimentos sobre a forma que os componentes do problema interagem entre si. Experimentos computacionais e análises estatísticas foram realizados para que as heurísticas aqui propostas pudessem ser melhor adaptadas para solucionar um conjunto de instâncias com as mais diversas características. Os resultados obtidos após esses experimentos são comparados com os resultados encontrados em outros três trabalhos presentes na literatura, revelando uma maior eficácia por parte das heurísticas aqui propostas quando cenários de pequeno e médio tamanho são selecionados.

In this dissertation the Travelling Thief Problem is presented, being this a multicomponent problem composed of the combination of two others well known and studied problems by the academic community: the Traveling Salesman Problem and the Knapsack Problem. Every multi-component problem has two important characteristics: combination and interdependence. The combination exists because a multi-component problem must be composed of two or more individual optimization problems. Interdependence occurs when the combination of these subproblems makes them capable of affecting each other's result, as a consequence, if solved separately and their best individual solutions put together, will not necessarily lead to the best solution to the whole problem. In the definition of the problem treated here, interdependence acts through the impact in time to go through the chosen route as several items, with specific weights, are collected (or not) in the cities where they are located. This problem has been proposed through a theoretical discussion about the distance found between the problems faced by industries and corporations, sometimes composed of several subproblems, and the way in which researchers in general try to solve them individually, thus preventing a whole view of the problem that they are in and the impact of the relationship between them. In this work several studies are carried out on how the interdependence of TTP components affects the search space of the problem, with heuristics proposals to solve it only based on its input data and a metaheuristic capable of initiating a search with a previously provided initial solution and significantly improve it by exploiting part of that search space with the exploration path being guided by another heuristic that uses knowledge about how the problem components interact with each other. Computational experiments and statistical analyzes were performed so that the heuristics proposed here could be better adapted to solve a set of instances with the most diverse characteristics. The results obtained after these experiments are compared with the results found in three other papers present in the literature, revealing a better efficiency by the heuristics proposed here when small and medium size instances are selected.