An improved tabu search algorithm for solving discrete optimization problems

This thesis develops an innovative hybrid metaheuristic algorithm for solving NP￾hard problems like the Traveling Salesman Problem (TSP). Named TS-HC-VNS, the method synergistically combines the strengths of three fundamental algorithms: Tabu Search (TS), Hill Climbing (HC), and Variable Neighborhood Search (VNS). The algorithm aims to establish a dynamic balance between intensification and diversification by integrating TS's memory-based guidance, HC's rapid local intensification, and VNS's systematic diversification (escaping local optima) strategy. The performance of TS-HC￾VNS, developed in Python, was extensively tested on 30 different TSP instances from the standard TSPLIB library. These tests analyze the algorithm's scalability, efficiency, and solution quality against problems of varying sizes. The effects of initial solutions, acceleration techniques like neighborhood segmentation, and key parameters were examined in detail. Experimental results have demonstrated that the proposed algorithm is highly effective. It found the known optimal solutions for small and medium-scale problems without error and delivered competitive results for large-scale problems when compared to state-of-the-art approaches. The most remarkable feature of the algorithm is its consistent and robust performance across different runs. It has been proven to be superior to many contemporary algorithms, particularly in terms of average solution quality, exhibiting lower deviation rates. This study presents a powerful alternative for solving TSP and similar complex optimization problems, especially in terms of robustness and reliability.