Hub and Spoke systems, is a important research area in localization theory. This occur,
because of these systems are very used in logistics problems, e.g., telecommunication
networks and transport of passenger and load.To serve the demand of each pair
source destination, basically, the Hub and Spoke system replaces direct connections
between the pairs for a hubs network. These hubs group the traffic sharing the transportation
medium. To get the best hubs configuration is necessary efficient methods,
because this problem, hubs allocation, is a NP-problem. In this work was developed an
parallel implementation of the Benders Decomposition method for the uncapacitated
multiple allocation hub location problem. In our implementation we use the Skorin-
Kapov model. The parallel implementation of Benders Decomposition for hub and
spoke problem is not known in literature. The results show that the parallel approach
is applicable and more efficient that nonparallel one. The experiments reveals that the
parallel algorithm had a time execution 70% minor when compared with the nonparallel
one. / Sistemas do tipo eixo raio, tornaram-se uma importante área de pesquisa da teoria de localização nas últimas décadas. Esse destaque deve-se em grande parte ao sucesso de sua utilização em sistemas logísticos, tanto de transporte de passageiros quanto de cargas, e em redes de telecomunicações. Ao invés de servir cada par origem destino de demanda com uma conexão direta, sistemas do tipo eixo raio substituem essas conexões diretas por uma rede de concentradores. Esses concentradores permitem que o tráfego seja agrupado e transportado através de um meio de transporte compartilhado, para ser então entregue aos respectivos destinos. Sendo um problema NP, é necessário o uso de métodos eficientes para sua resolução. Neste trabalho, é desenvolvida uma implementação em paralelo do método de Decomposição de Benders
para o problema de localização de concentradores de alocação múltipla não capacitados. A implementação em paralelo do método de Decomposição de Benders para o problema eixo raio não é conhecido na literatura, entretanto os bons resultados obtidos pelo algoritmo paralelo desenvolvido revelam que a abordagem paralela é aplicável e mais eficiente. Nos experimentos realizados, o algoritmo paralelo apresentou um tempo de resposta até 70% menor que o tempo de resposta do algoritmo seqüencial.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.repositorio.ufal.br:riufal/819 |
| Date | 23 February 2006 |
| Creators | Cabral, Raquel da Silva |
| Contributors | Luna, Henrique Pacca Loureiro, Luna, H. P. L., Miranda Junior, Gilberto de, MIRANDA JR, G., Pereira, Leonardo Viana, http://lattes.cnpq.br/1126995918085550 |
| Publisher | Universidade Federal de Alagoas, BR, Modelagem Computacional de Conhecimento, Programa de Pós-Graduação em Modelagem Computacional de Conhecimento, UFAL |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFAL, instname:Universidade Federal de Alagoas, instacron:UFAL |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | bitstream:http://www.repositorio.ufal.br:8080/bitstream/riufal/819/1/Dissertacao_RaqueldaSilvaCabral_2006.pdf, bitstream:http://www.repositorio.ufal.br:8080/bitstream/riufal/819/2/Dissertacao_RaqueldaSilvaCabral_2006.pdf.txt |
Page generated in 0.0027 seconds