Aluno: Carlo Sulzbach Sartori
Orientadora: Profª. Drª. Luciana Salete Buriol
Título: The Pickup and Delivery Problem with TimeWindows: Algorithms, Instances, and Solutions
Linha de Pesquisa: Algoritmos e Otimização
Data: 15/03/2019
Hora: 10h
Local: Sala 218 no prédio 43412 do Instituto de Informática da UFRGS
Banca Examinadora:
– Prof. Dr. Marcus Rolf Peter Ritt (UFRGS)
– Prof. Dr. Olinto César Bassi de Araújo (UFSM – por videoconferência)
– Prof. Dr. Thibaut Victor Gaston Vidal (PUC-Rio – por videoconferência)
Presidente da Banca: Profª. Drª. Luciana Salete Buriol
Resumo: Neste trabalho, o Problema de Coleta e Entrega com Janelas de Tempo é estudado. Trata-se de um difícil problema de otimização combinatória que generaliza problemas de roteamento de veículos, possuindo aplicações em serviços de entrega e transporte de passageiros. O objetivo é definir o melhor conjunto de rotas de veículos que atendam requisições de transporte entre locais de coleta e entrega, respeitando ao mesmo tempo a capacidade dos veículos e as restrições de tempos de serviço. Para resolver o problema, nós propomos um método híbrido combinando componentes heurísticos da literatura científica com programação matemática — uma técnica geralmente chamada de \textit{matheuristic}. Além disso, uma metodologia para gerar instâncias do problema que são baseadas em dados abertos e tempos de viagem reais é proposta. Um novo conjunto de testes foi gerado baseado nesta proposta. Experimentos computacionais demonstraram que o algoritmo proposto é capaz de obter bons resultados no conjunto padrão de testes da literatura, para o qual novas soluções também foram encontradas. Por outro lado, os resultados para o novo conjunto de instâncias diferem dos observados para o conjunto padrão e demonstram diferenças relevantes entre os dois conjuntos de teste. Uma série de análises e discussões a respeito dos experimentos, principais componentes, e variações do algoritmo híbrido proposto são apresentados.
Palavra-chave: Coleta e entrega. Janelas de tempo. Metaheurística. Programação matemática. Geração de instâncias.