Aplicação de Grafos Dirigidos em Sistemas de Navegação

Proceeding Series of the Brazilian Society of Computational and Applied Mathematics Preprint Uma aplicação de grafos dirigidos Alessandro Lopes 1 Felipe Leviski Medeiros2 Natan Hirata3 Irene Craveiro4 Silvana Morita Melo5 UFGD FACET Dourados MS 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 a complexidade aumenta à medida que o número de cidades ou rotas cresce O cálculo de melhor rota com grafos dirigidos é uma solução para esse desafio Grafos dirigidos são uma representação visual de conexões direcionais entre nós ou pontos No contexto de rotas os nós representam cidades e as conexões são estradas com pesos associados como a distância ou o tempo de viagem para isso consulte 2 3 Figura 1 Representação do grafo associado ao mapa do Brasil Fonte 3 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 assim percebese uma grande necessidade de um sistema que possa 1alessandrosousa082academicoufgdedubr 2felipemedeiros037academicoufgdedubr 3natanhirata069academicoufgdedubr 4irenecraveiroufgdedubr 5silvanameloufgdedubr 2 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 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 Agradecimentos Projeto sendo desenvolvido na discipina de Àlgebra Linear e Geometria Analítica ministrada pela Profa Dra Irene Craveiro sob a coorientação da Porfa Dra Silvana Morita Melo 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 22365915 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 Y Méndez e L Guardia Problema do caminho mais curtoAlgoritmo de Dijkstra Universidade Federal Fluminense Rio de Janeiro 2008 url httpswwwmarinhamil brspolmsiteswwwmarinhamilbrspolmfiles0061pdf