Scalable Route Optimization: A Case Study on Real-World Data
Atra Zeynep Bahçeci, Zeynep Kezban Turgut, Berkay Topçu · 2025
The Travelling Salesperson Problem (TSP) is a fundamental routing problem that has garnered significant attention in both academic research and practical applications. In this paper, we enhance the well-established Genetic Algorithm (GA) model by integrating k-means clustering to improve its scalability for large-scale instances. Our approach partitions the problem into clusters, solving each sequentially while utilizing the output of one cluster as an input for the next. Extensive experimental evaluations on real-world data demonstrate that our proposed method reduces total route length by over 20.94% on average compared to expert-designed routes, by 6.36% compared to Tabu Search (TS), and by 15.89% compared to the traditional GA. The code for the proposed method is available on GitHub.