Hybrid Artificial Intelligence Heuristics and Clustering Algorithm for Combinatorial Asymmetric Traveling Salesman Problem

Abstract

Problems of combinatorial optimization are characterized by their well-structured problem definition as well as by their huge number of action alternatives in practical application areas of reasonable size. Especially in areas like routing, task allocation, or scheduling, such kinds of problems often occur. Artificial Intelligence Heuristics, otherwise called Meta-heuristic techniques that mimic natural processes, can produce ‘good’ results in reasonable short runs for this class of optimization problems. Even though those bionic heuristics are much more flexible regarding modifications in the problem description when being compared to classical problem specific heuristics, they are often superior in their results. Those bionic heuristics have been developed following the principles of natural processes. In that sense, Genetic Algorithms (GAs) try to imitate the biological evolution of a species in order to achieve an almost optimal state whereas Simulated Annealing (SA) was initially inspired by the laws of thermodynamics in order to cool down a certain matter to its lowest energetic state. This paper develops a set of metaheuristics (GA, SA and Hybrid GA-SA) to solve a variant of combinatorial optimization problem called Asymmetric Traveling Salesman Problem. The set of met heuristics is compared with clustering based heuristic and the results are encouraging.