Grafos emparelhamento

Universidade Federal de Ouro Preto
ICEA – Instituto de Ciências Exatas e aplicadas
Campus de João Monlevade
Curso: Engenharia de Computação

Trabalho de Teoria de Grafos
Resenha apresentada à Disciplina de
Teoria de grafos,
Lecionada pelo professor George H. G. Fonseca,
Pelo aluno:
Fernando Antônio Martins Vieira Júnior
11.2.8090

Julho / 2014
Resenha
O artigo apresenta soluções do Problema da Programação de Tripulações (PPT) focado na geração da de motoristas e cobradores de ônibus urbanos ,que basicamente consiste em determinar o mínimo necessário de tripulações,juntamente com a programação dos veículos.O problema tem alta complexidade devido as restrições das tripulações (trabalhadores) e restrições dentro da própria empresa. Para resolução do problema foi utilizado um modelo de Emparelhamento,que a metodologia proposta consiste em emparelhar as tarefas que apresenta maior similaridade e que podem ser executadas por uma tripulação,sempre respeitando as restrições do problema.Depois do emparelhamento,cada par emparelhado de tarefas é representado por um único nó,devido ao algoritmo de peso máximo.Baseado nisso foram desenvolvidas duas metodologias,chamadas de Metodologia 1: Divisão das tarefas em Períodos e Metodologia 2 : Agrupamento das Tarefas em Blocos de Maior Duração.Na metodologia 1 as tarefas do mesmo período são agrupadas, então o modelo gera soluções com jornadas onde a duração predominante é no próprio periodo.A partir disso é realizado um pré-emparelhamento e as tarefas são agrupadas em um único nó,nós jornadas.E na Metodologia 2 nada mais é que uma variação da primeira em que as tarefas são agrupadas no início e no final das viagens dos veículos com objetivo de atingirem uma duração mínima,depois são aplicamentos emparelhamentos sucessivos até a solução do problema. Os resultados obtidos tiveram soluções satisfatórias nas duas metodologias propostas que atenderam as restrições, e serviram para diminuir