Uma abordagem heurística para o Multi-Period School Bus Routing Problem

Este artigo propõe uma extensão ao Problema de Roteamento do Ônibus Escolar, que engloba os subproblemas de localização de pontos de paradas de ônibus, alocação de estudantes aos pontos de parada selecionados e roteamento de ônibus envolvendo múltiplos períodos (e.g., dias) e uma única escola. O objetivo consiste em minimizar a distância total percorrida pela frota no conjunto de períodos analisados, atendendo às restrições de capacidade dos veículos e distância máxima que os alunos podem caminhar até as paradas. No contexto do Multi-Period School Bus Routing Problem os estudantes que têm demandas de transporte para (ou de) uma escola em um subconjunto de períodos devem ser alocados à mesma parada nos períodos em que possuem demandas. Primeiramente, é apresentado um modelo matemático para o problema e, em seguida, é proposto um algoritmo baseado nas meta-heurísticas Multi-Start e Variable Neighborhood Descent. O algoritmo proposto foi executado para as 192 instâncias de benchmark, mostrando-se capaz de obter um bom desempenho com um baixo custo computacional.