TSP review: performance comparison of the well-known methods on a standardized dataset

Abstract

Decades of research into the Travelling Salesman Problem (TSP) have yielded a plethora of algorithms, chiefly grouped into exact algorithms and heuristic/approximation algorithms. Exact algorithms, like the brute-force guarantee optimal solutions at the cost of exponential computational complexity. Conversely, heuristic algorithms, such as Greedy and natureinspired methods, offer sub-optimal solutions but with reduced computational demands. This study harnesses Reinelt Gerhard's TSPLIB dataset, featuring diverse TSP scenarios, including realworld challenges and problems crafted to gauge algorithmic efficacy in various contexts, like high-density clusters and Hamilton Cycle hard clusters. The research's crux is a comparative analysis of these TSP-solving techniques using TSPLIB. Subsequent sections delve into academic references, dataset methodologies, planned solutions, a juxtaposition of algorithmic results, culminating in concluding insights, that showed the shaked Nearest-Neighbor in current set of algorithms' implementation is the best, and it is worth trying to make it even better by applying some hybrid creative techniques, which is the subject of our future works.

More by Iskander Akhmetov

• A Lightweight Extractive Compression Pipeline for Long-Context Retrieval-Augmented GenerationComputación y Sistemas · 2026
• Character N-Gram Features for Kazakh POS Tagging Under Strict OOV EvaluationInternational Conference on Computer Science and Engineering · 2026
• KazakhStopEval: Stop-Word Inventories, Validation Benchmarks, and NLP Evaluation Artifacts for Kazakh Library OCR CollectionsMendeley Data · 2026
• Hierarchical Multi-Agent Extractive Framework for Long-Document Mind Map GenerationComputación y Sistemas · 2026