Grafos Dirigidos e Aplicações em Sistemas de Roteamento - Otimização de Rotas e SIG

Uma aplicação de grafos dirigidos Para que uma viagem seja eficiente é necessário que o motorista saiba o melhor caminho a se seguir esse motorista pode escolher uma variedade de rotas dependendo de sua necessidade Com esse cenário surgem algumas soluções para suprir essas demandas Dentre elas destacamse os sistemas de navegação como o GPS global positioning system e serviços de localização de endereço e de roteirização como o Google Maps Nesse contexto 1 o mapa é representado como um grafo dirigido onde cada interseção de ruas é um nó e cada trecho de rua entre as interseções é uma aresta dirigida que liga dois nós Todas as pessoas que lidam com sistemas de rotas informatizado estão fazendo uso de Sistema de Informação Geográficas SIG Um SIG pode ser aplicado por exemplo para o planejamento urbano de um município De acordo com 1 uma vez que isso pode evitar congestionamento e fornecer a melhor rota para quem está dirigindo dentro de uma cidade ou até mesmo em rodovias que não conhece No entanto à medida que aumenta o número de cidades ou a complexidade das rotas encontrar a solução ótima se torna um desafio É aí que entra o cálculo de melhor rota com grafos dirigidos Um grafo dirigido é uma representação visual de um conjunto de conexões direcionais entre pontos ou nós No contexto de rotas esses nós são as cidades e as conexões são as estradas que as ligam Cada conexão tem um peso associado que pode representar a distância entre as cidades o tempo de viagem ou qualquer outra métrica relevante para isso consulte 2 3 Figura 1 Representação do grafo associado ao mapa do Brasil Fonte 3 1autora1email 2autora2email 3autor3email 2 O cálculo de melhor rota com grafos dirigidos usa algoritmos para encontrar a rota mais eficiente entre duas cidades em um grafo Existem várias abordagens para isso incluindo o algoritmo de Dijkstra o algoritmo de BellmanFord e o algoritmo A Cada um desses algoritmos tem suas próprias vantagens e desvantagens mas todos são projetados para encontrar a solução ótima para o problema de melhor rota Em tempos em que tudo depende de um tempo mínimo para realizar uma atividade percebe se uma grande necessidade de um sistema que possa auxiliar o motorista a escolher a melhor rota em tempo real para que possa realizar sua viagem ou entrega dentro do prazo estipulado Por essa razão a ideia desse projeto é desenvolver um algoritmo de navegação autônomo para um veículo onde o algoritmo é usado para planejar rotas seguras e eficientes em tempo real O cálculo de melhor rota com grafos dirigidos é uma técnica amplamente utilizada em diversas áreas como logística transporte sistemas de navegação e muitas outras É uma ferramenta essencial para otimizar rotas e garantir que os recursos sejam utilizados de forma eficiente As interseções entre as estradas são os vértices os segmentos de estradas entre essas interseções são as arestas e os pesos associados a cada aresta representam as distâncias rodoviárias Além disso 1 busca apresentar uma visão geral do conceito incluindo o que são grafos dirigidos como eles são utilizados para representar rotas e como os algoritmos podem ser aplicados para encontrar a solução ótima para o problema de melhor rota Para representar a aplicação usaremos o conceito de matrizes que podem representar um dado grafo por meio das entradas dessa matriz e também podemos atribuir o pesos das arestas Com isso podemos criar um grafo direcionado por meio das entradas de uma matriz com um nó para cada linha e coluna da matriz Em seguida adicionamos uma aresta do nó correspondente à linha i ao nó correspondente à coluna j com o peso da aresta igual ao valor da entrada da matriz na posição i j O algoritmo de Dijkstra é um algoritmo de busca em grafos que encontra o caminho mais curto entre um nó de partida e todos os outros nós em um grafo ponderado não direcionado O algoritmo funciona atribuindo uma distância inicial de infinito para todos os nós exceto o nó de partida que tem uma distância inicial de 0 Em seguida ele examina todos os nós adjacentes ao nó de partida e atribui a cada nó adjacente uma distância calculada com base na distância atual do nó de partida e no peso da aresta que os conecta O algoritmo de Dijkstra encontra o menor caminho de um nó fonte ou origem s até os outros nós de uma rede orientada para o caso em que todos os pesos dos arcos sejam não negativos 4 Este trabalho tem como objetivo desenvolver um sistema que visa utilizar matrizes juntamente com grafos dirigidos para solucionar problemas de busca de caminho mínimo usando a potência de matriz para gerar um grafo dirigido e através desse grafo utilizar o algoritmo de Dijkstra para calcular o menor caminho entre um ponto e outro Referências 1 EF Oliveira Um sistema para cálculo de rotas de caminho mínimo utilizando pgRouting e dados do OpenStreetMap Dissertação de mestrado Universidade Federal de Uberlândia 2021 2 SA Araujo e S Rangel Matemática Aplicada ao Planejamento da Produção e Lo gística 1a ed São Paulo Notas de Matemática Aplicada CNMAC 2014 ISBn eISSN 2236 5915 3 A S Rabelo M Moreira e Rangel S O número cromático do Brasil Ed por SB MAC Anais do CNMAC 2010 Acessado em 14032023 2010 url httpswwwibilce unespbrHomeDepartamentosMatematicaAplicadadocentessocorrocnmacbrasil cromatico691pdf 4 MÉNDEZ Y GUARDIA L Problema do caminho mais curtoAlgoritmo de Dijkstra Universidade Federal Fluminense Rio de Janeiro 2008 url httpswwwmarinhamilbrspolmsiteswwwmarinhamilbrspolmfiles0061pdf