Implementação e avaliação de algoritmos sequencial e paralelo para descoberta de rotas ótimas para veículos

Abstract

The significant increase in the population in large urban centers has created some problems analyzed and addressed in this work as urban mobility and its efficiency, due to the increasing need for fast and low cost mobility. In this scenario, Smart Cities offers a variety of solutions that enable you to reduce all problems, generating diverse and sustainable solutions. From this, a vehicle traffic simulation was performed in regions of the city of Aracaju in the state of Sergipe - Brazil and in Manhattan in the state of New York - USA, in the traffic simulation tool SUMO (Simulation of Urban MObility), where the classic in the literature A-Star algorithm was executed, implemented in parallel, using NVIDIA’s CUDA and a Graphics Processing Unit (GPU) which in turn performs complex calculations efficiently when compared to the CPU (Central Process Unit) and also implemented sequentially, which executes one instruction at a time on the CPU. The use of GPU itself, as well as being advantageous due to its power to perform floating point operation, is also a viable device solution for its low financial cost, thus avoiding a supercomputer infrastructure to accomplish such a task. Thus, the algorithm implemented in parallel in this work and executed in the GPU, generated satisfactory results when compared to the implemented sequential algorithms. These results show us the power and efficiency of parallelism to generate fast and efficient solutions. The results show that it is possible to envision the implementation of this solution in Smart Cities for thousands of vehicles, by proposing low cost algorithms for the definition of optimized routes within the scope of the A-Star algorithm and Dijkstra, thus replacing an entire infrastructure. of supercomputers by GPUs.