An Efficient Tour Construction Heuristic for Generating the Candidate Set of the Traveling Salesman Problem with Large Sizes
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-09-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/12/19/2960 |
| _version_ | 1827066184190656512 |
|---|---|
| author | Boldizsár Tüű-Szabó Péter Földesi László T. Kóczy |
| author_facet | Boldizsár Tüű-Szabó Péter Földesi László T. Kóczy |
| author_sort | Boldizsár Tüű-Szabó |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2025-03-19T23:14:54Z |
| format | Article |
| id | doaj.art-1060a96143a041fab6d18c7d4cd617c7 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2025-03-19T23:14:54Z |
| publishDate | 2024-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-1060a96143a041fab6d18c7d4cd617c72024-10-15T12:59:55ZengMDPI AGMathematics2227-73902024-09-011219296010.3390/math12192960An Efficient Tour Construction Heuristic for Generating the Candidate Set of the Traveling Salesman Problem with Large SizesBoldizsár Tüű-Szabó0Péter Földesi1László T. Kóczy2Department of Information Technology, Szechenyi Istvan University, 9026 Gyor, HungaryDepartment of Logistics, Szechenyi Istvan University, 9026 Gyor, HungaryDepartment of Information Technology, Szechenyi Istvan University, 9026 Gyor, HungaryIn 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.https://www.mdpi.com/2227-7390/12/19/2960fuzzy clusteringcandidate setTSPheuristic |
| spellingShingle | Boldizsár Tüű-Szabó Péter Földesi László T. Kóczy An Efficient Tour Construction Heuristic for Generating the Candidate Set of the Traveling Salesman Problem with Large Sizes Mathematics fuzzy clustering candidate set TSP heuristic |
| title | An Efficient Tour Construction Heuristic for Generating the Candidate Set of the Traveling Salesman Problem with Large Sizes |
| title_full | An Efficient Tour Construction Heuristic for Generating the Candidate Set of the Traveling Salesman Problem with Large Sizes |
| title_fullStr | An Efficient Tour Construction Heuristic for Generating the Candidate Set of the Traveling Salesman Problem with Large Sizes |
| title_full_unstemmed | An Efficient Tour Construction Heuristic for Generating the Candidate Set of the Traveling Salesman Problem with Large Sizes |
| title_short | An Efficient Tour Construction Heuristic for Generating the Candidate Set of the Traveling Salesman Problem with Large Sizes |
| title_sort | efficient tour construction heuristic for generating the candidate set of the traveling salesman problem with large sizes |
| topic | fuzzy clustering candidate set TSP heuristic |
| url | https://www.mdpi.com/2227-7390/12/19/2960 |
| work_keys_str_mv | AT boldizsartuuszabo anefficienttourconstructionheuristicforgeneratingthecandidatesetofthetravelingsalesmanproblemwithlargesizes AT peterfoldesi anefficienttourconstructionheuristicforgeneratingthecandidatesetofthetravelingsalesmanproblemwithlargesizes AT laszlotkoczy anefficienttourconstructionheuristicforgeneratingthecandidatesetofthetravelingsalesmanproblemwithlargesizes AT boldizsartuuszabo efficienttourconstructionheuristicforgeneratingthecandidatesetofthetravelingsalesmanproblemwithlargesizes AT peterfoldesi efficienttourconstructionheuristicforgeneratingthecandidatesetofthetravelingsalesmanproblemwithlargesizes AT laszlotkoczy efficienttourconstructionheuristicforgeneratingthecandidatesetofthetravelingsalesmanproblemwithlargesizes |