Solving Traveling Salesman Problem by Ant Colony Optimization Algorithm with Association Rule

The traveling salesman problem (TSP) is among the most important combinatorial problems. Ant colony optimization (ACO) algorithm is a recently developed algorithm which has been successfully applied to several NP-hard problems, such as traveling salesman problem, quadratic assignment problem and job-shop problem. Association rule (AR) is the key in knowledge in data mining for finding the best data sequence. A new algorithm which integrates ACO and AR is proposed to solve TSP problems. Compare with the simulated annealing algorithm, the standard genetic algorithm and the standard ant colony algorithm, the new algorithm is better than ACO.

1. Introduction

Recently Traveling Salesman Problem (TSP) is the importance research core for combinatorial problems in the world. TSP is proven to be NP-hard. Research methods applied to TSP has been extended to some fine heuristics such as simulated annealing algorithm [1], tabu search algorithm [2] [3], genetic algorithms[4], ant colony algorithm [5] [6] etc. In this paper we present a new method to efficiently solve TSP problems. We used association rules to assist ant colony algorithm for solving TSP problems.