Aplicação da Meta-Heurística ILS no planejamento do transporte escolar intermunicipal na cidade de Itabirito - MG.

Abstract

A Prefeitura de Itabirito disponibiliza transporte gratuito, nos turnos da manhã e noite, para os residentes da cidade que estão matriculados em instituições de ensino localizadas em cidades vizinhas, com destaque para Belo Horizonte, destino que será tratado neste trabalho. O principal desafio enfrentado pela Secretaria Municipal de Transportes é a definição das rotas, levando em consideração as restrições que envolvem instituições de ensino com demandas que excedem a capacidade dos veículos disponíveis e as limitações relacionadas ao tempo de chegada dos alunos devido à grade de horários das aulas. Essas restrições classificam o problema como um "Problema de Roteamento de Veículos com Entrega Fracionada e Janela de Tempo" (PRVEFJT). Dada a complexidade desse problema, que é classificado como NP-difícil, este estudo propõe abordagens para resolver o PRVEFJT por meio da meta-heurística denominada "Iterated Local Search" (ILS). A avaliação do desempenho do algoritmo é conduzida através do uso de cinco pequenas instâncias geradas de maneira aleatória, com auxílio da biblioteca “random” da linguagem de programação Python. São comparados os resultados do algoritmo ILS e do método exato para essas instâncias. A análise do "gap" entre as soluções ótimas e as soluções geradas pelo algoritmo ILS revela que o algoritmo demonstra competitividade em relação ao método exato, exibindo resultados que se aproximam das soluções ideais, ao mesmo tempo em que mantém um baixo tempo de execução. Com base nesses resultados, o algoritmo é aplicado à situação real do problema, gerando soluções que consistem em 15 rotas no período da manhã (totalizando 1910 km percorridos) e 23 rotas no período noturno (totalizando 2822 km percorridos).