One direction of ant colony optimization researches is dividing the ants’ population into several colonies. These colonies work together to collectively solve an optimization problem. This approach offers good opportunity to explore a large area of the search space. It seems to be a suitable approach to improve the performance of ant algorithms. This paper proposes a new generic algorithmic approach utilizing multiple ant colonies with some new interaction techniques. Computational test shows promising results of the new approach. The proposed approach outperforms the single colony ant algorithms in term of the solution quality with the same computational effort.