Toward Instance-Aware Swarm Intelligence for TSP via Distance Uniqueness

The Traveling Salesman Problem (TSP) is a classical Nondeterministic Polynomial time hard (NP-hard) combinatorial optimization challenge that seeks the shortest Hamiltonian cycle in a weighted graph. Swarm intelligence algorithms have been utilized intensively in solving TSP instances of varying sizes. However, the effectiveness of a swarm algorithm can be affected by the structural characteristics of the TSP instance being solved. Furthermore, there is no superior swarm algorithm that provably outperforms all others on all TSP instances. Consequently, there is a need to build a computationally efficient Algorithm Selector (AS) that automatically selects the proper swarm algorithm to be applied per instance. This paper deeply investigates the effectiveness of various swarm algorithms in solving TSP instances based on the structural characteristics of the TSP instance type. To capture this, we propose a comprehensive framework that initially builds a portfolio of efficient swarm algorithms to be utilized in solving the TSP. Equipped with an easily computable feature, namely the uniqueness factor, we introduce a classification scheme that divides TSP instances into “drilling” and “cities” categories. With intensive analysis on various TSP instances, the AS is built to further select the appropriate swarm algorithm to be applied per instance with a simple threshold-based approach.