GES-TSP: Grafrandverkleining voor het TSP

Gepubliceerd 14 July 2026

Het oplossen van grootschalige gevallen van het Traveling Salesman Problem (TSP) is computationeel intensief. Onderzoekers gebruiken vaak grafverkleiningsmethoden om de efficiëntie te verbeteren. Traditionele methoden zijn meestal gebaseerd op vaste heuristieken en benutten niet volledig de specifieke structurele informatie van de gevallen. Dit artikel stelt Graph Edge Sparsification (GES) voor, een leermethode voor grafverkleining voor Euclidische TSP. Door geometrische informatie en combinatorische optimalisatie te integreren, genereert de methode adaptief een verkleiningsgrafiek voor verschillende gevallen, waardoor de grafiek aanzienlijk wordt verkleind en het oplossingsproces wordt versneld. Experimentele resultaten tonen aan dat de methode tot 95% van de randen kan verwijderen met een optimale waarde binnen 1%. In sommige gevallen overschrijdt de snoeisnelheid 99%.