Otimização da escala de motoristas do transporte público : uma abordagem de geração de colunas.

Abstract

Técnica de Geração de Colunas é comumente empregada na solução do Problema de Progra- mação de Tripulações (PPT), que visa encontrar o número mínimo de motoristas necessário para cobrir todas as viagens previstas na tabela de horários de uma empresa de transporte pú- blico. O objetivo central deste trabalho é modelar o PPT como um problema de particionamento de conjuntos em conformidade com as necessidades e restrições das empresas de ônibus, e resolvê-lo partindo de um conjunto pré-compilado razoavelmente grande de jornadas potenciais (chamado de shift-pool) com conhecimento específico do problema. O algoritmo de geração de colunas descrito neste trabalho decompõe esse problema em um problema mestre e uma série de subproblemas de pricing. O problema mestre seleciona as melhores jornadas a partir de um conjunto de jornadas conhecidas, selecionadas do shift-pool, enquanto o subproblema de pricing amplia o conjunto de jornadas viáveis para aprimorar a solução obtida no problema mestre. O algoritmo proposto foi então testado com dados reais provenientes de empresas de ônibus que operam na região metropolitana de Belo Horizonte, concluindo que o modelo proposto, com o uso de geração de colunas e um shift-pool otimizado, reduziu de forma eficiente o número de jornadas necessárias, atendendo às restrições legais e operacionais e produzindo escalas de trabalho ajustadas e econômicas para as empresas locais.