EUVIMEDEUVIMED entdecken
Crossref

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

Ting Huang, Zhen-Quan Zhang, Yue-Jiao Gong, Jing Liu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →