Trabalho de evento-anais periodico

Um método heurístico para o problema do caixeiro viajante suficientemente próximo (2025)

• Authors:
  • Ertel, Paula Cristina Rohr
  • Birgin, Ernesto Julian Goldberg
• USP affiliated authors: BIRGIN, ERNESTO JULIAN GOLDBERG - IME ; ERTEL, PAULA CRISTINA ROHR - IME
• Unidade: IME
• DOI: 10.5540/03.2025.011.01.0495
• Subjects: OTIMIZAÇÃO COMBINATÓRIA; HEURÍSTICA
• Keywords: Problema do caixeiro viajante; Traveling salesman problem; Métodos de busca em bloco de coordenadas
• Agências de fomento:
  • Financiamento CAPES
• Language: Português
• Abstract: O Problema do Caixeiro Viajante (TSP, do inglês Traveling Salesman Problem) é um dos problemas de otimização combinatória mais estudados. Dado m cidades e seus pares de distâncias, busca-se encontrar um tour de distância mínima que passe por todas as cidades. Na variante Close-Enough do TSP (CETSP), não é necessário passar exatamente por cada cidade, mas por uma vizinhança de cada cidade. Esse problema pode ser modelado como um problema de otimização contínua com variáveis inteiras. Neste trabalho, apresentamos um método heurístico para encontrar soluções para o CETSP, incluindo uma heurística construtiva, uma busca local baseada no movimento 2-opt e um método de otimização contínua de busca em blocos de coordenadas. Experimentos numéricos foram realizados com 60 instâncias de pontos aleatórios e 10 instâncias da biblioteca TSPLIB adaptadas ao CETSP. O método proposto se sobressai, na maioria dos testes, em relação a qualidade de soluções e tempo de execução aos métodos que usam movimentos de realocação.
• Imprenta:
  • Publisher: SBMAC
  • Publisher place: São Carlos
  • Date published: 2025
• Source:
  • Título: Proceeding Series of the Brazilian Society of Computational and Applied Mathematics
  • Volume/Número/Paginação/Ano: v. 11, n. 1, p. 1-7, 2025
• Conference titles: Congresso Nacional de Matemática Aplicada e Computacional - CNMAC

Informações sobre o DOI: 10.5540/03.2025.011.01.0495 (Fonte: oaDOI API)
• Este periódico é de acesso aberto
• Este artigo NÃO é de acesso aberto
  

---

Download do texto completo

Tipo	Nome	Link
	3248313.pdf

How to cite

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

• ABNT

  ERTEL, Paula Cristina Rohr e BIRGIN, Ernesto Julian Goldberg. Um método heurístico para o problema do caixeiro viajante suficientemente próximo. Proceeding Series of the Brazilian Society of Computational and Applied Mathematics. São Carlos: SBMAC. Disponível em: https://doi.org/10.5540/03.2025.011.01.0495. Acesso em: 03 mar. 2026. , 2025

• APA

  Ertel, P. C. R., & Birgin, E. J. G. (2025). Um método heurístico para o problema do caixeiro viajante suficientemente próximo. Proceeding Series of the Brazilian Society of Computational and Applied Mathematics. São Carlos: SBMAC. doi:10.5540/03.2025.011.01.0495

• NLM

  Ertel PCR, Birgin EJG. Um método heurístico para o problema do caixeiro viajante suficientemente próximo [Internet]. Proceeding Series of the Brazilian Society of Computational and Applied Mathematics. 2025 ; 11( 1): 1-7.[citado 2026 mar. 03 ] Available from: https://doi.org/10.5540/03.2025.011.01.0495

• Vancouver

  Ertel PCR, Birgin EJG. Um método heurístico para o problema do caixeiro viajante suficientemente próximo [Internet]. Proceeding Series of the Brazilian Society of Computational and Applied Mathematics. 2025 ; 11( 1): 1-7.[citado 2026 mar. 03 ] Available from: https://doi.org/10.5540/03.2025.011.01.0495

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

• A block coordinate descent enhanced metaheuristic for the Euclidean traveling salesman problem with polygonal neighborhoods
• A heuristic method for the close enough traveling salesman problem
• Uma abordagem contínua para o problema do caixeiro viajante
• Optimization of slice configuration of steel coils
• An augmented Lagrangian method with finite termination
• Packing circles within ellipses
• Spectral projected gradient and variable metric methods for optimization with linear inequalities
• Sparse Projected-Gradient Method As a Linear-Scaling Low-Memory Alternative to Diagonalization in Self-Consistent Field Electronic Structure Calculations
• The boundedness of penalty parameters in an augmented Lagrangian method with constrained subproblems
• On acceleration schemes and the choice of subproblem’s constraints in augmented Lagrangian methods