Please use this identifier to cite or link to this item:
https://repositorio.ufu.br/handle/123456789/50051| ORCID: |  http://orcid.org/0009-0005-3627-6230 |
| Document type: | Trabalho de Conclusão de Curso |
| Access type: | Acesso Aberto |
| Title: | Análise de desempenho de um sistema de roteamento geoespacial com integração ao OpenStreetMap |
| Alternate title (s): | Performance analysis of a geospatial routing system with OpenStreetMap integration |
| Author: | Ferreira, Guilherme Coutinho Sousa |
| First Advisor: | Razente, Humberto Luiz |
| First member of the Committee: | Lima, Maria Adriana Vidigal de |
| Second member of the Committee: | Araújo, Rafael Dias |
| Summary: | O presente estudo investiga o desempenho de um sistema de roteamento baseado em Sistemas de Informação Geográfica (SIG), que identifica a menor rota possível para o deslocamento entre dois pontos ao longo de uma rede de ruas ou estradas. Esse sistema de roteamento utiliza dados cartográficos de código aberto do OpenStreetMap para cobrir todo o território do Brasil. Ele foi implementado utilizando PostgreSQL, juntamente com suas extensões associadas PostGIS e pgRouting, para gerenciar e analisar a rede viária. O backend do sistema de roteamento foi implementado utilizando FastAPI, e seu frontend foi implementado utilizando React e Leaflet. O sistema completo foi conteinerizado utilizando Docker. O principal objetivo deste estudo foi avaliar três algoritmos conhecidos de menor caminho: Dijkstra, AStar e AStar Bidirecional. Aproximadamente 673 mil pares de arestas e 671 mil vértices estavam contidos no conjunto de dados da rede viária brasileira, que foi importado para o sistema de roteamento utilizando o osm2pgsql. Os testes foram conduzidos em seis rotas diferentes, com comprimentos variados. Os resultados indicam que o Dijkstra apresentou os menores tempos de execução para cada rota testada e também forneceu, de forma consistente, vantagens de tempo quase constantes em relação tanto ao AStar quanto ao AStar Bidirecional. Esse resultado é contrário a estudos anteriores, que indicaram que o AStar geralmente supera o Dijkstra na determinação da menor rota. |
| Abstract: | The present study investigates the performance of a geographic information systems (GIS) based routing system which identifies the shortest route possible for travel between two points along a street or road network. This routing system utilizes open-source mapping data from OpenStreetMap to cover the entirety of Brazil. It was implemented using PostgreSQL with its associated extensions postgis and pgrouting to manage and analyze the road network. The routing system’s backend was implemented using fastapi and its frontend was implemented using react and leaflet. The complete system has been containerized within docker. The primary objective of this study was to evaluate three well known shortest-route algorithms: dijkstra, astar and bidirectional. Approximately 673 thousand edge pairs and 671 thousand vertexes were contained in the brazilian road network dataset, which was imported into the routing system utilizing osm2pgsql. Tests were conducted on six different routes of varying lengths. Results indicate that dijkstra produced the fastest execution times for each route tested; also consistently provided near-constant time advantages relative to both astar and bidirectional astar. This result is contrary to previous studies, which have indicated that astar generally outperforms dijkstra when determining the shortest route. |
| Keywords: | Caminho mínimo Shortest path pgRouting pgRouting OpenStreetMap OpenStreetMap PostGIS PostGIS Roteamento geoespacial Geospatial routing |
| Area (s) of CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Language: | por |
| Country: | Brasil |
| Publisher: | Universidade Federal de Uberlândia |
| Quote: | FERREIRA, Guilherme Coutinho Sousa. Análise de desempenho de um sistema de roteamento geoespacial com integração ao OpenStreetMap. 2026. 71 f. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação) – Universidade Federal de Uberlândia, Uberlândia, 2026. |
| URI: | https://repositorio.ufu.br/handle/123456789/50051 |
| Date of defense: | 12-Aug-2026 |
| Appears in Collections: | TCC - Ciência da Computação |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| AnaliseDesempenhoSistema (1) (1).pdf | 5.22 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
