Análise de desempenho de um sistema de roteamento geoespacial com integração ao OpenStreetMap

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.