🤖 AI

GES-TSP: Graph Edge Sparsification for TSP

Dit artikel introduceert GES, een op leren gebaseerde methode voor graafrand-sparsificatie voor de Euclidische TSP die de grootte van de graaf adaptief met tot wel 99% vermindert terwijl een optimaliteitsverschil van minder dan 1% behouden blijft, wat de oplossing van grootschalige instanties aanzienlijk versnelt.

Oorspronkelijke auteurs: Tianfeng Chen, Xianyue Li

Gepubliceerd 2026-07-14

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Tianfeng Chen, Xianyue Li

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een bezorger bent met een kaart van een hele stad, en je baas zegt: "Bezoek elk huis precies één keer en kom terug bij huis, maar doe het zo snel mogelijk." Dat is het Handelsreizigersprobleem (Traveling Salesman Problem of TSP). Stel je nu voor dat die kaart niet alleen een lijst met huizen is; het is een gigantisch web waar elk huis met elk ander huis verbonden is door een directe weg. Als je 1.000 huizen hebt, zijn dat bijna een miljoen wegen om te controleren! Het proberen te vinden van de perfecte route op een kaart die zo groot is, is als het zoeken naar een specifiek zandkorreltje in een woestijn terwijl je geblinddoekt bent — het duurt eeuwen en kost een fortuin aan computerkracht.

Lange tijd probeerden mensen dit op te lossen door gebruik te maken van "vaste regels", zoals altijd de dichtstbijzijnde buur kiezen of driehoeken tussen punten tekenen. Het is een beetje alsof je zegt: "Ik kijk alleen naar de drie huizen die het dichtst bij me vandaan liggen," of "Ik kijk alleen naar huizen die perfecte driehoeken vormen." De auteurs van dit artikel, Tianfeng Chen en Xianyue Li, zeggen dat deze oude regels te rigide zijn. Ze houden geen rekening met de specifieke eigenaardigheden van dit specifieke stadje. Ze kunnen een kortere route missen of een weg opnemen die eigenlijk een doodlopende weg is.

Het Grote Idee: Een Slimme Filter
De auteurs stellen een nieuwe truc voor genaamd GES-TSP (Graph Edge Sparsification). Denk aan het inhuren van een superintelligente, door AI aangedreven verkenner die naar het hele rommelige web van wegen kijkt en zegt: "Hé, 95% van deze wegen is nutteloos voor de beste route. Laten we ze weggooien en alleen de meest veelbelovende overhouden."

Zo werkt hun "verkenner" stap voor stap:

De Ruwe Versie (Coarse Graph): Eerst gebruikt de verkenner een klassieke geometrische truc genaamd "Delaunay triangulatie". Stel je voor dat je stippen op een vel papier verbindt zodat er geen stip binnen de cirkel van een driehoek ligt die je tekent. Dit snijdt direct een enorme hoeveelheid extreem lange wegen weg, waardoor er een veel kleiner, schoner web overblijft. Het is een goed begin, maar niet perfect.
Het Slimme Brein (GNN): Vervolgens voeren ze dit kleinere web in een "Graph Neural Network" (GNN). Je kunt dit zien als een student die duizenden eerdere bezorgroutes heeft bestudeerd. De student kijkt naar de wegen en stelt vier specifieke vragen over elke weg:
- Hoe lang is de weg? (Kort is meestal beter).
- Zijn deze twee huizen buren? (Zijn ze dichtbij elkaar?).
- Hoe verhoudt deze weg zich tot de beste weg die uit dit huis vertrekt? (Is het een "goede" keuze of een "slechte" keuze?).
- Wat zegt het grote plaatje? (Past deze weg in de algemene structuur van de stad?).
Het Scoreformulier: Op basis van deze vragen geeft de AI een score aan elke weg. Hoge scores betekenen: "Hou deze!" Lage scores betekenen: "Weg ermee!"
Het Veiligheidsnet: Om te voorkomen dat ze per ongeluk de enige weg die twee delen van de stad met elkaar verbindt, voegen ze een paar specifieke wegen toe die zijn gevonden door een klassiek algoritme genaamd "Christofides". Dit garandeert dat er altijd een geldige route mogelijk is.

