O Problema do Ladrão Viajante: propriedades e heurística

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.