Optimizing the Traveling Salesman Problem Using Machine Learning and Predictive Algorithms

Abstract

The Traveling Salesman Problem (TSP) is a foundational challenge in optimization, with applications in logistics, routing, and scheduling. Traditional algorithms such as dynamic programming and brute-force search guarantee optimal solutions but become computationally expensive as the number of cities grow, hindering scalability. Consequently, research has shifted towards machine learning (ML) and predictive algorithms, which show promise in approximating optimal solutions more efficiently. This study aims to optimize TSP using ML models, specifically focusing on enhancing scalability and minimizing computational overhead. The approach incorporates techniques like reinforcement learning (RL) and graph neural networks (GNNs), leveraging their ability to learn and generalize from smaller problem instances. The primary contribution of this work is an ML-driven framework for TSP, which demonstrates improved efficiency and adaptability compared to traditional algorithms. Evaluation metrics, including total path length, convergence time, and optimality gap, validate the model's effectiveness, achieving optimal paths with reduced execution time. This research offers a practical ML-based solution for TSP that balances accuracy with computational speed, providing a feasible alternative for large-scale and dynamic real-world applications.