De Resultaten: Het Vet Wegsnijden
Toen ze dit testten op de MATILDA-dataset (een collectie stadkaarten met 100 huizen), waren de resultaten indrukwekkend. Hun methode slaagde erin om 95% van de wegen weg te snijden! Dat betekent dat in plaats van een miljoen verbindingen te controleren, de computer er slechts ongeveer 50.000 hoefde te controleren. Nog beter: de route die ze vonden was nog steeds ongelooflijk dicht bij de perfecte route — meestal binnen 1% van het best mogelijke antwoord.

Ze testten het ook op de TSPLIB-benchmark, die veel grotere steden bevat met tot wel 2.392 huizen. Op deze gigantische kaarten was de methode nog agressiever en sneed het meer dan 99% van de wegen weg, terwijl het verschil in oplossing onder de 1% bleef.

Wat Ze Afwezen en Wat Ze Niet Deden
De auteurs waren zeer duidelijk over wat niet goed genoeg werkte. Ze argumenteerden expliciet tegen het uitsluitend vertrouwen op vaste geometrische regels (zoals alleen de dichtstbijzijnde buren kiezen), omdat dergelijke methoden de specifieke "persoonlijkheid" van elke kaart missen. Ze merkten ook op dat hoewel andere AI-methoden proberen de hele route vanaf nul op te bouwen, deze vaak moeite hebben met generaliseren (goed werken op nieuwe, onbekende kaarten) of te ingewikkeld zijn. Hun aanpak is anders: ze bouwen de route niet; ze maken de kaart alleen maar schoner zodat een standaard solver de route veel sneller kan vinden.

Hoe Zeker Zijn Ze?
De auteurs zijn vrij zelfverzekerd over hun cijfers omdat ze daadwerkelijke experimenten hebben uitgevoerd. Ze hebben niet zomaar geraden; ze hebben hun methode getest op echte datasets (MATILDA en TSPLIB) en deze direct vergeleken met andere methoden zoals "SGN" en "Fitzpatrick".

Op MATILDA: Hun methode had consequent de kleinste foutmarge (optimality gap) en de hoogste weg-snijrate (pruning rate).
Op TSPLIB: Ze lieten zien dat naarmate de steden groter werden, hun methode zelfs beter werd in het wegknippen van wegen zonder aan nauwkeurigheid in te boeten.
Snelheid: Omdat ze zoveel wegen hadden verwijderd, loste de computer de problemen veel sneller op. In hun tests was hun methode de snelste van de hele groep.

Ze hebben ook een "wat als"-test uitgevoerd (een ablatie-studie) waarbij ze delen van hun systeem hebben verwijderd. Toen ze de "Delaunay" ruwe versie weghaalden, daalde de prestatie. Toen ze de "slimme vragen" (de kenmerken) weghaalden, daalde de prestatie ook. Dit bewijst dat elk deel van hun systeem daadwerkelijk belangrijk werk verricht.

De Kern van het Verhaal
Het artikel suggereert dat door klassieke geometrie te combineren met een moderne, op leren gebaseerde AI die de specifieke vorm van het probleem begrijpt, je het oplossen van deze enorme bezorgpuzzels veel sneller en gemakkelijker kunt maken. Ze hebben het Traveling Salesman Problem nog niet voor altijd "opgelost" (het blijft een lastige noot om te kraken!), maar ze hebben een zeer effectieve manier getoond om het probleem te verkleinen zodat het hanteerbaar wordt, zelfs voor enorme steden. Ze richten zich momenteel alleen op deze specifieke soorten kaarten (Euclidische TSP) en hebben het nog niet geprobeerd op andere soorten puzzels, maar de resultaten tot nu toe zijn zeer veelbelovend.

