Modelos e heurísticas para os problemas de programação de veículos e de tripulações no sistema de transporte público.

Abstract

Este trabalho aborda dois problemas comumente presentes no sistema de transporte público brasileiro: (i) o Problema de Programação de Veículos (PPV), que trata da atribuição de um conjunto de viagens programadas a um conjunto de veículos, e (ii) o Problema de Programação de Tripulação (PPT), que consiste em agrupar as viagens em jornadas de trabalho que serão atribuídas aos tripulantes. O objetivo central deste trabalho é avaliar modelos matemáticos e heurísticas para estes problemas, com o objetivo de minimizar a quantidade de veículos e de tripulantes necessários para atendimento às demandas de algumas empresas de ônibus da região metropolitana de Belo Horizonte. Para tratar o PPV é utilizado um modelo de fluxo em redes, capaz de rapidamente resolver o problema. O PPT, por outro lado, reconhecido pela sua dificuldade de resolução, é modelado como um problema de particionamento de conjuntos. Uma estratégia de geração de colunas envolvendo heurísticas para resolução do problema de pricing é empregada para resolver a relaxação linear do problema. A partir do modelo resultante, uma heurística de recobrimento é utilizada para obter soluções inteiras. Experimentos computacionais demonstram a qualidade dos limites inferiores obtidos com a relaxação linear, bem como o potencial da heurística de recobrimento utilizada. Soluções com gap de otimalidade inferior a cinco porcento foram geradas para a maioria das instâncias consideradas. Por fim, os resultados obtidos são comparados com resultados da literatura, evidenciando a qualidade das abordagens proposta.