nLKH-ACS: A Niching Lin-Kernighan–Helsgaun-Based Ant Colony System for Multisolution Traveling Salesman Problems

The search for multiple optimal solutions in the traveling salesman problem (TSP), as a challenging multimodal optimization problem in the combinatorial domain, has received increasing attention in recent years. Nevertheless, the multisolution TSP (MSTSP) still remains extremely difficult for larger-scale TSP instances. In this article, we propose a niching Lin-Kernighan–Helsgaun (LKH)-based ant colony system (ACS), named nLKH-ACS, taking advantage of LKH’s ability to solve large-scale TSPs, ACS’s search efficiency, and the niching technique for diversity preservation. Specifically, first, to address multisolution problems, we design a niching LKH (nLKH) strategy to generate diverse cost-efficient spanning trees, and adopt the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-nearness on each tree to obtain a diverse candidate edge set. The nLKH strategy enhances the ACS by improving pheromone initialization, solution construction, and local search operation using spanning trees and candidate edge sets, thereby strengthening the search capability and diversity. Then, to balance convergence and diversity, an adaptive Gaussian strategy is utilized to update the pheromone matrix. Furthermore, we design an indicator to measure the geometric diversity between pairs of solutions in the MSTSP solution set. The comprehensive experiments on MSTSPs and TSPLIB are conducted to validate the performance of the proposed nLKH-ACS. The experimental results demonstrate the powerful solving capability and excellent diversity of the proposed nLKH-ACS, particularly in finding various optimal solutions in larger-scale TSP instances.