Technische Samenvatting: GES-TSP: Graph Edge Sparsification voor TSP

Probleemstelling
Het Traveling Salesman Problem (TSP), in het bijzonder de Euclidische variant (ETSP), is een klassiek NP-zwaar combinatorisch optimalisatieprobleem. Hoewel exacte methoden (bijv. CPLEX, SCIP) instanties tot optimaliteit kunnen oplossen, worden ze computationeel onhaalbaar voor grootschalige instanties vanwege de kwadratische groei van randen ( $O(n^2)$ ) in de volledige graafformulering. Traditionele technieken voor graaf-sparsificatie, zoals $k$ -nearest neighbor (KNN) grafen en Delaunay-triangulatie, reduceren de zoekruimtes met behulp van vaste geometrische heuristieken. Deze methoden slagen er echter vaak niet in om de instantiespecifieke structurele informatie volledig te benutten, wat leidt tot ofwel redundante randen, ofwel het weglaten van cruciale probleemspecifieke structuren. Daartegenover staan recente op leren gebaseerde end-to-end TSP-solvers, die vaak lijden onder beperkte generalisatie en complexe architecturen. De kernuitdaging die dit artikel aanpakt, is hoe men adaptief een ijle graaf kan genereren die de computationele overhead aanzienlijk vermindert, terwijl een hoogwaardige oplossing behouden blijft en een sterke generalisatie over verschillende instantieverdelingen wordt gehandhaafd.

