Improved Genetic Algorithms for Route Optimization

Abstract

Route optimization is a problem that has been studied for centuries. There exist numerous solutions to the problem, especially for scenarios that have a pre-existing geometry, resulting in a discrete search space, such as in case of a network of roads, a network of cellular nodes, etc. However, in scenarios such as path planning for long-distance electricity transmission lines, airplane route optimization, etc., there does not exist any predefined geometry. In such scenarios, many route optimization algorithms yield sub-optimal results because the size of the search space is an order of magnitude greater than conventional road network-based routing problems. The genetic algorithm has historically proven to yield good results in complex optimization scenarios. This thesis identifies a suitable way to model genetic algorithms for such problems by using GIS data over a geographical region. The thesis then purposes three methods inspired by the conventional genetic algorithm. The first method introduces a new mutation technique, the second technique introduces a new operator that makes use of the steepest descent method, while the third method suggests a new tournament selection approach that helps in retaining population diversity. It is found that the proposed techniques outperform the conventional genetic algorithm in terms of accuracy. Furthermore, a model is introduced for taking into consideration the obstacles over a geographical region and avoids them by incorporating penalties into the genetic algorithm. The thesis also identifies an underlying problem associated with the penalty-based approach; i.e. rapid loss of diversity and introduces a novel Island Selection technique to avoid losing diversity within the population. Results show that the Island Selection technique helps in maintaining population diversity, and improves the overall accuracy of the algorithm.