Modelos e algoritmos para o problema de alocação de tripulação em redes de transporte
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Henrique Pacca L. Luna
Mauricio Cardoso de Souza
Mauricio Cardoso de Souza
Resumo
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.
Abstract
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.
Assunto
Administração do tempo, Computação, Algoritmos geneticos, Produção de horário
Palavras-chave
redes de transporte