Defesa de mestrado do discente André Luyde Souza, dia 12/06/19, as 10:00, Sala de Seminários - DECOM

Defesa de mestrado do discente André Luyde da Silva Souza, dia 12/06/2019, as 10:00 na Sala de Seminários do DECOM - ICEB III.
Orientador: Puca Huachi Vaz Penna
Coorientador: Marcone Jamilson Freitas Souza
Título: Algoritmos meta-heurísticos para o Problema Dial-a-Ride
Resumo:
Este trabalho trata do problema Dial-a-Ride, que consiste em fazer rotas para veículos com a finalidade de transportar pacientes de diferentes locais para realizar exames médicos em unidades de tratamento de saúde. O Dial-a-Ride é uma extensão do Problema de Roteamento de Veículos, possuindo características do Problema de Roteamento de Veículos com Janela de Tempo e do Problema de Roteamento de Veículos com Coleta e Entrega, combinados com restrições relativas aos pacientes. O trabalho considera a forma estática do problema e utiliza dados obtidos da Prefeitura Municipal de Ouro Preto-MG para modelagem e contextualização do problema. Para resolvê-lo, propõe-se dois algoritmos meta-heurísticos, um baseado em Iterated Local Search (ILS) e outro baseado em Variable Neighborhood Search. Ambos têm como método de busca local o procedimento heurístico Randomized Variable Neighborhood Descent (RVND), o qual usa os movimentos de realocação, troca e cruzamento para explorar o espaço de soluções do problema. Os resultados computacionais foram obtidos pela aplicação dos algoritmos em um conjunto de instâncias da literatura e comparados com os das melhores soluções desta variante do problema. Apesar de simples, os algoritmos desenvolvidos foram capazes de encontrar a solução ótima para algumas instâncias e soluções de boa qualidade para as demais. Os algoritmos também foram testados em um conjunto de instâncias criadas a partir de dados fornecidos pela Prefeitura Municipal de Ouro Preto-MG. Ambos se mostraram capazes de atender as demandas da cidade de Ouro Preto de forma automatizada, proporcionando ao setor de transporte da prefeitura uma ferramenta que possibilita reduzir os custos com o transporte de pacientes e diminuir a alocação de funcionários para cumprir essa atividade.