The travelling salesman problem is a common NP-hard problem that needs quick and adequate solutions in many different areas e.g. in logistics, biology and manufacturing, to name a few. NP-hard problems can not be solved in polynomial time by brute-force solutions, which is why heuristic algorithms that give suboptimal solutions quickly are needed.
This study introduces a new heuristic algorithm based on subdividing the travelling salesman problem by use of clustering and proposes a new heuristic for connecting the subproblems together by approximating endpoints between clusters, resulting in a complete tour. Therefore, the posed research questions of the study concern how the application of different clustering methods and the proposed heuristic of endpoint approximating affects the quality of the solutions produced by the algorithm.
To enable the research, an experiment was conducted, data collection was done by observation, and the data was analyzed by the use of descriptive statistics.
The results indicate that the choice of clustering method greatly impacts the closeness of the generated solutions to the optimal solution, where KMeans and Agglomerative Hierarchical clustering using an average inter-cluster distance metric clearly outperformed the other methods. Also, the approximation heuristic was concluded to improve the algorithm’s results.
The proposed algorithm can be used to quickly find a suboptimal solution for large instances of the problem. The proposed heuristic for approximating endpoints for open-loop subsolutions may be implemented into other solutions to enhance other heuristic algorithms and would need further research.