Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/EABA-AGLJ5F| Type: | Dissertação de Mestrado |
| Title: | O Problema do Ladrão Viajante: propriedades e heurística |
| Authors: | Henrique Alves Magalhaes |
| First Advisor: | Ricardo Hiroshi Caldeira Takahashi |
| First Referee: | Denise Burgarelli Duczmal |
| Second Referee: | Eduardo Gontijo Carrano |
| Abstract: | Muitos problemas clássicos são estudados em otimização devido à suas capacidades de modelar algumas classes de problemas do mundo real, além de sua própria complexidade. Mas problemas clássicos de referência como o Problema da Mochila e o Problema doCaixeiro Viajante são os mesmos há algumas décadas, com algumas variantes sendo desenvolvidas ao longo deste período. Em 2013 foi proposto um problema que é baseado nestes dois, e foi chamado de Problema do Ladrão Viajante. Este problema não é apenas uma variação destes dois problemas clássicos, mas interconecta diversas características destes dois problemas sendo mais complexo e assim, possibilita uma melhor modelagem de problemas reais modernos.Foi feito um algoritmo genético com operadores personalizados, e este foi comparado a um método de resolução proposto que se baseia na divisão do problema em clusters. Esta divisão busca simplificar o problema e reduzir o espaço de busca com o fim de se obter um melhor desempenho do algoritmo genético original. Para esta comparação são feitas simulações de problemas onde os clusters se tornam cada vez mais próximos espacialmente, de modo que estes agrupamentos se tornam cada vez menos evidentes. |
| Abstract: | Many classic problems are studied in optimization because of their ability to model some classes of real-world problems, in addition to its own complexity. But classic reference problems like the Knapsack Problem and the Travelling Salesman Problem are the same for decades, with some variants being developed over this period. In 2013 it was proposed a problem which is based on these two, and was called the Travelling Thief Problem. This problem is not just a variation of these two classic problems, but interconnects various characteristics of these two problems being more complex and thus allow better modelling of modern real problems. A genetic algorithm with custom operators was made, and it was compared to resolution method which is based on the clustering of the problem. This division seeks to simplify the problem and reduce the search space in order to get a better performance of the original genetic algorithm. For this comparison it was made simulations of problems where the clusters are becoming closer spatially, so that these groups are becoming less evident. |
| Subject: | Matemática Otimização combinatória Problema do caixeiro viajante Otimização combinatoria Analise por conglomerados |
| language: | Português |
| Publisher: | Universidade Federal de Minas Gerais |
| Publisher Initials: | UFMG |
| Rights: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/EABA-AGLJ5F |
| Issue Date: | 30-Nov-2016 |
| Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| diss285.pdf | 1.65 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.