Analyzing the Effect of Recursive Branch Pruning and Heuristic Upper-Bound Initialization in Exact Travelling Salesman Problem Search

Abstract

This study investigates exact algorithms for solving the Travelling Salesman Problem (TSP), formulated as the problem of finding a minimum Hamiltonian cycle in a complete weighted undirected graph. Two recursive algorithms are presented and analyzed. The first algorithm, denoted RecursiveHamiltonianCycle (RHC), performs an exhaustive recursive search of the solution space, while the second algorithm, denoted PrunedHamiltonianCycleSearch (PHCS), applies an early branch-pruning mechanism to eliminate non-promising partial solutions. The main objective of this research is to evaluate the influence of recursive branch pruning and initial upper-bound selection on the computational efficiency of exact TSP search procedures. A series of computational experiments was conducted using complete graphs containing between 12 and 21 vertices. The obtained results show that both algorithms always produce identical optimal Hamiltonian cycles. However, the PHCS algorithm requires significantly fewer recursive calls and substantially less execution time. Additional experiments demonstrate that the quality of the initial upper bound has a substantial impact on pruning efficiency. A nearest-neighbor heuristic was therefore used to generate high-quality initial solutions, resulting in further reductions in the search space. The results confirm that combining heuristic initialization with exact branch-pruning search significantly improves the practical applicability of exact TSP algorithms while preserving solution optimality.

The authors' abstract, as published at the source. Algorithms, 2026 · DOI ↗