Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do Simpósio Brasileiro de Pesquisa Operacional

Este artigo aborda uma variante do Problema de Roteamento de Ônibus Escolares, que envolve decisões relacionadas à localização de paradas de ônibus, atribuição de estudantes às paradas e roteamento dos ônibus. O objetivo consiste em minimizar o custo total de roteamento para pegar estudantes e entregá-los a uma escola, satisfazendo a capacidade do veículo e a distâncias máxima que estudantes podem caminhar de sua casa até as paradas de ônibus. Para resolver o problema, foi proposto um algoritmo híbrido que combina uma metaheurística Iterated Local Search (ILS) com uma formulação de programação linear inteira (PLI). Em particular, o ILS faz uso de diversas vizinhanças e estruturas de dados auxiliares para explorar eficientemente o espaço de busca de solução. O algoritmo proposto foi avaliado ao resolver 95 instâncias de benchmark, e mostrou ser capaz de obter soluções de alta qualidade, 10 das quais são melhores do que as melhores encontradas na literatura.