Route planning by evolutionary computing: an approach based on genetic algorithms

摘要

Route planning is a classical kind of problem that arises in different areas of knowledge, such as path scheduling, transportation, collision avoidance, robotics and game design. Due to its stochastic behaviour, the search for viable paths can benefit from the use of heuristic algorithms, such as those available in evolutionary computing. In this way, this work presents a procedure to evaluate a feasible route between two points, in a constrained environment, through the use of a genetic algorithm. The developed implementation starts by searching for the track from random generated paths, which will evolve towards the best possible solution. Results demonstrate the ability of the algorithm to learn and produce suitable routes without previous knowledge of the environment. It can be concluded that the algorithm is simple, produces reliable tracks and is fast enough to deal with problems in real time, thus allowing it to be applied in real world issues, such as the planning of transport routes capable of avoiding congestion points.