Author(s):
Carla Sofia de Assunção Gomes 
Date: 2008
Persistent ID: http://hdl.handle.net/10773/9525
Origin: RIA - Repositório Institucional da Universidade de Aveiro
Subject(s): Matemática aplicada; Problema do caixeiro viajante; Optimização combinatória
Description
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. Mestrado em Matemática e Aplicações
