Detalhes bibliográficos
| Ano de defesa: |
2023 |
| Autor(a) principal: |
Ertel, Paula Cristina Rohr |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Biblioteca Digitais de Teses e Dissertações da USP
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
https://www.teses.usp.br/teses/disponiveis/45/45132/tde-27042023-223742/
|
Resumo: |
O problema do caixeiro viajante contínuo ou CTSP, do inglês Continuous Traveling Salesman Problem, é uma variante do problema do caixeiro viajante (TSP) na qual cada cidade pertence a um conjunto arbitrário e o objetivo é determinar o tour de menor comprimento que passa por cada um dos conjuntos e retorna ao primeiro. Neste trabalho consideramos o CTSP em que os conjuntos visitados são dados por bolas pertencentes ao R^2. Ou seja, dado um conjunto de m bolas do R^2, estamos interessados em determinar pontos x^i, um em cada bola, e uma permutação de modo que o tour passando pelos pontos x^i com a ordem dada pela permutação tenha comprimento mínimo. Para resolver este problema propomos quatro algoritmos, nos quais unimos heurísticas já consolidadas para o TSP clássico, como a heurística 2-Opt, com um método de busca em bloco de coordenadas. Os algoritmos foram implementados na linguagem de programação Fortran 90 e para testá-los geramos 60 instâncias de pontos aleatórios, sendo 10 para cada número de bolas m = 50, 100, 200, 300, 400 e 500. Além disso, foram realizados experimentos numéricos com 10 instâncias da biblioteca TSPLIB adaptadas ao CTSP. Tabelas foram geradas para cada experimento, detalhando as soluções encontradas pelos métodos e seus desempenhos, permitindo realizar comparações entre eles. Figuras das soluções encontradas pelos métodos também são apresentadas para algumas instâncias. |
