🔢 mathematics

A Surface-Based Formulation of the Traveling Salesman Problem

Dit artikel introduceert een exacte oppervlaktegebaseerde formulering voor het Symmetrische Reisende Verkoopprobleem die, in plaats van randen te selecteren, een oppervlak van verbonden driehoeken construeert waarbij de rand de tour vormt, en waarbij globale connectiviteit wordt gewaarborgd via boombeperkingen en lokale connectiviteit via Euler-characteristiekbeperkingen.

Oorspronkelijke auteurs: Yılmaz Arslanoğlu

Gepubliceerd 2026-03-03

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yılmaz Arslanoğlu

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 postbode bent in een grote stad en je moet elke straat een keer afleggen om alle brieven te bezorgen, maar je wilt de kortste route vinden. Dit is het beroemde "Reizende Verkoper"-probleem (TSP).

Meestal proberen computers dit op te lossen door te kijken naar lijnen: "Welke straten (lijnen) moet ik kiezen om een rondje te maken?" Het probleem is dat dit heel lastig is voor een computer, omdat er zoveel mogelijke combinaties zijn dat het snel vastloopt.

De auteur van dit artikel, Yılmaz Arslanoğlu, heeft een slimme nieuwe manier bedacht. In plaats van te kijken naar de lijnen, kijkt hij naar vlakken (driehoekjes).

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Van Lijnen naar Deken

Stel je voor dat de stad niet bestaat uit straten, maar uit een groot tapijt van driehoekige stukken stof.

De oude manier: Je probeert een touw te leggen dat precies langs de rand van de stad loopt. Je kiest stukjes touw (lijnen) en hoopt dat ze een perfect rondje vormen.
De nieuwe manier (de "Oppervlakte-methode"): Je pakt een doos vol driehoekige lapjes stof. Je plakt deze lapjes aan elkaar tot je een deken (een oppervlak) hebt.
- Het mooie is: als je deze deken zo legt dat hij perfect op de grond past, vormt de rand van de deken vanzelf de kortste route voor de postbode.

Je hoeft de route niet direct te tekenen; je bouwt gewoon een deken, en de rand van die deken is de oplossing.

2. De "Knikker" en de "Gaten"

Waarom werkt dit?
Stel je voor dat je een deken van driehoekjes maakt.

Als twee driehoekjes naast elkaar liggen, is de lijn ertussen binnenin de deken. Die lijn telt niet mee voor de postbode, want die loopt er niet over.
Alleen de lijnen aan de buitenrand van de deken zijn de straten waar de postbode overheen moet.

De computer probeert nu een deken te bouwen die zo klein mogelijk is (zodat de rand kort is), maar die wel één groot stuk moet zijn.

3. De "Boom" en de "Magische Regel"

Om ervoor te zorgen dat de computer geen rare deken bouwt (bijvoorbeeld eentje met gaten erin, of eentje die in een knoop zit), gebruikt de auteur twee regels:

De Boom-regel: De driehoekjes moeten aan elkaar zitten als de takken van één grote boom. Als je de deken zou "opblazen", zou hij niet in stukken moeten vallen. Dit zorgt ervoor dat de route één groot rondje is.
De "Ogen" van de stad (Euler-regel): Kijk naar een enkel huisje in de stad. De driehoekjes die om dat huisje heen liggen, moeten een perfect rondje vormen. Als ze dat niet doen (bijvoorbeeld als ze een "stervorm" maken met een gat erin), dan is het geen goede deken. De computer controleert dit voor elk huisje.

4. Waarom is dit slim?

Voor kleine steden: Als je alle mogelijke driehoekjes gebruikt, is dit een perfecte manier om de exacte kortste route te vinden.
Voor grote steden: Het is te veel werk om alle driehoekjes te bekijken. Maar als je alleen kijkt naar de driehoekjes die er "logisch" uitzien (zoals een net van lijnen dat de dichtstbijzijnde buren verbindt, wat een Delaunay-triangelatie heet), werkt het als een razendsnelle en slimme gissing.

