| Autor: |
Henrique de Oliveira Gressler, Márcia Cristina Cera |
| Jazyk: |
English<br />Portuguese |
| Rok vydání: |
2014 |
| Předmět: |
|
| Zdroj: |
Revista Brasileira de Computação Aplicada, Vol 6, Iss 2, Pp 35-47 (2014) |
| Druh dokumentu: |
article |
| ISSN: |
2176-6649 |
| DOI: |
10.5335/rbca.2014.3660 |
| Popis: |
O Problema do Roteamento de Veículos (PRV) é um problema combinatório de difícil solução, aplicável tanto para logística de empresas de transporte quanto para melhor ocupação das vias públicas. Resolvê-lo testando todas as combinações possíveis (método de força bruta) torna-se inviável à medida que o problema escala, pois demanda um tempo de computação muito grande. Os Algoritmos Genéticos (AG) são meta-heurísticas capazes de encontrar soluções em um tempo computacional aceitável. Entretanto, mesmo os AG podem demandar um elevado tempo de processamento, dependendo das configurações utilizadas. Com a evolução das arquiteturas computacionais e a difusão das arquiteturas multicore, o uso da programação multithread torna-se uma alternativa para reduzir o tempo envolvido na solução de problemas combinatórios. Este artigo objetiva acelerar a resolução do PRV por meio da paralelização do AG com OpenMP, que é um padrão amplamente difundido para programação multithread. Nossos resultados atingiram um speedup acima de 2, utilizando 4 threads em um processador quadcore. Esse ganho está limitado à forma como o AG está implementado. Além do impacto no desempenho do AG também comprovou-se que o uso do OpenMP não afeta a qualidade das soluções. Adicionalmente, o uso do OpenMP permitiu que o AG encontrasse melhores soluções devido ao aumento do número de evoluções computadas num mesmo intervalo de tempo. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
