A comparative study of heuristic and exact algorithms: the case of cheapest insertion heuristic and branch and bound algorithm
TL;DR
The comparison suggests that CIH is more suitable for large-scale problems requiring quick solutions, whereas B&B is preferable when obtaining the optimal solution is essential, despite its higher computational cost and longer execution time.
Abstract
The Traveling Salesman Problem (TSP) is one of the most prominent combinatorial optimization problems, attracting significant interest in both research and practical applications. This paper compares the performance of two approaches for solving the TSP: the Cheapest Insertion Heuristic (CIH) and the Branch-and-Bound (B&B) algorithm. The results show that CIH produced a route of 584 km. This approach is simple and fast to execute, but it provides approximate solutions and does not guarantee optimality. In contrast, B&B was effective in finding the optimal solution by relying on lower-bound (LB) calculations and systematically eliminating nonpromising branches. The best route obtained using B&B was A → D → C → B → E → A. The comparison suggests that CIH is more suitable for large-scale problems requiring quick solutions, whereas B&B is preferable when obtaining the optimal solution is essential, despite its higher computational cost and longer execution time.