An Efficient Tour Construction Heuristic for Generating the Candidate Set of the Traveling Salesman Problem with Large Sizes

Boldizsár Tüű-Szabó (), Péter Földesi and László T. Kóczy
Additional contact information
Boldizsár Tüű-Szabó: Department of Information Technology, Szechenyi Istvan University, 9026 Gyor, Hungary
Péter Földesi: Department of Logistics, Szechenyi Istvan University, 9026 Gyor, Hungary
László T. Kóczy: Department of Information Technology, Szechenyi Istvan University, 9026 Gyor, Hungary

Mathematics, 2024, vol. 12, issue 19, 1-21

Abstract: In this paper, we address the challenge of creating candidate sets for large-scale Traveling Salesman Problem (TSP) instances, where choosing a subset of edges is crucial for efficiency. Traditional methods for improving tours, such as local searches and heuristics, depend greatly on the quality of these candidate sets but often struggle in large-scale situations due to insufficient edge coverage or high time complexity. We present a new heuristic based on fuzzy clustering, designed to produce high-quality candidate sets with nearly linear time complexity. Thoroughly tested on benchmark instances, including VLSI and Euclidean types with up to 316,000 nodes, our method consistently outperforms traditional and current leading techniques for large TSPs. Our heuristic’s tours encompass nearly all edges of optimal or best-known solutions, and its candidate sets are significantly smaller than those produced with the POPMUSIC heuristic. This results in faster execution of subsequent improvement methods, such as Helsgaun’s Lin–Kernighan heuristic and evolutionary algorithms. This substantial enhancement in computation time and solution quality establishes our method as a promising approach for effectively solving large-scale TSP instances.

Keywords: fuzzy clustering; candidate set; TSP; heuristic (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/19/2960/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/19/2960/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:19:p:2960-:d:1484274

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().