Resolução do problema de programação de ônibus urbano utilizando a metaeurística LNS.

Abstract

O transporte público é um sistema amplamente utilizado pela população, principalmente por aqueles que residem nos grandes perímetros urbanos. Como esse sistema tem um grande impacto no dia-a-dia de milhões de pessoas, ele precisa estar em constante melhora. Uma das etapas da operação do sistema de transporte público é a programação dos veículos que irão realizar as viagens previstas na tabela de horários. Esta alocação pode ser realizada de forma manual pelas empresas, entretanto, o uso de métodos de otimização pode implicar num melhor aproveitamento da frota e uma consequente redução nos custos das empresas. Com base nesse cenário, neste trabalho foi desenvolvida uma versão da heurística Large Neighborhood Search (LNS) para resolver o Problema de Programação de Veículos (PPV). Ao solucionar o PPV, pretende-se definir a quantidade mínima de veículos em operação, assim como o detalhamento das atividades de cada veículo em operação. Este detalhamento especifica quais as viagens serão realizadas por quais veículos, o tempo de espera nos terminais e as possíveis viagens ociosas realizadas. A solução para o problema foi construída inicialmente com a busca gulosa, posteriormente foram adaptados métodos de remoção e inserção das viagens aos veículos e finalmente foi implementada a heurística LNS. Foram realizados testes computacionais com dados reais de uma série de empresas que operam na região metropolitana de Belo Horizonte, MG. Os resultados foram comparados com aqueles obtidos por um modelo exato baseado em Algoritmos de Fluxo em Redes. Os resultados se mostraram promissores, visto que na maioria dos casos a diferença entre a solução aproximada e a solução ótima foi pequena.