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.
| Identifer | oai:union.ndltd.org:IBICT/oai:tede.biblioteca.ufpb.br:tede/5268 |
| Date | 13 February 2014 |
| Creators | Coutinho, Walton Pereira |
| Contributors | Nascimento, Roberto Quirino do, Subramanian, Anand |
| Publisher | Universidade Federal da Paraíba, Programa de Pós-Graduação em Engenharia de Produção, UFPB, BR, Engenharia de Produção |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFPB, instname:Universidade Federal da Paraíba, instacron:UFPB |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | -8217436986773215563, 600, 600, 600, 600, 2087065505892217820, 2551182063231974631, 2075167498588264571 |
Page generated in 0.0026 seconds