Hybrid Approach: Combining Hill Climbing and Genetic Algorithms for Traveling Salesman Problem
Tina Babu, Rekha R Nair, Sneha Sumanth, T P Ishith, Chitra K S · 2025
The Traveling Salesman Problem (TSP) is a classic NP-hard optimization challenge, requiring an efficient approach to identify near-optimal solutions. This paper presents a hybrid algorithm combining Genetic Algorithm (GA) and Hill Climbing (HC) to improve solution accuracy and convergence speed. GA provides global search capabilities through selection, crossover, and mutation, while HC enhances local optimization by refining solutions iteratively. The hybrid approach leverages GA's exploration strength and HC's exploitative power, reducing premature convergence and improving search efficiency. Experimental results indicate that the hybrid GA-HC algorithm outperforms standalone GA and HC in terms of tour length reduction and computational efficiency. Benchmarked on TSP instances, the proposed method demonstrates a 15% improvement in solution quality compared to traditional approaches. Additionally, the hybrid method achieves faster convergence, requiring 30% fewer iterations than standalone GA. The results highlight the hybrid algorithm's potential for real-world applications such as logistics, network design, and supply chain management. This study contributes to the growing research on hybrid metaheuristics, showcasing the benefits of integrating global and local search strategies to solve complex combinatorial problems.