"Ciências Básicas para o Desenvolvimento Sustentável"
24 a 26 de outubro de 2023
Trabalho 18992
| 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 | FAPEMIG |
| Conclusão de bolsa | Sim |
| Apoio financeiro | FAPEMIG |
| Primeiro autor | Maria Victória Fernandes Vaz |
| Orientador | JOSE ELIAS CLAUDIO ARROYO |
| Título | Aplicação de Algoritmos Heurísticos para Distribuição de Entregas utilizando Caminhão e Drones |
| Resumo | O Problema do Caixeiro Viajante (Traveling Salesman Problem-TSP) é um dos problemas clássicos de Otimização Combinatória, cuja obtenção da solução ótima costuma ser um processo complexo (problema NP-difícil). Atualmente, existem muitas aplicações modernas do TSP, porém de forma mais incrementada e complexa. Uma das aplicações é a utilização veículos terrestres (caminhões) e drones para entregas de última milha em operações logísticas Neste trabalho aborda-se o Problema do Caixeiro Viajante com Drones Paralelos (Parallel Drone Scheduling Traveling Salesman Problem -PDSTSP), onde um caminhão e um ou mais drones, partido de um mesmo centro de distribuição, precisam realizar entregas a um conjunto de clientes de forma a minimizar o tempo máximo de atendimento (makespan). Neste problema, a elegibilidade dos clientes é considerada. Como os drones são alimentados por baterias, eles são restritos, tanto na distância máxima de viagem quanto no tamanho e peso da encomenda a ser transportada. Clientes elegíveis são aqueles que podem receber suas entregas por meio de drones e clientes não-elegíveis são aqueles cujas entregas necessitam de atendimento do veículo terrestre. Para resolver o problema abordado, métodos baseados em heurísticas e meta-heurísticas são propostos. Através de uma heurística gulosa, constrói-se uma rota TSP inicial de distribuição alocando todos os clientes para o caminhão, criando assim uma Rota Gigante (RG). Com o objetivo de melhorar a RG, aplica-se uma heurística de busca local denominada RVND (Random Variable Neighborhood Descent). Esta heurística utiliza 4 estruturas de vizinhança para fazer a busca de soluções. A partir da RG, aplica-se outra heurística construtiva para fazer a separação dos clientes: determina-se os clientes a serem atendidos pelo caminhão (rota TSP) e os clientes a serem atendidos pelos drones. Em seguida aplica-se a meta-heurística GRASP (Greedy Randomized Adaptive Search Procedure), que também utiliza a busca loca RVND. Assim, o algoritmo desenvolvido é denominado GRASP-RVND. O algoritmo GRASP-RVND é executado durante um número iterações. A cada iteração, constrói-se uma solução viável para o problema e esta solução é melhorada pelo RVND. No final, considera-se a melhor solução obtida durante todas as iterações. Diversos experimentos computacionais foram realizados e foi possível observar que o algoritmo proposto, GRASP-RVND, é bastante competitivo com os algoritmos da literatura. Ressalta-se que, na literatura não foram encontradas propostas do algoritmo híbrido GRASP-RVND para o problema em estudo. |
| Palavras-chave | Heurísticas, Drones, Otimização |
| Forma de apresentação..... | Painel |
| Link para apresentação | Painel |
|---|