Spelling suggestions: "subject:"longerenough traveling salesman problem"" "subject:"longenough traveling salesman problem""
1 |
Um algoritmo branch-and-bound para o problema do caixeiro viajante suficientemente próximoCoutinho, Walton Pereira 13 February 2014 (has links)
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.
|
Page generated in 0.1722 seconds