“Inteligência Artificial: A Nova Fronteira da Ciência Brasileira”
19 a 24 de outubro de 2020
Trabalho 13790
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Ciência da computação |
| Setor | Departamento de Informática |
| Bolsa | PIBIC/CNPq |
| Conclusão de bolsa | Sim |
| Apoio financeiro | CNPq |
| Primeiro autor | Natan Seabra Garcias |
| Orientador | ANDRE GUSTAVO DOS SANTOS |
| Título | Reposicionamento de veículos em sistemas de Free Floating Carsharing |
| Resumo | O compartilhamento de veículos tem se tornado um serviço cada vez mais presente no mundo. Por meio de aplicativos, as pessoas podem alugar um veículo que esteja próximo dela e deixá-lo em qualquer ponto da cidade. Tal serviço oferece acesso a flexibilidade que um carro pode ter e evita a aquisição deste e todos os fardos que o acompanham, gerando assim, economia de tempo e dinheiro para os usuários que o utilizam no dia a dia. No entanto, esta possibilidade de aluguel torna necessária a reposição desses veículos utilizados para pontos na cidade que têm demanda da população. Para isso, as empresas utilizam vans que transportam motoristas, estes que têm o objetivo de realocar esses veículos em um certo período de tempo. Calcular a melhor rota para essas vans e determinar quais veículos serão reposicionados pelos motoristas se torna necessário, visto que, a partir que um tempo limite é estabelecido, é preciso reposicionar os veículos certos para os lugares certos para se conseguir atender um número maior de pessoas. Entretanto, devido ao grande número de possibilidades disponíveis para realizar esses reposicionamentos dentro do tempo limite, torna-se inviável a aplicação de um algoritmo exato para resolver o problema. Assim, a partir de um modelo matemático criado pelo orientador do projeto, foi realizado o trabalho de adaptar e aprimorar este modelo para que fosse possível a utilização de um solver para encontrar a solução do problema. Porém, por se tratar de um problema de otimização combinatória, a utilização de um solver demanda grande esforço computacional e um intervalo de tempo demasiado. Com isso, no decorrer do projeto de Iniciação Científica, trabalhou-se na aplicação de técnicas de otimização matemática, heurísticas e meta-heurísticas para se obter um bom desempenho computacional e foi desenvolvido um algoritmo eficiente e robusto capaz de determinar uma boa rota que se aproxima da ideal com baixo tempo de processamento. Ademais, também foi adaptada a solução do algoritmo para o solver, podendo assim, combinar a utilização dos dois para obter melhores resultados. O algoritmo foi testado sobre um conjunto de dados representados por veículos espalhados na cidade, e com pontos que representam lugares na cidade que havia demanda. Nessa fase, se comparados os resultados do algoritmo com o solver, o algoritmo encontrou rotas melhores avaliadas em 27 das 30 instâncias disponíveis, sendo que em duas delas o resultado encontrado obteve a mesma avaliação, ressaltando ainda, que o tempo médio gasto pelo algoritmo foi cerca de 400 vezes menor que o do solver. Desse modo, baseado nos resultados do algoritmos e do solver, conclui-se que a adaptação do modelo foi um sucesso e que a aplicação de heurísticas e metaheurísticas podem nos levar a boas soluções para este problema, contribuindo para áreas como aluguel de veículos. |
| Palavras-chave | Otimização, roteamento de veículos, metaheurísticas |
| Forma de apresentação..... | Vídeo |
| Link para apresentação | Vídeo |
|---|