Problema do caixeiro viajante

Abstract

O Problema do Caixeiro Viajante (PCV) pode ser entendido como o problema de um vendedor que deseja visitar um conjunto de cidades, passando exactamente uma vez por cada uma e voltando ao ponto de partida no final do seu percurso. O PCV está classificado como NP- Completo, o que faz com que seja de muito difícil resolução. A grande dificuldade na obtenção da solução óptima deste tipo de problemas, deve-se ao elevado número de restrições que cresce exponencialmente com o número de clientes. Neste trabalho, começamos por introduzir o problema com exemplos bastante simples, onde são exibidos métodos heurísticos para a sua resolução. De seguida, é feita uma abordagem mais formal, onde são apresentados vários resultados que permitem reduzir substancialmente o número de restrições. Posteriormente, é feito um estudo de várias instâncias do problema, de forma a averiguar o comportamento das restrições de eliminação de sub-ciclos e o modo como estas se influenciam mutuamente. A grande parte dos testes efectuados neste trabalho apontam para a existência de uma forte redundância, do ponto de vista prático, na maior parte das restrições de eliminação de sub- -ciclos. Assim, os resultados obtidos indicam que apenas uma pequena percentagem das restrições de eliminação de sub-ciclos é necessária para a obtenção da solução óptima do problema.

The Travelling Salesman Problem (TSP) can be seen as a problem of a salesman that wants to visit a set of cities, passing by each city exactly one time and returning to the starting point at the end of his tour. The TSP is classified as a NP-Complete problem, which makes it a very hard to solve. The major difficulty in obtaining the optimal solution of this kind of problems is in the large number of constraints, that grows exponentially with the number of clients. In this work, we start by introducing the problem through simple examples, where heuristic methods to obtain a solution are presented. Next, we take a more formal approach, where several results that allow for a considerable reduction on the number of constraints are presented. An analysis of several instances of the problem is then performed, with the objective of analysing the behaviour of the sub-cycle elimination constraints and the way they mutually interfere. The majority of the tests presented in this work indicate that there exists high redundancy, from a practical point of view, in most of the sub-cycle elimination constraints. Therefore, the results indicate that only a small percentage of the sub- -cycle elimination constraints is necessary to obtain the optimal solution for the problem.