Hybrid Christofides Algorithm and List-Based Simulated Annealing (HCA-LBSA) dalam Menyelesaikan Traveling Salesman Problem (TSP)

Abstract

The Traveling Salesman Problem (TSP) is a well-known classical problem in combinatorial optimization and graph theory. This study proposes the Hybrid Christofides Algorithm and List-Based Simulated Annealing (HCA-LBSA) to solve TSP. This approach employs the Christofides algorithm as an initial solution due to its guarantee that the result does not exceed 3/2 of the optimal solution. To further enhance solution quality, optimization is performed using List-Based Simulated Annealing (LBSA). LBSA is an adaptive version of Simulated Annealing (SA), integrating a temperature list, Variable Markov Chain Length (VMCL), and the Heuristic Augmented Instance-Based Sampling Method to improve the efficiency of optimal solution exploration. The evaluation was conducted on 32 datasets, where HCA-LBSA achieved an average percentage error of the average tour length (PEav) of 0.619% with an average execution time of 23.285 seconds. From the parameter tuning process, the optimal parameter combination for HCA-LBSA is Lmax (the length of the temperature list) of 140 and pos (the relative position of the generation with the maximum MCL) of 0.5. The performance of HCA-LBSA is also compared with the ELBSA, LBSA, ASA-GS, SOS-SA, AHSA-TS, and D-CLPSO algorithms. Experimental results indicate that HCA-LBSA significantly outperforms LBSA, ASA-GS, AHSA-TS, and D-CLPSO. This demonstrates that HCA LBSA is capable of providing effective solutions for solving the TSP.