“Bicentenário da Independência: 200 anos de ciência, tecnologia e inovação no Brasil e 96 anos de contribuição da UFV”.
8 a 10 de novembro de 2022
Trabalho 16645
| 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 | Não |
| Apoio financeiro | CNPq |
| Primeiro autor | Davi de Paula Oliveira |
| Orientador | ANDRE GUSTAVO DOS SANTOS |
| Título | Uso de entregadores ocasionais na última milha das entregas |
| Resumo | Compras por e-commerce movimentaram mais de U$500 bilhões em 2019, com um crescimento estimado nos EUA de 31% até 2023. Mas, com a pandemia, as compras aumentaram muito mais que isso, não só nos EUA. Isto aumenta enormemente o número de veículos que fazem a entrega, que já contribuíam com 16 a 50% da emissão de poluentes em áreas urbanas, demandando uma alternativa urgente. A literatura científica recente contém diversas propostas e estudos de crowdsourcing, em que os próprios clientes fazem a entrega a outros clientes. Os problemas deste projeto de pesquisa são de grande interesse prático, visto o uso de crowdsourcing pode reduzir consideravelmente a quantidade de veículos em circulação, diminuindo tráfego e emissão de poluentes e também de interesse teórico, pela dificuldade computacional, dado o volume de dados, estocásticos e dinâmicos, exigindo adaptações das heurísticas e métodos existentes para uma resposta rápida. O contexto é então o de entrega de produtos comprados on-line por entregadores ocasionais (OCs - ocasional courriers), clientes da própria empresa que decidem ir à loja/depósito. Produtos não entregues por OCs devem ser entregues por uma frota profissional (PF), veículos da empresa para entrega porta-a-porta. Portanto, o objetivo do projeto é, dado um conjunto de entregas a serem feitas para os clientes e um conjunto de OCs, decidir as entregas por OCs para minimizar o custo esperado de entregas da empresa, ou seja, a soma do valor total gasto com os OCs com o valor total gasto com a PF. Para determinar quais clientes terão seus produtos entregues por OCs e quais terão pela PF, foi utilizada a Pesquisa de Árvore de Monte Carlo (MCTS - Monte Carlo Tree Search). MCTS é um algoritmo de busca baseado em heurística e probabilidade que combina a implementação de uma busca em árvore com os princípios de aprendizado por reforço. Como já havia na literatura uma heurística que procurava resolver o mesmo problema proposto pelo projeto, após a implementação do MCTS, foi feita uma comparação dos dois algoritmos. Comparando os resultados, foi possível concluir que o MCTS foi um pouco pior em relação à qualidade da solução, porém ele conseguiu ser mais rápido que a heurística. Nesse contexto, é primordial ter uma decisão rápida, vantagem do MCTS. Porém, por mais que o MCTS tenha funcionado bem para este problema, é preciso considerar dois pontos: não foram utilizadas instâncias reais; e foi considerado que todos os clientes e OCs são conhecidos de antemão. Todavia, no mundo real os OCs aparecem ao longo do dia, ou seja, eles não são conhecidos de antemão. Portanto, a etapa atual e futura do projeto é, dado um conjunto de entregas para os clientes e um histórico de valores oferecidos para os OCs, implementar um algoritmo que determina o valor e o cliente ideal para cada OC que chegar à loja de forma que, simultaneamente, os custos sejam minimizados e a probabilidade dele aceitar seja alta. |
| Palavras-chave | Entrega de Última Milha, Roteamento de Veículos, Pesquisa de Árvore de Monte Carlo |
| Forma de apresentação..... | Vídeo |
| Link para apresentação | Vídeo |
|---|