Silva, Gustavo PeixotoMartins, Leandro do Carmo2017-04-172017-04-172017MARTINS, Leandro do Carmo. O uso da heurística Adaptive Large Neighborhood Search para resolver o Problema de Programação de Tripulações do Transporte Público. 2017. Dissertação (Mestrado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2017.http://www.repositorio.ufop.br/handle/123456789/7614Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.Este trabalho propõe o desenvolvimento da heurística Adaptive Large Neighborhood Search (ALNS) para resolver o Problema de Programação de Tripulações (PPT) do Sistema de Transporte Público. O PPT consiste em determinar o número mínimo de tripulações necessário para conduzir todas as viagens previstas na programação dos veículos, definida anteriormente. Os dados de entrada do PPT são as viagens a serem realizadas por cada veículo da frota em operação, definida na etapa anterior, assim como as regras operacionais da empresa, as leis trabalhistas e os acordos vigentes para a categoria. A solução deste problema é um conjunto de sequências de viagens. Cada sequência é uma jornada de trabalho, ou seja, a programação das atividades a serem executadas por uma dada tripulação ao longo de um dia de trabalho. As jornadas devem satisfazer as leis trabalhistas, os acordos sindicais e ainda as regras operacionais da empresa. Como o problema é NP-difícil, casos reais de grande porte são normalmente resolvidos por metaheurísticas. A heurística ALNS tem como objetivo minimizar os custos fixos e variáveis de uma programação completa das tripulações, satisfazendo todas as restrições mencionadas. Os custos fixos são representados pelo número de jornadas (tripulações) e os custos variáveis são calculados em função do total de horas extras e do número de duplas pegadas. A ALNS inicia sua busca a partir de uma solução viável e opera com diferentes métodos de “destruição” e “reparo” da solução corrente para obter uma solução de melhor qualidade. Inicialmente, um peso é atribuído a cada método de destruição e reparo. Estes pesos são ajustados dinamicamente, baseados no desempenho de cada método ao longo da busca, com o intuito de encontrar o par de métodos mais eficiente. Vários métodos diferentes de destruição e reparo tem sido propostos na literatura para resolver o Problema de Roteamento de Veículos. Alguns destes métodos clássicos foram adaptados ao PPT e outros foram propostos pela primeira vez neste trabalho. A heurística foi implementada e testada com dados reais de várias empresas que operam na região metropolitana da cidade de Belo Horizonte, MG. Os parâmetros foram refinados e os resultados obtidos superaram alguns métodos da literatura e a solução adotada pela empresa.pt-BRabertoProgramação heuristicaDissertacaoAutorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 05/04/2017 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais nem a adaptação.