Mapeamento automático de rotas para vias expressas de ônibus: uma abordagem com algoritmos genéticos com ênfase na cidade de Boa Vista - RR

Resumo

Apesar dos benefícios de uma via expressa de ônibus, o trabalho de engenharia para mapear quais vias devem compor a via expressa é complexo, já que existem exponenciais possibilidades de combinação. Note que computacionalmente falando, uma cidade pode ser vista como um grafo direcionado G e uma via expressa pode ser representada por um subgrafo G', onde G' ⊆ G. Dessa forma, a tarefa de selecionar as vias que irão compor uma via expressa pode ser representada por uma variação do problema do caminho com ciclo de peso máximo, onde esse caminho seria um ciclo conexo com maior quantidade de vias dentro dos parâmetros do grafo da cidade. Nesse sentido, o presente estudo tem o propósito de selecionar rotas que formem ciclos que maximizem o número de vias com alta demanda. Além disso, esse ciclo deve impreterivelmente passar por um terminal de ônibus da cidade, já que esse é o ponto de convergência dos ônibus. Como prova de conceito, optou-se por usar os dados da cidade de Boa Vista - RR. Visto que algoritmos genéticos apresentam alternativas viáveis para problemas de aproximação, optou-se por usar essa técnica para automatizar o processo de seleção e otimização da topologia de rotas para via expressas de ônibus. Os melhores resultados foram atingidos utilizando o algoritmo genético NSGA-II, gerando uma rota que cobre 120 arestas do grafo representado por avenidas da cidade. A convergência do AG foi atingida após 500 gerações. Por fim, destaca-se ainda que o método pode ser generalizado para outros cenários de experimentação, potencialmente sendo aplicado em outros centros urbanos com uma rede de avenidas e pelo menos um terminal de ônibus.