Tile map size optimization for real world routing by using differential evolution

Abstract

Finding the shortest path between two places is a well known problem in road traveling. While most of the work done up to this moment is focused on algorithmics, efficiently managing the information has received significantly less attention. Nevertheless, real world problems like road map routing present a challenge due to the impact that the immense size of the map has over the temporal complexity of the routing algorithms. In this work we propose a strategy for efficiently computing the shortest path in real road maps based on data managing: the tile map partitioning. To recreate a real scenario, we implemented a routing system and we tested our strategy using the road map of the Province of Málaga, Spain. Using a Differential Evolution we found the optimal tile size and prove that significant time reductions can be achieved by using the tile map partitioning.