Publicação
Um algoritmo branch-and-bound para o problema do caixeiro viajante suficientemente próximo
| 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. |
|---|---|
| Autores principais: | Coutinho, Walton Pereira |
| Assunto: | 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 ENGENHARIAS::ENGENHARIA DE PRODUCAO |
| Ano: | 2015 |
| País: | Brasil |
| Tipo de documento: | dissertação de mestrado |
| Tipo de acesso: | acesso aberto |
| Instituição associada: | IBICT |
| Idioma: | português |
| Origem: | Oasisbr |
| 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. |
|---|
Atividades financiadas
Não foram encontrados projetos financiados.