Ahmad Budi Trisnawan; Syed Asif Ali; Erlita Sulistiati
This research explores the effectiveness of heuristic techniques for solving combinatorial optimization problems, with a particular focus on the Traveling Salesman Problem (TSP). Combinatorial optimization is a critical area of study, especially in fields like computer science, engineering, and economics, where finding optimal solutions from a finite set of possibilities is crucial. However, the NP-hard nature of many combinatorial problems, such as the TSP, makes traditional exact methods like Branch-and-Bound and Dynamic Programming computationally expensive and inefficient for larger problem sizes. The primary objective of this research is to evaluate the performance of heuristic methods, including Simulated Annealing (SA), Genetic Algorithms (GA), and Iterative Computation techniques, such as Tabu Search (TS) and Particle Swarm Optimization (PSO). These methods are tested for their ability to provide approximate solutions efficiently. The findings reveal that while ACO provided the best solution quality, it had the longest runtime. TS was the fastest, though with slightly lower solution quality. SA and GA demonstrated a balance between solution quality and computational efficiency, but their performance heavily depended on parameter tuning. The hybridization of SA and GA showed potential for improving solution quality but introduced additional complexity. The research concludes that heuristic methods, especially when combined, offer viable solutions for large-scale combinatorial optimization problems, though the trade-off between solution quality and computational time must be considered when selecting an algorithm.