Defesa de Mestrado de Welverton Rodrigues da Silva

Título do Trabalho
Algoritmos Exatos e Heurísticos para um Problema de Compartilhamento de Veículos
Candidato(a)
Welverton Rodrigues da Silva
Nível
Mestrado
Data
Add to Calender 2019-03-28 00:00:00 2019-03-28 00:00:00 Defesa de Mestrado de Welverton Rodrigues da Silva Algoritmos Exatos e Heurísticos para um Problema de Compartilhamento de Veículos Sala 85 IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
10:00
Local
Sala 85 IC 2
Orientador(a)
Rafael Crivellari Saliba Schouery
Banca Examinadora

* Titulares

Unidade/Instituição

Rafael Crivellari Saliba Schouery

IC/UNICAMP

Pedro Henrique Del Bianco Hokama

IMC/UNIFEI

Fábio Luiz Usberti

IC/UNICAMP

 

* Suplentes

Unidade/Instituição

Lehilton Lelis Chaves Pedrosa

IC/UNICAMP

Mário César San Felice

DC/UFSCar

Resumo

Nesta dissertação abordamos um problema de otimização combinatória motivado por serviços de aluguéis de veículos conhecidos por car-sharing. Este problema explora a possibilidade das devoluções dos veículos alugados serem em pátios de estacionamento diferentes daquelas em que os veículos foram retirados. O problema pode ser descrito da seguinte maneira. Considere dois pátios de estacionamentos, denominados por A e B, com um conjunto indistinguível de veículos. Dado n clientes, onde cada cliente tem exatamente duas demandas em direções opostas, uma demanda de A para B e outra de B para A, mas não necessariamente nesta ordem. Cada demanda especifica o intervalo de tempo em que o veículo será utilizado. O objetivo do problema é encontrar um escalonamento dos veículos aos clientes que maximiza o número de clientes satisfeitos. Um cliente está satisfeito se e somente se ambas as suas demandas puderem ser atendidas. Primeiramente apresentamos uma formulação de programação linear inteira mista e a adição de desigualdades válidas à formulação. Em seguida, descrevemos algoritmos heurísticos baseados nas meta-heurísticas GRASP, VNS, Busca Tabu e BRKGA. Uma série de experimentos computacionais foram conduzidos para comparar as metodologias propostas. A formulação proposta foi capaz de resolver até a otimalidade a maioria das instâncias de até 1000 clientes, em menos de 20 minutos. Os resultados obtidos com a formulação apresentaram gap de otimalidade menor que 1%. Entretanto, demonstrou-se ter dificuldade para convergir (aproximar cada vez mais) os limitantes superior e inferior, em várias instâncias testadas. Os algoritmos heurísticos por sua vez, são ineficientes para se obter soluções ótimas, dada a dificuldade das heurísticas em obter soluções viáveis a partir de outra solução, utilizando-se estruturas de vizinhanças.