Esta pesquisa trata o Problema de Programação de Tripulantes (PPT), presente no planejamento operacional das empresas aéreas. O principal objetivo do PPT é atribuir um conjunto de tarefas aos tripulantes, considerando as regulamentações trabalhistas, as regras de segurança e as políticas das empresas, de tal maneira que o custo da tripulação seja mínimo. O PPT é normalmente dividido em dois subproblemas, resolvidos sequencialmente: Problema de Determinação das Viagens (PDV) e Problema de Atribuição de Escalas (PAE). No PDV, determina-se um conjunto de viagens que cubra todos os voos planejados. Em seguida, no PAE, as escalas, compostas pelas viagens escolhidas e outras atividades como folgas, sobreavisos, reservas, treinamentos e férias, são atribuídas aos tripulantes. Esta decomposição justifica-se pela natureza combinatória do PPT, porém não incorpora as disponibilidades e as preferências dos tripulantes em ambos os subproblemas (PDV e PAE), gerando assim custos extras relacionados aos conflitos que surgem durante a atribuição das escalas aos tripulantes no PAE. Além disso, as estimativas de custos adotadas no PDV não possuem caráter global, já que o custo real da programação só pode ser obtido após a atribuição das escalas. O estado da arte envolve a solução integrada do PPT, em que se elimina a necessidade de resolver inicialmente o PDV, provendo assim uma melhor estimativa de custo e uma programação final com melhor qualidade, por considerar os custos da tripulação, as disponibilidades e preferências dos tripulantes de forma global. O problema, no entanto, é NP-Difícil. Assim sendo, a metodologia proposta nesta pesquisa objetiva a solução do PPT de forma integrada, através de um Algoritmo Genético Híbrido (AGH) associado a um procedimento de busca em profundidade, levando em conta as particularidades da legislação brasileira. A metodologia foi testada, com sucesso, para a solução de instâncias baseadas na malha real de uma empresa aérea brasileira.

This master of science research treats the Crew Scheduling Problem (CSP), as part of the airlines operational planning. The main aim of the CSP is to assign a set of tasks to crew members, considering the labor regulations, safety rules and policies of companies, such that the crew cost is minimal. The CSP is divided into two subproblems, solved sequentially: Crew Pairing Problem (CPP) and Crew Rostering Problem (CRP). First, CPP provides a set of pairings that covers all the planned flights. Then, in the CRP, the rosters, encompassing the pairings and other activities such as rest periods, alert duties, reserve duties, training times and vacations, are assigned to the crew members. This decomposition is justified by the combinatorial nature of the CSP, but it not incorporates the crew members availabilities and preferences in both subproblems (CPP and CRP), generating extra costs related to conflicts that arise during the assignment of rosters to the crew members in the CRP. Besides, the costs estimations adopted in the CPP does not have a global character, since the real cost of the global schedule can be only obtained after the assignment of the rosters. The state of the art involves the integrated solution of CSP, where the CPP does not need to be solved, thus providing a better estimated cost and a better schedule quality, considering crew costs and also crew members availabilities and preferences globally. The problem, however, is NP-Hard. Therefore, the methodology proposed in this master of science research aims to obtain an integrated solution of the CSP, through an hybrid algorithm genetic associated with a depth-first search procedure, taking into account the Brazilian legislation. The methodology was tested, with success, to solve instances related a real network of a Brazilian airline.