Uma Abordagem Heurística para a Solução de Problemas de Recobrimento de Conjuntos de Grande Porte, em Aplicação de Alocação de Tripulação para Companhias Aéreas
Autores
|
4481 |
44,1015,519,2010
|
|
|
4482 |
44,1015,519,2010
|
|
|
4483 |
44,1015,519,2010
|
|
|
4484 |
44,1015,519,2010
|
Informações:
Publicações do PESC
Este trabalho apresenta uma nova metodologia para a solução de problemas de recobrimento de conjuntos de grande porte, com aplicação ao problema de alocação de tripulações para companhias aéreas. O problema de alocação de tripulações é definido e contextualizado, e são apresentados alguns métodos de solução existentes. É proposta uma formulação que divide o processo de solução em duas etapas: geração das rotações e otimização. A abordagem escolhida envolve a prévia geração de um conjunto de rotações, e a partir deste, a busca de uma boa solução inteira. Para a fase de geração das rotações foi desenvolvido um algoritmo paralelo, com base na meta-heurística GRASP. Na fase de otimização foi utilizado o modelo de recobrimento de conjuntos para o qual foi desenvolvido um algoritmo híbrido, baseado em técnicas de Branch-and-Bound. Os algoritmos foram testados utilizando um problema real de uma companhia aérea nacional e os resultados obtidos são apresentados.
The present work Proposes a new method for solving large scale set covering problems with application to the airline crew pairing problem.
The definition, context and main characteristcs of the crew pairing problem are presented, as well as some existing solution methods.
A problem formulation is proposed, dividing the solution process into two phaes: pairing generation and otimization. A solution approach is chosen: the pairing generation phase is conducted first, originating a subproblem of the global crew pairing problem; and the optimization process searches for a good integer solution within the subproblem generated.
A parallel algorithm, based on the meta-heuristic GRASP, is developed and tested in the pairings generation phase. In the second phase, a set covering based model is proposed and an hybrid algorithm based on a branch-and-nound approach develoed.
The algorithms are tested using a real rpoblem from a domestic airline carrier and the computational results presented.