Defesa de Mestrado de Suelaine Gonçalves Andrade; dia 05/09/2013, as 10:00, Sala de Seminários.

Defesa de Mestrado de Suelaine Débora Gonçalves Andrade; dia 05/09/2013, as 10:00, Sala de Seminários no DECOM

Banca: Prof. Dr. Gustavo Peixoto Silva; Prof. Dr. Haroldo Gambini Santos; Prof. Dr. Marco Antônio Moreira de Carvalho; Prof. Dr. José Elias Claudio Arroyo.

Título: Metaheursticas Busca Tabu Para o Problema de Rodzio de Tripulaçõoes de Ônibus Urbanos

Resumo:

O Problema de Rodzio das Tripulaçõoes (PRT) do sistema de transporte publico consiste
em atribuir a cada tripulação uma sequência de jornadas para os dias do horizonte
de planejamento. Como as jornadas diarias tem durações diferentes, as sequências das
jornadas podem resultar em um acumulo de horas extras ou de horas ociosas. Assim o
objetivo do PRT e minimizar as horas extras da escala, compensando-as com ociosidades
entre jornadas. Este e o princpio do banco de horas permitido pela legislação, desde que
sejam respeitadas as restrições operacionais e leis trabalhistas. Neste trabalho o problema
foi resolvido em duas etapas, utilizando diferentes implementações do Algoritmo
de Busca Tabu.
Na primeira etapa e feita a geração da solução inicial atraves de heurística gulosa.
A solução gerada e viavel, no entanto os custos são altos. A segunda etapa utiliza as
jornadas criadas e com base em trocas viaveis tenta diminuir o custo de cada rodzio
com diferentes versões implementadas de Busca Tabu. Foram implementadas 4 versões:
a primeira versão, BTMP, que possui menor tempo da busca local para quando encontra
um vizinho melhor; a segunda, denominada BTMV, em que a busca local e efetuada
sobre toda a vizinhanca; a terceira, BTPV, que utiliza um criterio de porcentagem
variavel para a busca pelo melhor vizinho e a quarta versão BTID, que utiliza criterios
de intensi cação e diversi cação para a Busca Tabu. Ao montar um rodízio, devem ser
consideradas as folgas das tripulações ao longo do perodo. Neste trabalho foi desenvolvido
um modelo em dois cenarios distintos: um que não considera a atribuição das folgas e outro que realiza esta atribuição. Posteriormente os resultados foram comparados
aos obtidos no trabalho de (Prates and Silva 2012) atraves da metaheurstica VNS.
Os resultados mostram que as implementações do modelo desenvolvido se aproveitam
das caractersticas de cada etapa, gerando soluções mais econômicas.

PPGCC - Programa de Pós-Graduação em Ciência da Computação

Departamento de Computação  |  ICEB  |  Universidade Federal de Ouro Preto
Campus Universitário Morro do Cruzeiro  |  CEP 35400-000  |  Ouro Preto - MG, Brasil
Telefone: +55 31 3559-1692  |  secretaria.ppgcc@ufop.edu.br