Publicação: Algoritmo bioinspirado para roteamento de distribuição de alimentos do produtor aos consumidores finais
Carregando...
Arquivos
Data
Autores
Orientador
Rizol, Paloma Maria Silva Rocha 
Coorientador
Ribeiro, Vitor Pinto
Pós-graduação
Curso de graduação
Guaratinguetá - FEG - Engenharia Elétrica
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Estadual Paulista (Unesp)
Tipo
Trabalho de conclusão de curso
Direito de acesso
Acesso aberto
Resumo
Resumo (português)
As commodities são produtos de suma importância para a economia brasileira e então é necessário que as logísticas desses produtos primários utilizem os trajetos mais eficientes desde o produtor até os consumidores finais. Além disso, é importante que haja uma redução na emissão de gases poluentes, já que, no Brasil, os caminhões são responsáveis por grande parte do transporte das commodities e emitem uma grande quantidade de gases poluentes. Uma rota ótima seria aquela que há um menor tempo para chegar de um lugar a outro e, consequentemente, possui a menor emissão de gases poluentes.
Neste trabalho de graduação será desenvolvido um algoritmo bioinspirado que encontre as melhores rotas partindo de um único ponto representando o produtor até os diferentes locais de chegada que seriam os mercados e, para isso, será utilizado um grafo não direcionado e georreferenciado para representar a malha viária a ser seguida. Um grafo é representado por vértices que são conectados por arestas que podem ter direção ou não, sendo uma possível aplicação do grafo a representação de um mapa geográfico.
O problema de roteamento consiste em encontrar a rota ótima entre dois nós diferentes, sendo ela definida como a menor soma dos comprimentos de cada uma das arestas que estão entre o ponto de partida e o de chegada. O algoritmo de Dijkstra é usado para calcular os menores caminhos de um ponto inicial e todos os outros restantes a partir de um grafo não direcionado, sendo este algoritmo o mais utilizado em problemas de roteamento.
O algoritmo bioinspirado denominado Physarum solver foi desenvolvido com o objetivo de identificar a rota ótima entre dois pontos distintos em um grafo não direcionado. Neste trabalho de graduação utilizou-se o grafo não direcionado para simplificar a representação de uma localização geográfica e diminuir o tempo de execução do algoritmo. Além disso, o algoritmo bioinspirado desenvolvido neste trabalho oferece uma abordagem diferente do algoritmo de Dijkstra, pois permite encontrar rotas ótimas de um ponto de partida para múltiplas saídas, enquanto o Dijkstra se concentra em rotas de entrada e saída única.
Para aplicar o Physarum solver partindo de um ponto para outros destinos finais, foi necessário modificar o algoritmo original. Para realizar a aplicação final na cidade de Guaratinguetá - SP, utilizou-se outros dois exemplos de localizações com áreas menores, sendo eles um bairro na cidade de São Paulo chamado Vila Esperança e a cidade de Iracemápolis - SP.
Uma vez que tentativas e correções foram feitas, comparou-se o desempenho do Physarum solver com o algoritmo de Dijkstra e, mesmo com o tempo do algoritmo bioinspirado sendo muito maior, as rotas obtidas para ambos os algoritmos foram idênticas. A partir desta comparação, foram realizadas diferentes aplicações do Physarum solver no bairro Vila Esperança localizado na cidade de São Paulo e em Iracemápolis - SP utilizando rotas já validadas pelo algoritmo de Dijkstra para encontrar a rota ótima entre um ponto para diferentes locais. Após essas execuções, aplicou-se o Physarum solver para a cidade de Guaratinguetá - SP resultando as rotas ótimas.
Resumo (inglês)
Commodities are products of utmost importance for the Brazilian economy, and therefore it is essential that the logistics of these primary products use the most efficient routes from the producer to the final consumers. Additionally, it is important to reduce pollutant gas emissions, as in Brazil, trucks are responsible for a significant part of commodities transport and emit a large amount of pollutant gases. An optimal route would be one with the shortest time to travel from one place to another and, consequently, the lowest emission of pollutant gases.
In this undergraduate project, a bio-inspired algorithm will be developed to find the best routes from a single point representing the producer to various destination points representing the markets. For this, an undirected and georeferenced graph will be used to represent the road network to be followed. A graph is represented by vertices connected by edges, which may or may not have direction, and one possible application of the graph is the representation of a geographic map.
The routing problem consists of finding the optimal route between two different nodes, defined as the shortest sum of the lengths of each of the edges between the starting and ending points. Dijkstra's algorithm is used to compute the shortest paths from an initial point to all remaining points in an undirected graph, being the most widely used algorithm in routing problems.
The bio-inspired algorithm known as the Physarum solver was developed to identify the optimal route between two distinct points in an undirected graph. In this undergraduate project, the undirected graph was used to simplify the representation of a geographical location and reduce the algorithm's runtime. Additionally, the bio-inspired algorithm developed in this work offers a different approach from Dijkstra's algorithm, as it allows for finding optimal routes from a starting point to multiple exits, while Dijkstra focuses on single-source to single-destination routes.
To apply the Physarum solver from one point to multiple final destinations, it was necessary to modify the original algorithm. For the final application in the city of Guaratinguetá - SP, two other examples of locations with smaller areas were used, namely a neighborhood in the city of São Paulo called Vila Esperança and the city of Iracemápolis located in the state of São Paulo.
After some experiments and some fine-tuning, the performance of the Physarum solver was compared with Dijkstra's Algorithm. Despite the much longer runtime of the bio-inspired algorithm, the routes obtained for both algorithms were identical. Based on this comparison, various applications of the Physarum solver were carried out in the neighborhood of Vila Esperança and in the city of Iracemápolis, using routes already validated by Dijkstra's Algorithm to find the optimal route from one point to different locations. After executing the algorithm for these use cases, the Physarum solver was applied to the city of Guaratinguetá - SP, resulting in the optimal routes.
Descrição
Palavras-chave
Algoritmo bioinspirado, Bioinspired algorithm, Physarum polycephalum, Physarum solver, Algoritmos, Logística, Grafos - Teoria dos
Idioma
Português
Como citar
OTA, Fernando Jun. Algoritmo bioinspirado para roteamento de distribuição de alimentos do produtor aos consumidores finais. Orientadores: Paloma Maria Silva Rocha Rizol; Vitor Pinto Ribeiro. 2024. 48 f. Trabalho de Conclusão de Curso (Graduação em Engenharia Elétrica) - Faculdade de Engenharia e Ciências, Universidade Estadual Paulista, Guaratinguetá, 2024.
