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 assinatura
• Este artigo NÃO é de acesso aberto
  
• Cor do Acesso Aberto: closed

---

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: 11 jan. 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 jan. 11 ] 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 jan. 11 ] 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 heuristic method for the close enough traveling salesman problem
• A block coordinate descent enhanced metaheuristic for the Euclidean traveling salesman problem with polygonal neighborhoods
• Uma abordagem contínua para o problema do caixeiro viajante
• Optimization of slice configuration of steel coils
• Assessing the reliability of general-purpose Inexact Restoration methods
• Foreword special issue dedicated to selected surveys in nonlinear programming. [Apresentação]
• Spectral projected gradient methods: review and perspectives
• Optimality properties of an Augmented Lagrangian method on infeasible problems
• Sequential equality-constrained optimization for nonlinear programming
• Augmented Lagrangians with possible infeasibility and finite termination for global nonlinear programming