Problema de alocação de frota : modelagem, simulação e comparação de algoritmos para resolver problemas MILP usando computação paralela

Abstract

Este trabalho, construído sobre pesquisas anteriores, investigou o emprego de paradigmas de programação paralela, aliado à execução de programas em múltiplos processadores e unidades de processamento gráfico - GPUs - para a resolução de problemas de alocação de frota. O objetivo foi modelar o Problema de Alocação de Frota com estruturas da linguagem Python de forma a possibilitar a resolução do modelo de programação linear mista resultante com recursos de programação paralela a nível de software e hardware. Para a consecução do objetivo foram empregadas abordagens a nível de software, dentro de um ambiente de programação centrado na linguagem Python, e hardware, com uso de equipamentos com processamento paralelo em CPU. Programas Python foram adaptados para o ambiente de computação paralela do NPAD/UFRN, tanto na forma interativa do Jupyter Notebook quanto para execução não assistida em linha de comando e por intermédio de arquivos de comandos para o interpretador bash. O desempenho na solução do Problema de Alocação de Frota foi avaliado para os solvers CBC e HiGHS. Os resultados encontrados corroboram trabalho anterior, trazem perspectivas quanto ao uso dos recursos de programação paralela para a solução de problemas de programação linear mista em geral e propostas para novos estudos sobre o tema.