Uma abordagem contínua para o problema do caixeiro viajante (2023)
- Authors:
- Autor USP: ERTEL, PAULA CRISTINA ROHR - IME
- Unidade: IME
- Sigla do Departamento: MAP
- DOI: 10.11606/D.45.2023.tde-27042023-223742
- Subjects: HEURÍSTICA; ALGORITMOS GENÉTICOS
- Keywords: Block coordinate descent methods; Continuous traveling salesman problem; Heuristics; Métodos de busca em bloco de coordenadas; Problema do caixeiro viajante; Problema do caixeiro viajante contínuo; Traveling salesman problem
- Agências de fomento:
- Language: Português
- Abstract: 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
- Imprenta:
- Data da defesa: 01.03.2023
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
ERTEL, Paula Cristina Rohr. Uma abordagem contínua para o problema do caixeiro viajante. 2023. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2023. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-27042023-223742/. Acesso em: 02 jan. 2026. -
APA
Ertel, P. C. R. (2023). Uma abordagem contínua para o problema do caixeiro viajante (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45132/tde-27042023-223742/ -
NLM
Ertel PCR. Uma abordagem contínua para o problema do caixeiro viajante [Internet]. 2023 ;[citado 2026 jan. 02 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-27042023-223742/ -
Vancouver
Ertel PCR. Uma abordagem contínua para o problema do caixeiro viajante [Internet]. 2023 ;[citado 2026 jan. 02 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-27042023-223742/ - A block coordinate descent enhanced metaheuristic for the Euclidean traveling salesman problem with polygonal neighborhoods
- Um método heurístico para o problema do caixeiro viajante suficientemente próximo
- A heuristic method for the close enough traveling salesman problem
- Optimization of slice configuration of steel coils
Informações sobre o DOI: 10.11606/D.45.2023.tde-27042023-223742 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
