Ant Colony Optimization Approach for TTP with Balanced Intensification and Diversification

Abstract

Ant Colony Optimization (ACO) is one of the techniques of swarm intelligence motivated by real world foraging behavior of ants. ACO has been successfully applied to so many combinatorial optimization problems successfully. However, ACO has not achieved excellent solutions to constraint satisfaction problems. Traveling Tournament Problem (TTP) is a real world sports time tabling problem that abstracts the important issues in creating time tables where teams‘ travel is an important issue and is one of the constraint satisfaction problems. In the existing approaches of ACO to TTP have some of the issues like poor quality solution (sum of the total distance traveled by each team in the tournament is large) and large solution construction time. So here, we have made efforts to deal with some of the above mentioned issues. First we have compared different ACO family algorithms and have analyzed that ACS is the most successful algorithm of ACO family. So here by using Ant Colony System (ACS) as the base algorithm with backtracking integration, we are getting better solution quality. Cranky ant approach has been used for better exploration. Apart from the solution quality, number of iterations and the number of local search solutions needed to construct the solution have been reduced up to a large extent.