Um método heurístico para o problema do caixeiro viajante suficientemente próximo (2025)
- Authors:
- 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:
- 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
- Este periódico é de assinatura
- Este artigo NÃO é de acesso aberto
- Cor do Acesso Aberto: closed
-
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 - 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
Informações sobre o DOI: 10.5540/03.2025.011.01.0495 (Fonte: oaDOI API)
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
