10 jul 2023
14:30 Defesa de Doutorado Auditório do IC3
Tema
Problema de Compartilhamento Veículos Elétricos: Complexidade, Modelos e Algoritmos
Aluno
Welverton Rodrigues da Silva
Orientador / Docente
Rafael Crivellari Saliba Schouery - Coorientador: Fábio Luiz Usberti
Breve resumo
O problema de compartilhamento de veículos elétricos (EVSP) é um novo e desafiador problema de otimização combinatória motivado por sistemas de compartilhamento de carros elétricos baseado em reservas na modalidade one-way, para estações de origem e destino. O EVSP visa encontrar o tempo total máximo de locação em que as demandas dos clientes são atribuídas à frota existente. No EVSP, ou todas as demandas do cliente são totalmente atendidas, ou o cliente não utiliza o sistema. Mostramos que o EVSP é fortemente NP-difícil e que é NP-difícil aproximar em um fator de n^{1−ϵ} em tempo polinomial, para qualquer ϵ > 0, onde n denota o número de clientes, a menos que P = NP. Para resolver o EVSP, propomos diferentes formulações de programação linear inteira mista, com modelagem baseadas em redes de espaço-tempo homogêneas e heterogêneas, fluxo de energia, e fluxo misto de duas camadas — juntamente com alguns resultados teóricos e etapas de pré-processamento. Também propomos um algoritmo exato baseado em uma estratégia de fixação de variáveis utilizando o custo reduzido, heurística baseada em uma estratégia de relax-and-fix (incluindo uma estratégia de decomposição) e uma mateurística baseada em uma estratégia de decomposição que gera iterativamente soluções melhoradas. Um estudo computacional abrangente do comportamento das abordagens propostas é realizado usando benchmarks com base em dados reais de um sistema de compartilhamento de carros elétricos localizado em Fortaleza, Brasil. A maior parte de nossos experimentos computacionais mostrou a eficácia das metodologias propostas na obtenção de soluções ótimas ou quase ótimas para muitas instâncias grandes. Também avaliamos os méritos de cada decisão metodológica no que diz respeito às suas contribuições para a melhoria da qualidade das soluções.
Banca examinadora
Titulares:
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |
| Mariá Cristina Vasconcelos Nascimento | ITA |
| Franklina Maria Bragion Toledo | ICMC/USP |
| Cristiano Torezzan | FCA/UNICAMP |
| Marcos Medeiros Raimundo | IC/UNICAMP |
Suplentes:
| Orlando Lee | IC/UNICAMP |
| Santiago Valdés Ravelo | INF/UFRGS |
| Pedro Henrique del Bianco Hokama | IMC/UNIFEI |