Geometric Insertion Optimizer for TSPLIB

This paper introduces the Geometric Insertion Optimizer (GIO), a deterministic heuristic approach to the Traveling Salesman Problem (TSP). Unlike stochastic metaheuristics, GIO seamlessly maps multi-dimensional spatial distributions—including 2D Euclidean, 3D Euclidean, and Geographic (spherical) coordinate systems—into a 1-dimensional insertion sequence via a Fibonacci-inspired spatial projection. The algorithm executes a structured parameter sweep across a torsion constant (Φ) and a geometric tension threshold (Ratio), initializing the topological expansion from every node in the dataset. GIO performs route construction using continuous floating-point geometric analysis and angular penalization to mitigate spatial traps, while format-specific discrete distance evaluation (adapting dynamically to planar, spatial, or spherical mathematics) is used for final validation. Empirical results on TSPLIB instances demonstrate that a single unified implementation of GIO reliably finds exact optimal solutions (0.00% gap) across the vast majority of small to medium instances (up to 100 nodes), spanning planar, spatial, and spherical topologies. In the rare instances where the absolute global optimum is not strictly met, the algorithm maintains rigorous, near-optimal margins (typically sub-0.5%). Table 1 provides a representative sample of GIO’s performance across these diverse topological engines, demonstrating its precision in perfectly planar environments, 3D point clouds, and spherical geodesics. Table 1: Performance of the GIO Engine across diverse TSPLIB spatial topologies. Instance Name Topology Engine Nodes Optimal Distance GIO Distance Gap (%) burma14 GEO (Spherical) 14 3,323 3,323 0.0000% ulysses22 GEO (Spherical) 22 7,013 7,013 0.0000% iacubo50 EUC_3D (Spatial) 50 809 809 0.0000% berlin52 EUC_2D (Planar) 52 7,542 7,542 0.0000% pr76 EUC_2D (Planar) 76 108,159 108,159 0.0000% gr96 GEO (Spherical) 96 55,209 55,210 0.0018% jb_caos_cv135 EUC_2D (Planar) 100 5,734 5,735 0.0174% kroA100 EUC_2D (Planar) 100 21,282 21,282 0.0000% eil101 EUC_2D (Planar) 101 629 632 0.4769% lin105 EUC_2D (Planar) 105 14,379 14,379 0.0000% bier127 EUC_2D (Planar) 127 118,282 118,326 0.0372%