Contribuições para a Solução do Problema do Caixeiro Viajante Assimétrico
Autores
|
1642 |
693,44
|
|
|
1643 |
693,44
|
Informações:
Publicações do PESC
Contribuições para a Solução do Problema do Caixeiro Viajante Assimétrico
Rosa Maria Videira de Figueiredo
Maio/1998
| Orientador: | Nelson Maculan Filho $Corientador" ?> | |
| ||
Diversas formulações de programação linear inteira são conhecidas
para o Problema do Caixeiro Viajante Assimétrico. Embora diferentes formulações
de um problema representem as mesmas soluções viáveis para este, elas podem
diferir em diversos aspectos.
Neste trabalho são analisados os limites inferiores fornecidos pelas
respectivas relaxações lineares de duas formulações de programação linear inteira
as quais modelam o Problema do Caixeiro Viajante Assimétrico como um problema
de fluxo em um grafo direcionado. As formulações analisadas são as formulações de
Claus (1984) e de Finke, Claus & Gunn (1984).
Como ferramenta para tal análise foi implementado um algoritmo de planos
de corte utilizando rotinas de separação conhecidas na literatura para classes de
desigualdades simétricas, que definem facetas do politopo associado. Além disso,
é apresentada uma nova rotina de separação para uma classe de desigualdades
assimétricas.
Foram realizados testes computacionais em intâncias geradas aleatoriamente
e com instâncias do mundo real disponíveis em uma biblioteca pública. Resultados
computacionais mostraram que os limites inferiores obtidos foram próximos ao ótimo
e que a rotina de separação aqui proposta se mostrou bastante eficiente.
Contribuition to the Solution of the Asymmetric Traveling Salesman Problem
Rosa Maria Videira de Figueiredo
May/1998
| Advisor: | Nelson Maculan Filho | |
| Department: Systems Engineering and Computer Science | ||
Several integer programming formulations to the Asymmetric Traveling
Salesman Problem have been proposed in the literature. Although different
formulations for a same problem do convey the same set of feasible solutions for
the problem, those formulations may differ in a number of ways.
We analyze the lower bounds produced by the linear relaxation of
two integer programming formulations. The formulations considered (Claus, 1984;
Flinke, Claus e Gunn, 1984) model the Asymmetric Travelling Salesman Problem like
a flow problem in a directed graph.
In order to analyze those formulations we implemented a cutting
plane algorithm that use some separation routines from the literature for classes
of symmetric constraints. A new separation algorithm for a class of asymmetric
constraints was also proposed in this thesis and used in the study.
Preliminary computational tests were conducted on randomly generated
instances and on some real world instances from the literature. The lower
bounds obtained were close to optimality, and the proposed separation algorithm
have shown to be very effective.