Use este identificador para citar ou linkar para este item:
http://www.repositorio.ufal.br/jspui/handle/riufal/819
Tipo: | Dissertação |
Título: | Uma implementação em paralelo para decomposição de benders aplicada a sistemas eixo raio com múltipla atribuição |
Título(s) alternativo(s): | A parallel Benders decoposition implmentation for multiple hub and spoke system allocation |
Autor(es): | Cabral, Raquel da Silva |
Primeiro Orientador: | Luna, Henrique Pacca Loureiro |
metadata.dc.contributor.referee1: | Miranda Junior, Gilberto de |
metadata.dc.contributor.referee2: | Pereira, Leonardo Viana |
Resumo: | 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 sequencial. |
Abstract: | 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. |
Palavras-chave: | Hub and spoke systems Parallel programing Benders decomposition Sistemas eixo-raio Programação paralela Decomposição de Benders |
CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
Idioma: | por |
País: | BR |
Editor: | Universidade Federal de Alagoas |
Sigla da Instituição: | UFAL |
metadata.dc.publisher.department: | Modelagem Computacional de Conhecimento |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Modelagem Computacional de Conhecimento |
Citação: | CABRAL, Raquel da Silva. A parallel Benders decoposition implmentation for multiple hub and spoke system allocation.. 2006. 62 f. Dissertação (Mestrado em Modelagem Computacional de Conhecimento) - Universidade Federal de Alagoas, Maceió, 2006. |
Tipo de Acesso: | Acesso Aberto |
URI: | http://repositorio.ufal.br/handle/riufal/819 |
Data do documento: | 23-fev-2006 |
Aparece nas coleções: | Dissertações e Teses defendidas na UFAL - IC |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Uma implementação em paralelo para decomposição de benders aplicada a sistemas eixo raio com múltipla atribuição.pdf | 346.49 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.