Analyzing the Effect of Recursive Branch Pruning and Heuristic Upper-Bound Initialization in Exact Travelling Salesman Problem Search
Open Access
- 30 October 2026
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 19 (11) , 938
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.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Graph convolutional branch and boundEuropean Journal of Operational Research, 2026
- Solving the traveling salesman problem with machine learning: a review of recent advances and challengesArtificial Intelligence Review, 2025
- Valid inequalities and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacksEuropean Journal of Operational Research, 2022
- Deep reinforcement learning for transportation network combinatorial optimization: A surveyKnowledge-Based Systems, 2021
- Reasoning About Iteration and Recursion Uniformly Based on Big-Step Semantics2021
- A branch-cut-and-price algorithm for the traveling salesperson problem with hotel selectionComputers & Operations Research, 2020
- A distance matrix based algorithm for solving the traveling salesman problemOperational Research, 2018
- A Difference in Complexity Between Recursion and Tail RecursionTheory of Computing Systems, 2016
- Automatic transformation of iterative loops into recursive methodsInformation and Software Technology, 2015
- NP-hard graph problems and boundary classes of graphsTheoretical Computer Science, 2007