Samenvatting in één zin

In plaats van te proberen een touw om de stad te leggen, bouwt deze methode een puzzel van driehoekjes in het midden van de stad; de rand van die puzzel is dan automatisch de kortste route voor de postbode.

Het is alsof je niet de weg zoekt door te kijken naar de weg, maar door het landschap zo te vormen dat de weg vanzelf ontstaat!

Titel: Een oppervlakte-gebaseerde formulering van het Traveling Salesman Problem (TSP)

1. Het Probleem

Het klassieke Traveling Salesman Problem (TSP) wordt doorgaans gemodelleerd als een grafprobleem waarbij het doel is om een Hamilton-cyclus met minimaal gewicht te vinden door een subset van randen ( $E' \subseteq E$ ) te selecteren.

Huidige uitdagingen: Compacte rand-gebaseerde modellen (zoals MTZ of stroom-gebaseerde modellen) vereisen vaak complexe, exponentiële "subtour-eliminerende" constraints om globale connectiviteit te garanderen. Alternatieven zoals flow-constraints kunnen rekenkundig zwaar zijn of zwakke relaxaties bieden.
De kernvraag: Kan men het TSP benaderen vanuit een topologisch perspectief in plaats van een puur graf-theoretisch perspectief, om zo de noodzaak voor subtour-eliminatie te omzeilen?

2. Methodologie: Van Randen naar Oppervlakken

De auteur introduceert een fundamenteel perspectiefverschil: in plaats van een 1-dimensionale cyclus (randen) te bouwen, wordt een 2-dimensionaal oppervlak (een verzameling verbonden driehoeken) geconstrueerd waarvan de rand de optimale toer vormt.

De Incidentiegrafiek (Bipartite Graph):
Het model bouwt een bipartiete grafiek $B = (U \cup W, A)$ :

Knopen $U$ (Driehoeken): Een kandidaat-set van driehoeken $T \subseteq \binom{V}{3}$ .
Knopen $W$ (Randen): De set van oorspronkelijke randen van de TSP-grafiek.
Arcs $A$ : Een verbinding tussen een driehoek en een rand als de rand in de driehoek voorkomt.

Doelfunctie en Rand-Annulering:
De doelstelling is om een samenhangende subset van driehoeken te selecteren die de totale lengte van de geïnduceerde rand minimaliseert.

Er wordt een kostenfunctie gekoppeld aan randen ( $c(e) = 2L_e$ ) en een winst aan incidenties ( $p(t,e) = L_e$ ).
Mechanisme: Als een rand door twee geselecteerde driehoeken wordt gedeeld (interne rand), heffen de kosten en winsten elkaar op ( $2L_e - L_e - L_e = 0$ ). Alleen de randen die slechts door één driehoek worden gedeeld (de rand van het oppervlak) dragen bij aan de totale kosten.
Het minimaliseren van de netto-kosten is dus equivalent aan het minimaliseren van de lengte van de toer.

Topologische Beperkingen (MILP):
Om te garanderen dat de geselecteerde driehoeken een geldig oppervlak vormen waarvan de rand één enkele Hamilton-cyclus is, worden vier structurele constraints toegepast:

Globale Boom-connectiviteit: De geselecteerde subgrafiek moet een enkele samenhangende boom vormen. Dit zorgt ervoor dat het oppervlak topologisch een schijf is (eenvoudig samenhangend).
Cardinaliteit: Het aantal driehoeken en randen wordt vastgelegd op $N-2$ en $2N-3$ respectievelijk (gebaseerd op de Euler-karakteristiek van een gediscrreteerde schijf).
Manifold Regulariteit: Elke rand mag incident zijn op maximaal twee driehoeken (voorkomt niet-manifold structuren).
Lokale Connectiviteit (Euler-filter): Om singulariteiten (zoals "strikken" of bowties) te voorkomen, wordt voor elke stad $v$ de lokale Euler-karakteristiek van de incidentie-subgrafiek gecontroleerd: $\chi(H_v) = 1$ . Dit garandeert dat de omgeving van elke stad samenhangend is.

3. Belangrijkste Bijdragen

Equivalentie: Het bewijs van de equivalentie tussen het vinden van een minimum-gewicht Hamilton-cyclus in de volledige complexiteit en het vinden van een maximum-gewicht dual-baam in de bipartiete incidentiegrafiek.
Nieuwe MILP-formulering: Een exacte Mixed-Integer Linear Programming (MILP) formulering die subtour-eliminatie vervangt door een combinatie van een boom-constraint en een Euler-karakteristiek-filter.
Input-Decoupling: Het model behandelt de kandidaat-driehoekenset $T$ als een "black-box". Het werkt exact op de volledige set van alle mogelijke driehoeken ( $K_{All}$ ), maar is ook toepasbaar op schaarse geometrische triangulaties (zoals Delaunay of Greedy) voor heuristische toepassingen.

4. Resultaten en Validatie

De auteur heeft de formulering getest op verschillende scenario's:

Topologische Validatie: Het model slaagt erin de optimale oppervlakte te extraheren voor zowel dichte input (alle driehoeken) als schaarse input (Delaunay), zelfs in niet-metriekke ruimtes waar de driehoeksongelijkheid niet geldt.
Vergelijking met Bestaande Methodes (MTZ):
- Op TSPLIB-instanties (bijv. berlin52, st70, ch130) met Delaunay-schaarsing presteert het oppervlakte-gebaseerde model (specifiek de variant met Single-Commodity Flow) aanzienlijk beter dan de standaard Lifted-MTZ.
- Branch-and-Bound (B&B) Efficiëntie: De oppervlakte-gebaseerde Flow-variant lost veel instanties op bij de wortel van de B&B-boom (1 knoop), terwijl de Lifted-MTZ duizenden knopen nodig heeft (bijv. 16.058 knopen voor ch130).
- Schaalbaarheid: Voor grotere instanties (bijv. pcb442) blijft de oppervlakte-Flow-variant zeer efficiënt (142 knopen) in vergelijking met de MTZ-variant (23.205 knopen).
Zware Instanties:
- Op de "Hard-to-Solve" instantie Tnm199 leverde een Greedy-triangulatie als input een gap van 1,85% op, wat beter is dan de Christofides-heuristiek (5,69%) en de Delaunay-versie (6,17%). Dit toont aan dat de kwaliteit van de oplossing sterk afhankelijk is van de kwaliteit van de input-triangulatie.
- Beperking: Bij degeneratie (bijv. punten op parallelle lijnen in p100) kunnen triangulatie-gebaseerde methoden falen (gap >100%), wat aangeeft dat de keuze van de kandidaat-set cruciaal is.

5. Betekenis en Conclusie

Deze paper biedt een fundamenteel nieuwe benadering voor het TSP door de optimalisatie te verschuiven van randen naar een dual oppervlak.

Theoretische waarde: Het demonstreert dat topologische constraints (boom-connectiviteit + Euler-filter) effectief kunnen worden gebruikt om globale Hamilton-eigenschappen af te dwingen zonder expliciete subtour-eliminatie.
Praktische waarde: Hoewel het exacte model op de volledige set driehoeken computationeel onhaalbaar is voor grote $N$ , biedt het een krachtige heuristiek wanneer het wordt beperkt tot een schaarse, geometrisch zinvolle set (zoals Delaunay).
Toekomst: De methode biedt een robuust raamwerk voor het integreren van extra geometrische of topologische constraints die moeilijk te modelleren zijn in traditionele rand-gebaseerde formuleringen, zonder de kern van het model te hoeven veranderen.

Kortom, de oppervlakte-gebaseerde formulering levert, vooral in combinatie met flow-gebaseerde connectiviteitsconstraints, een sterkere relaxatie en een efficiëntere zoekruimte dan conventionele compacte MILP-modellen voor geometrische TSP-instanties.