2025/12/16 by Trofimov, Ilya, Voronkova, Daria, Mironenko, Alexander +4
Computer Science · Engineering · #Artificial Intelligence (cs.AI) #Computational Geometry (cs.CG) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2512.15800
openalex publication_date 2025/12/16 · openalex created_date 2025/12/21 · openalex updated_date 2026/07/28
We introduce a topological feedback mechanism for the Travelling Salesman Problem (TSP) by analyzing the divergence between a tour and the minimum spanning tree (MST). Our key contribution is a canonical decomposition theorem that expresses the tour-MST gap as edge-wise topology-divergence gaps from the RTD-Lite barcode. Based on this, we develop a topological guidance for 2-opt and 3-opt heuristics that increases their performance. We carry out experiments with fine-optimization of tours obtained from heatmap-based methods, TSPLIB, and random instances. Experiments demonstrate the topology-guided optimization results in better performance and faster convergence in many cases.