Texto completo
| |
| Autor(es): |
Welverton Rodrigues da Silva
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2019-03-28 |
| Membros da banca: |
Rafael Crivellari Saliba Schouery;
Fábio Luiz Usberti;
Pedro Henrique Del Bianco Hokama
|
| Orientador: | Rafael Crivellari Saliba Schouery |
| Resumo | |
Nesta dissertação abordamos um problema de otimização combinatória motivado por serviços de aluguel de veículos conhecidos por car-sharing. O problema explora a possibilidade de devoluções flexíveis, isto é, permitir que os clientes devolvam os veículos alugados em pátios de estacionamento diferentes daquelas em que os veículos foram retirados. Este problema pode ser descrito da seguinte maneira. Considere dois pátios, denominados por A e B, com cada pátio contendo um conjunto indistinguível de veículos. Dado n clientes, onde cada cliente possui 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 são atendidas. Em um primeiro momento, apresentamos uma formulação de programação linear inteira mista para o problema, bem como 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. Em nossos experimentos computacionais, a formulação sem e com a adição de desigualdades válidas obtiveram em média menos de 1% de gap de otimalidade entre o valor do limitante inferior e o valor do limitante superior -- resultados obtidos sobre instâncias com até 1000 clientes e pelo menos 10 veículos disponíveis em cada pátio, com tempo de execução limitado em 20 minutos por instância. No entanto, o problema abordado mostrou-se ser de difícil resolução por meio dos algoritmos heurísticos propostos. Em nossos experimentos computacionais, para as instâncias de 1000 clientes e 10 veículos disponíveis em cada pátio, os algoritmos heurísticos não conseguiram obter uma solução ótima, onde obtiveram em média 10% de gap de otimalidade entre o valor da solução incumbente e o valor da solução ótima obtida por meio do resolvedor de programação inteira mista utilizado (AU) | |
| Processo FAPESP: | 17/23343-1 - Algoritmos exatos e heurísticas para o compartilhamento de veículos |
| Beneficiário: | Welverton Rodrigues da Silva |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |