Repositório Institucional da UFPB
Use este identificador para citar ou linkar para este item:
https://repositorio.ufpb.br/jspui/handle/tede/5268| Tipo: | Dissertação |
| Título: | Um algoritmo branch-and-bound para o problema do caixeiro viajante suficientemente próximo |
| Autor(es): | Coutinho, Walton Pereira |
| Primeiro Orientador: | Nascimento, Roberto Quirino do |
| Primeiro Coorientador: | Subramanian, Anand |
| Resumo: | Esta pesquisa trata do Problema do Caixeiro Viajante Suficientemente Próximo, uma variante do Problema do Caixeiro Viajante que possui diversas aplicações em logística. No Problema do Caixeiro Viajante Suficientemente Próximo, ao invés de visitar o próprio vértice (cliente), o caixeiro deve visitar uma região especifica contendo este vértice. Para resolver este problema, é proposto um algoritmo exato, simples e efetivo, baseado em branch-and-bound e Programação Cônica de Segunda Ordem. O algoritmo proposto foi testado em 824 instâncias sugeridas na literatura. Soluções ótimas foram obtidas para instâncias com até mil vértices. Foram consideradas instâncias nos espaços bi e tridimensional. |
| Abstract: | 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. |
| Palavras-chave: | Problema do caixeiro viajante suficientemente próximo Branch-and-bound Programação cônica de segunda ordem Logística Close-enough traveling salesman problem Branch-and-bound Second order cone programming Logistics |
| CNPq: | ENGENHARIAS::ENGENHARIA DE PRODUCAO |
| Idioma: | por |
| País: | BR |
| Editor: | Universidade Federal da Paraíba |
| Sigla da Instituição: | UFPB |
| Departamento: | Engenharia de Produção |
| Programa: | Programa de Pós-Graduação em Engenharia de Produção |
| Citação: | COUTINHO, Walton Pereira. Um algoritmo branch-and-bound para o problema do caixeiro viajante suficientemente próximo. 2014. 61 f. Dissertação (Mestrado em Engenharia de Produção) - Universidade Federal da Paraíba, João Pessoa, 2014. |
| Tipo de Acesso: | Acesso aberto |
| URI: | https://repositorio.ufpb.br/jspui/handle/tede/5268 |
| Data do documento: | 13-Fev-2014 |
| Aparece nas coleções: | Centro de Tecnologia (CT) - Programa de Pós-Graduação em Engenharia de Produção |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| arquivototal.pdf | 7,72 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.