Publication Search

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.

Combinatorial optimization is a fundamental area in operations research and computer science, focusing on identifying optimal solutions from a finite set of possibilities. This study explores the integration of branch and bound methods with heuristic algorithms to address optimization problems in graph theory and discrete mathematics. Python was employed for algorithm implementation due to its flexibility and comprehensive computational libraries, enabling efficient data analysis and visualization. Several benchmark problems were examined, including the Traveling Salesman Problem (TSP), Minimum Spanning Tree (MST), and Graph Coloring. Simulations were conducted using datasets of varying sizes (small, medium, and large) to evaluate performance across different scales. The results demonstrate that the hybrid approach achieves a balance between solution quality and computational efficiency, outperforming brute-force methods in terms of speed while maintaining near-optimal accuracy. Tabulated results and graphical comparisons highlight the reduction in computation time and improved scalability of the proposed method. The findings suggest that combining systematic search strategies with heuristics offers a practical and effective framework for solving complex combinatorial optimization problems. Recommendations for future research include testing scalability with larger datasets, incorporating advanced metaheuristics, and applying the approach to real-world domains such as logistics and network design.

Travelling Salesman Problem (TSP) is a problem that is often encountered by a salesman who must travel exactly once to all consumers in a route and will return to the starting point of departure. Algorithm Genetic Algorithm is one way to find heuristic solutions based on the evolutionary ideas of natural selection and genetics. The aim is to find the optimal route for the distribution of bottled water products produced by PT. Mual Natio Maju Bersama. To find a solution, the chromosomes processed by the genetic algorithm are represented through the stages in the Genetic Algorithm individual initialization, fitness value, linear fitness ranking, roulette whell selection, crossover, and mutation. In order to achieve the optimum solution, namely The best path obtained is PT Mual Tio Maju Bersama –BUMDES Sait ni Huta - UD. Alvaro - UD. Lancelhot – UD. Alris – UD. Jamel – Toko Kelontong SRC Resi 2 – Toko Notra – UD. B Siringoringo – Toko Dahlia Siahaan – UD. Purba – UD. Cahaya – UD. Hutapea – UD. Gabe – UD. Setia II – UD. Larisma II – UD. Antoni – UD. Bona Siahaan – UD. Sederhana – Toko Manalu – UD. Setia I – Toko Ferdinan – UD. Alboy – Wisma Daun Mas – UD. Top Jaya – UD. Mega Silaban – BUMDES Silaitlait – UD. Rika – UD. Panamot – Piltik Coffee and Homestay Bandar Udara Silangit – UD. Rolas Boy – UD. Salamat Karya – UD. Simpang Jaya – UD. Lambok - Piltik Coffee and Homestay Siborongborong – UD. Bahagia – UD. Marlinca – UD. Heri Joel Pasaribu – UD. Ebenezer – UD. Mawar – UD. A Saudara – UD. SP Perdana – PDAM Mual Na Tio – UD. Rokkap - PT Mual Tio Maju Bersama. The best path length is 125.2700 cartesian units and the best fitness value is 0.008000.