Um Algoritmo Híbrido para a Solução de Problemas de Escala de Motoristas

Apresenta-se, nesta tese, uma metodologia híbrida para resolução de Problemas de Escalonamento de Motoristas(PEM).Na literatura, existem muitas contribuições sobre o Problema de Escalonamento de Motoristas(PEM), em geral, modelamos esse problema como um Problema de Particionamento de Conjuntos, que no caso, não podemos resolvê-lo através de Algoritmos exatos, pois, o PPC é um problema NPCompleto. Então, uma forma que muitos autores adotam são algoritmos heurísticos de busca local para resolver problemas com dados reais, mas esses algoritmos podem se perder no grande espaço de solução gerado pela solução inicial.Então, uma proposta feita para esse trabalho é resolver o problema através de geração de colunas, com auxílio de algoritmos heurísticos para acelerar o processo de geração de novas colunas no subproblema pricing, obtendo assim, um número reduzido de colunas, que nos facilita na resolução do problema mestre, que um Problema de Particionamento de Conjuntos(PPC).Para comprovar a eficiência da metodologia em resolver tal problema, repotamos resultados computacionais para dados na literatura, que foram tomados na literatura, e que comprova o método híbrido pode resolver de forma exata Problemas de Escalonamento de Motoristas(PEM) mais rapidamente que utilizando-se apenas métodos exatos ou apenas heurísticas.