Return to search

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

Made available in DSpace on 2015-05-08T14:53:38Z (GMT). No. of bitstreams: 1
arquivototal.pdf: 7900350 bytes, checksum: fbca2db827307d8c3ed2a1c15067d0da (MD5)
Previous issue date: 2014-02-13 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / 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. / 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.

Identiferoai:union.ndltd.org:IBICT/oai:tede.biblioteca.ufpb.br:tede/5268
Date13 February 2014
CreatorsCoutinho, Walton Pereira
ContributorsNascimento, Roberto Quirino do, Subramanian, Anand
PublisherUniversidade Federal da Paraí­ba, Programa de Pós-Graduação em Engenharia de Produção, UFPB, BR, Engenharia de Produção
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Formatapplication/pdf
Sourcereponame:Biblioteca Digital de Teses e Dissertações da UFPB, instname:Universidade Federal da Paraíba, instacron:UFPB
Rightsinfo:eu-repo/semantics/openAccess
Relation-8217436986773215563, 600, 600, 600, 600, 2087065505892217820, 2551182063231974631, 2075167498588264571

Page generated in 0.0026 seconds