Modelagem matemática e algoritmos heurísticos para o problema de roteamento de ônibus escolares envolvendo múltiplos períodos

Abstract

Esta dissertação aborda uma extensão do School Bus Routing Problem (SBRP), 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, recentemente introduzido na literatura por Melo e Kramer (2021). 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 (MP-SBRP), 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 Iterated Local Search (ILS) e Variable Neighborhood Descent (VND), além de heurísticas de inserção e remoção de paradas considerando os múltiplos períodos, denominado de Iterated Local Search with Randomized Variable Neighborhood Descent and Remove (ILS-RVND-R). O algoritmo proposto foi executado para 95 instâncias do SBRP, propostas por Schittekat et al. (2013), e para 192 instâncias do MP-SBRP obtidas através de uma extensão das instâncias de Schittekat et al. (2013), mostrando-se capaz de obter um desempenho favorável e com um baixo custo computacional para ambos os problemas.