Browsing by Author "Martins, Leandro do Carmo"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Aplicação de um algoritmo genético ao problema de rodízio de tripulações do sistema de transporte público urbano.(2017) Martins, Leandro do Carmo; Silva, Gustavo PeixotoEste trabalho aborda a resolução do Problema de Rodízio de Tripulações (PRT) de empresas do sistema de trans-porte público. O PRT consiste em atribuir uma sequência de jornadas de trabalho aos tripulantes de uma empresa para um dado horizonte de planejamento, com o intuito de minimizar seus custos totais. O custo fixo é dado pelo número de tripulações necessárias para realizar todas as jornadas e os custos variáveis correspondem ao total de horas extras ou ociosas, acumuladas por cada tripulação no período. Na resolução deste problema, são consideradas tanto as restrições operacionais quanto as restrições trabalhistas de uma dada empresa. Neste trabalho, o PRT foi resolvido em duas etapas: a primeira consiste em atribuir os dias de folga, minimizando o número de tripulações. A segunda etapa consiste em alocar as jornadas a serem realizadas, minimizando as horas extras e ociosas no período. As duas etapas foram resolvidas utilizando um Algoritmo Genético ainda não aplicado em casos brasileiros. O algoritmo foi desenvolvido para resolver um caso real e seus resultados foram comparados com a solução exata de um modelo de Programação Linear Inteira, mostrando ser competitivo.Item O uso da heurística Adaptive Large Neighborhood Search para resolver o Problema de Programação de Tripulações do Transporte Público.(2017) Martins, Leandro do Carmo; Silva, Gustavo Peixoto; Silva, Gustavo Peixoto; Freitas, Alan Robert Resende de; Ribeiro, Glaydston Mattos; Ferreira, Anderson AlmeidaEste 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.