SIGNATURE WORK
CONFERENCE & EXHIBITION 2023

The Traveling Salesman Problem (TSP) is an important NP-Hard combinatorial problem worth studying in Computer Science, Mathematical Optimization, and Operations Research. Heuristic methods are often used in looking for a nearly-optimized solution for TSP. Common heuristic methods for solving the TSP are known to be the Genetic Algorithm (GA), Ant Colony Optimization (ACO), Simulated Annealing (SA), and the Lin-Kernighan-Helsgaun (LKH) algorithm. Recent studies have combined the Reinforcement Learning (RL) methods with LKH to boost its performance. However, little is known about the performance differences between the many heuristic methods given. Also, little is understood about the impact of the TSP landscape (structure) on the performance of the heuristic methods. In this Signature Work research project, we discussed five heuristic methods which are GA, ACO, SA, LKH, VSR-LKH. We employed four types of landscape instances from the TSPLIB: random uniform instances, random clustered instances, somewhat structured instances, and highly structured instances to run the five heuristics. We did an empirical analysis of the performance. Visualizations and analytical discussions are also included. We find that the loss and convergence speed of the algorithms is not directly related to the dimension of the TSP instances but the landscape of the TSP instances instead.