Algoritmos exatos e heurísticas para o compartilhamento de veículos

• Processo: 17/23343-1
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de abril de 2018
• Data de Término da vigência: 31 de março de 2019
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Acordo de Cooperação: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
• Pesquisador responsável: Rafael Crivellari Saliba Schouery
• Beneficiário: Welverton Rodrigues da Silva
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Vinculado ao auxílio: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural, AP.TEM
• Assunto(s): Otimização combinatória Algoritmos Heurística
• Palavra(s)-Chave do Pesquisador: Algoritmos Exatos | Compartilhamento de veículos | heuristicas | Otimização Combinatória | Algoritmos

Resumo

Neste projeto de pesquisa é abordado um problema de otimização combinatória que surge no compartilhamento de veículos (car-sharing). O problema de compartilhamento de veículos, como é chamado, fundamenta-se na seleção de um conjunto de demandas por locação de veículos com devoluções flexíveis de modo a satisfazer o maior número possível de clientes. Neste texto, as devoluções são ditas flexíveis pois os clientes podem deixar os veículos em pátios, i.e., estacionamentos da empresa locadora, diferentes de onde foram retirados. Além disso, um cliente é dito satisfeito se todas as suas demandas por locação são atendidas. Em particular, o compartilhamento de veículos elétricos tem aplicações na mobilidade sustentável em centros urbanos, levando a benefícios econômicos e ecológicos. Além do mais, este problema é relevante também para a Ciência da Computação e Pesquisa Operacional por ser um problema NP-difícil mesmo quando há dois pátios e cada cliente possui duas demandas para a locação de veículos. Apesar disso, até o momento existem apenas estudos teóricos para o mesmo. Por isto, este projeto propõe o desenvolvimento e implementação de algoritmos, tanto exatos quanto heurísticos, e a análise empírica destes algoritmos em instâncias reais ou geradas aleatoriamente para que instâncias do problema possam ser resolvidas rapidamente na prática. (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

SILVA, Welverton Rodrigues da. Algoritmos exatos e heurísticos para um problema de compartilhamento de veículos. 2019. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.