GKILS: una metaheuristica hibrida y escalable para el TSP euclideo de gran tamano

This work presents GKILS, a scalable hybrid metaheuristic solver for the 2D Euclidean Traveling Salesman Problem (TSP). GKILS integrates Iterated Local Search (ILS), Variable Neighborhood Search (VNS), Guided Local Search (GLS), adaptive operator selection inspired by ALNS, and a multilevel coarsen–solve–refine strategy. The method is designed as a self-contained, dependency-free Python implementation, prioritizing scalability, accessibility, and reproducibility over extreme optimality. The solver exploits geometric properties of the Euclidean TSP through k-nearest-neighbor candidate sets, grid-based spatial indexing, edge pools derived from multiple constructive tours, and a lightweight uncrossing post-processing step. A multilevel pipeline enables GKILS to scale to very large instances by solving coarsened representations and progressively refining solutions at finer levels. Experimental results on 43 benchmark instances from TSPLIB, VLSI, National TSP collections, and a massive 100,000-node TSP Art instance show an average gap of 4.17% on instances with known reference values, with practical runtimes on commodity hardware. GKILS targets educational, prototyping, and applied research scenarios where ease of implementation and scalability are preferred over state-of-the-art solvers requiring complex dependencies or advanced tuning.