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

• Ano de defesa: 2022
• Autor(a) principal: MELO, Igor Eduardo Santos de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Pernambuco; UFPE; Brasil; Programa de Pos Graduacao em Engenharia de Producao
• Palavras-chave em Português: Engenharia de produção; Multi-Period School Bus Routing Problem; Seleção das paradas de ônibus; Geração das rotas; Algoritmo heuristico
• Link de acesso: https://repositorio.ufpe.br/handle/123456789/45020

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.