Dynamic Adaptation of Genetic Algorithm for Solving Routing Problems on Large Scale Systems

Abstract

This paper is devoted to the implementation of the dynamic adaptation procedure for the genetic algorithm used for solving large-scale travelling salesman problem. This procedure serves to obtain more profitable solutions by a fixed operating time. In order to evaluate effectiveness of new approach computational experiments were performed on well-known problem instances from TSPLib library. As a result, generated solutions reduce the length of the routing plans in considered problem instances compare to classical genetic heuristics. By that, we show how to use the property of time inconsistency of heuristics to get better solutions. New criteria for estimating the efficiency of heuristics algorithms called experimental level of time consistency is introduced.