Document details

O problema de alocação de tripulações em redes de transporte (PAT) é uma tarefa bastante rotineira no contexto de grandes empresas de transporte. Tal atividade envolve, basicamente, subdividir um conjunto de jornadas entre diferentes tripulações respeitando legislações trabalhistas e normas operacionais vigentes e impostas às empresas que atuam nesse setor. Por se tratar de um problema de grande complexidade computacional, o mesmo costuma ser divido em dois subproblemas: problema de recobrimento e problema de seqüenciamento de jornadas. Essa dissertação tem seu foco no Problema de Recobrimento. Além da definição formal do mesmo e de uma revisão da literatura, também são apresentados dois algoritmos para a sua resolução: um algoritmo lagrangeano e um genético. Por fim, resultados computacionais são apresentados com o objetivo de avaliar o desempenho dos algoritmos apresentados. Palavras-chave: Escalonamento de Tripulações, Problema de Recobrimento, Algoritmo Genético, Algoritmo Lagrangeano, Problema de Seqüenciamento de Jornadas.

The crew scheduling problem is a common activity that appears on public transport companies. The main goal of this problem is to assign the tasks to be carried out to different crews such that rules and regulations are respected and costs minimized. This problem is considered NP-Hard and generally it is split into two other problems: set covering and crew rostering. This thesis focusses on set covering problem. We give a formal definition, a literature revision and we present two heuristics to solve it a lagrangean and a genetic one. Computational results are also presented to evaluate the performance of the implementedalgorithms.