Um algoritmo branch-and-bound para o problema do caixeiro viajante suficientemente próximo

Detalhes bibliográficos
Ano de defesa: 2014
Autor(a) principal: Coutinho, Walton Pereira
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal da Paraí­ba
BR
Engenharia de Produção
Programa de Pós-Graduação em Engenharia de Produção
UFPB
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Problema do caixeiro viajante suficientemente próximo
Branch-and-bound
Programação cônica de segunda ordem
Logística
Close-enough traveling salesman problem
Second order cone programming
Logistics
ENGENHARIAS::ENGENHARIA DE PRODUCAO
Link de acesso: https://repositorio.ufpb.br/jspui/handle/tede/5268
Resumo: This research deals with the Close-Enough Traveling Salesman Problem, a variant of the Traveling Salesman Problem wich has several applicatios in logistics. In the Close-Enough Traveling Salesman Problem, rather than visiting the vertex (customer) itself, the salesman must visit a specific region containing such vertex. To solve this problem, we propose a simple yet effective exact algorithm, based on Branch-and-Bound and Second Order Cone Programming. The proposed algorithm was tested in 824 instances suggested in the literature. Optimal solutions are obtained for open problems with up to a thousand vertices. We consider both instances in the two- and three-dimensional space.

Registros relacionados