Tese

Uma abordagem contínua para o problema do caixeiro viajante (2023)

• Authors:
  • Ertel, Paula Cristina Rohr
  • Birgin, Ernesto Julian Goldberg (Orientador)
• 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:
  • Financiamento CAPES
• 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:
  • Publisher place: São Paulo
  • Date published: 2023
• Data da defesa: 01.03.2023

Informações sobre o DOI: 10.11606/D.45.2023.tde-27042023-223742 (Fonte: oaDOI API)
• 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

---

How to cite

A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

• 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: 28 abr. 2024.

• 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 2024 abr. 28 ] 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 2024 abr. 28 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-27042023-223742/

Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

• A heuristic method for the close enough traveling salesman problem