Methodologie
De auteurs stellen GES-TSP (Graph Edge Sparsification for TSP) voor, een op leren gebaseerd framework dat geometrische structuren integreert met Graph Neural Networks (GNN's) om veelbelovende randen te identificeren. De methodologie verloopt via vier belangrijke fasen:

Constructie van een grove graaf: Om de computationele last van het trainen op volledige grafen te verminderen, construeert de methode eerst een grove ijle graaf met behulp van Delaunay-triangulatie. Deze geometrische structuur behoudt lokale nabijheidsrelaties en bevat $O(n)$ randen, wat dient als een sterke initiële kandidaatverzameling die aanzienlijk kleiner is dan de volledige graaf.
Kenmerkconstructie: Het model maakt gebruik van een vierdimensionale featurevector voor elke rand $(i, j)$ $(i, j)$ :
- Euclidische afstand ( $d_{ij}$ ): De fundamentele kostenmetriek.
- KNN-indicator ( $KNN_{ij}$ ): Een binaire feature die aangeeft of knopen wederzijdse $k$ -nearest neighbors zijn, wat de lokale dichtheid vastlegt.
- Q-waarde ( $Q_{ij}$ ): Een genormaliseerde metriek die de lengte van een rand vergelijkt met de kortste rand verbonden aan knoop $i$ , wat een fijnmazigerere maatstaf biedt voor lokale randkwaliteit dan de binaire KNN.
- IMST (Iterative Minimum Spanning Tree): Een globale feature afgeleid door iteratief MST's te berekenen en te verwijderen, genormaliseerd om schaalinvariantie over verschillende graafgroottes te garanderen.
GNN-inferentie: Een Graph Attention Network (GAT) wordt ingezet om de belangrijkheid van randen te voorspellen. Het model gebruikt een attention-mechanisme om buurinformatie te aggregeren, waarbij zowel knoop-embeddings als de bovengenoemde edge-features worden opgenomen. De output is een score voor elke rand, getraind als een binaire classificatietaak (inclusie van de rand in de optimale tour) met behulp van binary cross-entropy loss met klasse-imbalansweging.
Generatie van ijle graaf en oplossing: Randen worden gefilterd op basis van een score-drempelwaarde. Cruciaal is dat om de existentie van een haalbare oplossing te garanderen, randen uit een Christofides-algoritme oplossing gedwongen worden opgenomen in de ijle graaf. Dit garandeert connectiviteit en de aanwezigheid van ten minste één geldige Hamiltoniaanse cyclus. De resulterende ijle graaf wordt vervolgens doorgegeven aan een exacte solver (SCIP) om de uiteindelijke tour te berekenen.

Belangrijkste Bijdragen

Hybride Framework: Het artikel introduceert een nieuwe aanpak die deterministische geometrische heuristieken (Delaunay-triangulatie, Christofides) combineert met datagestuurd leren (GAT) om een robuuste sparsificatie-pipeline te creëren.
Adaptieve Feature Engineering: De auteurs stellen een specifieke set edge-features voor, inclusief de Q-waarde en genormaliseerde IMST, die ontworpen zijn om zowel lokale structurele kwaliteit als globale grafeigenschappen effectief vast te leggen.
Garantie van Haalbaarheid: In tegenstelling tot sommige op leren gebaseerde pruning-methoden die het risico lopen de graaf te ontkoppelen, integreert GES-TSP Christofides-randen om wiskundig te garanderen dat de geprunede graaf oplosbaar blijft.
Generalisatie: De methode vertoont sterke generalisatiecapaciteiten en presteert goed op zowel de synthetische MATILDA-dataset als de real-world TSPLIB-benchmark zonder opnieuw te hoeven trainen voor specifieke instantiegroottes.

Experimentele Resultaten
Experimenten werden uitgevoerd op de MATILDA-dataset (verschillende distributies van 100-node instanties) en de TSPLIB-benchmark (instanties variërend van 130 tot 2392 knopen).

Pruning Rate: GES-TSP bereikt aanzienlijk hogere pruning rates vergeleken met baseline-methoden (SGN en Fitzpatrick et al.). Op de MATILDA-dataset pruneert het tot wel 94% van de randen. Op grootschalige TSPLIB-instanties (bijv. pcb1002, vm1748, pr2392) overstijgt de pruning rate de 99%.
Oplossingskwaliteit: Ondanks agressieve pruning behoudt de methode een nauwe optimaliteitskloof (optimality gap). Op MATILDA is de gemiddelde gap 0,10% (vs. 0,68% voor SGN en 0,17% voor Fitzpatrick). Op TSPLIB blijft de gap onder de 1%, zelfs voor de grootste instanties.
Efficiëntie: De hoge pruning rates vertalen zich naar significante versnellingen. GES-TSP presteert consistent beter dan de baselines in rekentijd, wat aantoont dat de verminderde graafgrootte ervoor zorgt dat exacte solvers veel sneller kunnen draaien.
Ablatie-studies: Het verwijderen van de Delaunay grove filter of het vervangen ervan door KNN vermindert de pruning rate met ongeveer 3–5%. Feature-ablatie bevestigt dat de KNN- en IMST-features de meest impactvolle zijn, terwijl de Q-waarde en afstand-features de nodige verfijningen bieden.

Betekenis en Claims
Het artikel claimt dat GES-TSP een praktische en effectieve oplossing biedt voor het schalen van exacte TSP-solvers naar grote instanties. Door de graafgrootte met meer dan 95% (en tot 99% in sommige gevallen) te verminderen terwijl de oplossingskloof binnen 1% blijft, overbrugt de methode de kloof tussen de schaalbaarheid van heuristieken en de optimaliteitsgaranties van exacte methoden. De auteurs benadrukken dat hun aanpak erin slaagt om geometrische structurele informatie te gebruiken om het leren te sturen, wat resulteert in een systeem dat goed generaliseert over verschillende datadistributies en probleemmaten. Het werk onderstreept het potentieel van het integreren van geometrische heuristieken met Graph Neural Networks voor combinatorische optimalisatie, hoewel de auteurs nederig opmerken dat het huidige framework beperkt is tot TSP en nog niet is uitgebreid naar andere combinatorische problemen.

Technische Samenvatting: GES-TSP: Graph Edge Sparsification voor TSP

Meer zoals dit