O uso da heurística Adaptive Large Neighborhood Search para resolver o Problema de Programação de Tripulações do Transporte Público.
No Thumbnail Available
Date
2017
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Programa 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.
Keywords
Programação heuristica
Citation
MARTINS, 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.