nLKH-ACS: A Niching Lin-Kernighan–Helsgaun-Based Ant Colony System for Multisolution Traveling Salesman Problems
IEEE Transactions on Evolutionary Computation · 2025-12 · 29 (6) · 2596-2610
DOI: 10.1109/tevc.2024.3507777 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Evolutionary Computation, 2025-12. Verfasst von Ting Huang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 47 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Guangdong Natural Science Funds for Distinguished Young Scholars, Guangzhou Basic and Applied Basic Research Foundation.
Abstract (Originalsprache)
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 $\alpha $ -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.
Förderung
- National Natural Science Foundation of China
- Guangdong Natural Science Funds for Distinguished Young Scholars
- Guangzhou Basic and Applied Basic Research Foundation
- Fundamental Research Funds for the Central Universities
- Guangdong High-Level Innovation Research Institution Project
- Guangzhou Key Research and Development Program
- Xidian-UTAR China Malaysia Science and Technology Innovation Fund
Zitieren
APA
Huang, T., Zhang, Z., Gong, Y., & Liu, J. (2025). nLKH-ACS: A Niching Lin-Kernighan–Helsgaun-Based Ant Colony System for Multisolution Traveling Salesman Problems. IEEE Transactions on Evolutionary Computation, 29(6), 2596-2610. https://doi.org/10.1109/tevc.2024.3507777
Vancouver
Huang T, Zhang Z, Gong Y, Liu J. nLKH-ACS: A Niching Lin-Kernighan–Helsgaun-Based Ant Colony System for Multisolution Traveling Salesman Problems. IEEE Transactions on Evolutionary Computation. 2025;29(6):2596-2610. doi:10.1109/tevc.2024.3507777
BibTeX
@article{Huang2025,
author = {Huang, Ting and Zhang, Zhen-Quan and Gong, Yue-Jiao and Liu, Jing},
title = {nLKH-ACS: A Niching Lin-Kernighan–Helsgaun-Based Ant Colony System for Multisolution Traveling Salesman Problems},
journal = {IEEE Transactions on Evolutionary Computation},
year = {2025},
volume = {29},
number = {6},
pages = {2596--2610},
doi = {10.1109/tevc.2024.3507777}
}
EUVIMED