A New Ant Colony Algorithm for Traveling Salesman Problem with Negative Weight Edges

Abstract

We propose a new Ant Colony Algorithm (ACO) which is a Hybrid combination of ACO with Simulated Annealing (SA). We call this algorithm the ACOSA algorithm. This new algorithm has been used to solve the Traveling Salesman Problem with some Negative Weight Edges (TSPne).

We compare the original ACO on TSPne with ACOSA and report their performance. It is observed that the new ACOSA algorithm gives more optimal results as compared to ACO on TSPne.