Português English
Contato

Dissertação de Carlo Sulzbach Sartori


Detalhes do Evento


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.