Extensões do problema do caixeiro viajante

Abstract

Esta dissertação tem como objetivo o estudo do problema do caixeiro viajante, um problema clássico de otimização combinatória. Apesar da sua simples descrição, o problema do caixeiro viajante é um problema NP-Difícil, não existindo até à data um algoritmo ótimo e eficiente para a sua resolução. Inicialmente será feito um estudo do problema nas suas variantes simples e múltipla (onde são considerados vários caixeiros). Em seguida será estudado o problema do caixeiro viajante multi-objetivo, também nas suas variantes simples e múltipla. Na otimização multi-objetivo o conceito de solução ótima é substituído pelo conceito de eficiência, deixando de haver um valor ótimo único para o problema. É introduzida a noção de dominância de forma a determinar o conjunto das soluções eficientes sendo este o objetivo na resolução de problemas multi-objetivo. Para cada um dos problemas abordados, serão referidas diversas variantes e formulações, bem como diversos algoritmos presentes na literatura para a sua resolução. Posteriormente são propostos novos algoritmos com o objetivo de resolver cada um dos problemas abordados. São apresentados resultados computacionais para cada método implementado, de forma a analisar o desempenho dos algoritmos propostos.

This thesis aims to study the travelling salesman problem, a classical problem of combinatorial optimization. Despite its simple description, the traveling salesman problem is NP-Hard, not existing, so far, an optimum and eficient algorithm to solve it. We start by studying the problem in its single and multiple variants (where multiple salesman are considered). Furthermore, we will study the multi-objective travelling salesman problem, also in its single and multiple variants. In multi-objective optimization, the concept of optimal solution is replaced by the concept of eficiency, ceasing to be a single optimal value to the problem. We introduce the notion of dominance in order to determine the set of eficient solutions which is the main purpose when solving a multi-objective problem. For each of the problems addressed, several variants and formulations will be referred, as well as several algorithms in the literature for their resolution. Afterward, new algorithms are proposed with the aim of solving each one of the problems addressed. For each implemented method, computational results are shown, in order to analyze the performance of the proposed algorithms.