Handelsreizigersprobleem

Het Reizende Verkopersprobleem (vaak TSP genoemd) is een klassiek algoritmisch probleem op het gebied van computerwetenschappelijk en operationeel onderzoek. Het is gericht op optimalisatie. In deze context betekent betere oplossing vaak een oplossing die goedkoper, korter of sneller is. TSP is een wiskundig probleem. Het wordt het gemakkelijkst uitgedrukt als een grafiek die de locaties van een set van knooppunten beschrijft.

Het reizende verkopersprobleem werd in de jaren 1800 gedefinieerd door de Ierse wiskundige W.R. Hamilton en door de Britse wiskundige Thomas Kirkman. Hamilton's Icosian Game was een recreatieve puzzel gebaseerd op het vinden van een Hamiltoniaanse cyclus. De algemene vorm van het TSP lijkt voor het eerst te zijn bestudeerd door wiskundigen in de jaren dertig van de vorige eeuw in Wenen en op Harvard, met name door Karl Menger. Menger definieert het probleem, beschouwt het voor de hand liggende brute-force-algoritme en observeert de niet-optimiteit van de dichtstbijzijnde heuristiek:

We geven met messenger probleem aan (aangezien deze vraag in de praktijk door elke postbode, in ieder geval ook door veel reizigers, moet worden opgelost) de taak om, voor ﬁnitely veel punten waarvan de afstanden paarsgewijs bekend zijn, de kortste route te vinden die de punten met elkaar verbindt. Natuurlijk is dit probleem op te lossen door eindig veel proeven. Regels die het aantal proeven onder het aantal permutaties van de gegeven punten zouden duwen, zijn niet bekend. De regel dat men eerst van het beginpunt naar het dichtstbijzijnde punt moet gaan, dan naar het dichtstbijzijnde punt, etc., levert over het algemeen niet de kortste route op.

Hassler Whitney van de Universiteit van Princeton introduceerde de naam reizende verkopersprobleem kort daarna.

Een verkoper wil alle steden bezoeken,A, B, C en D. Wat is de beste manier om dit te doen (goedkoopste vliegtickets, en minimale reistijd)?

Optimale route van een verkoper die de 15 grootste steden van Duitsland bezoekt. De getoonde route is de kortste van de 43.589.145.600 mogelijke routes.

William Rowan Hamilton

Het probleem vermelden

Het Reizende Verkopersprobleem beschrijft een verkoper die tussen N-steden moet reizen. De volgorde waarin hij dat doet is iets waar hij niet om geeft, zolang hij maar een keer op bezoek komt tijdens zijn reis en eindigt waar hij in het begin was. Elke stad is verbonden met andere steden in de buurt, of knooppunten, met vliegtuigen, of met de weg of het spoor. Aan elk van die verbindingen tussen de steden zijn een of meer gewichten (of de kosten) verbonden. De kosten beschrijven hoe "moeilijk" het is om deze rand te overbruggen op de grafiek, en kunnen bijvoorbeeld worden gegeven door de kosten van een vliegticket of treinkaartje, of misschien door de lengte van de rand, of de tijd die nodig is om het traject af te leggen. De verkoper wil zowel de reiskosten als de afstand die hij aflegt zo laag mogelijk houden.

Het Reizende Verkopersprobleem is typerend voor een grote klasse van "harde" optimalisatieproblemen die wiskundigen en computerwetenschappers al jaren intrigeren. Het belangrijkste is dat het toepassingen heeft in de wetenschap en techniek. Zo is het bijvoorbeeld bij de vervaardiging van een printplaat belangrijk om de beste volgorde te bepalen waarin een laser duizenden gaten zal boren. Een efficiënte oplossing voor dit probleem verlaagt de productiekosten voor de fabrikant.

Moeilijkheidsgraad

In het algemeen is het probleem van de reizende verkoper moeilijk op te lossen. Als er een manier is om dit probleem op te splitsen in kleinere componentproblemen, zullen de componenten minstens zo complex zijn als de oorspronkelijke. Dit is wat computerwetenschappers NP-harde problemen noemen.

Veel mensen hebben dit probleem bestudeerd. De eenvoudigste (en duurste) oplossing is om gewoon alle mogelijkheden uit te proberen. Het probleem hierbij is dat je voor N-steden (N-1) factoriële mogelijkheden hebt. Dit betekent dat er voor slechts 10 steden meer dan 180 duizend combinaties te proberen zijn (omdat de startstad is gedefinieerd, kunnen er permutaties zijn op de overige negen). We tellen slechts de helft omdat elke route een gelijke route in omgekeerde richting heeft met dezelfde lengte of kosten. 9! / 2 = 181 440

Exacte oplossingen voor het probleem kunnen worden gevonden, met behulp van vertakkingen en gebonden algoritmen. Dit is momenteel mogelijk voor maximaal 85.900 steden.
Heuristische benaderingen gebruiken een aantal leidende regels voor de selectie van het volgende knooppunt. Maar omdat heuristiek resulteert in benaderingen, zullen ze niet altijd de optimale oplossing geven, hoewel kwalitatief hoogwaardige, toelaatbare heuristiek een nuttige oplossing kan vinden in een fractie van de tijd die nodig is voor een volledige brute kracht van het probleem. Een voorbeeld van een heuristiek voor een knooppunt zou een opsomming zijn van het aantal niet-bezochte knooppunten die "dicht bij" een aangesloten knooppunt liggen. Dit zou de verkoper kunnen aanmoedigen om een groep van nabijgelegen knooppunten te bezoeken die samen gegroepeerd zijn, voordat hij naar een ander natuurlijk cluster in de grafiek gaat. Zie Monte Carlo-algoritmen en Las Vegas-algoritmen.

Vragen en antwoorden

V: Wat is het handelsreizigersprobleem?

A: Het Traveling Salesman Problem (TSP) is een klassiek algoritmisch probleem op het gebied van informatica en operationeel onderzoek. Het is gericht op optimalisatie, waarbij betere oplossingen vaak goedkopere, kortere of snellere oplossingen betekenen.

V: Hoe wordt TSP uitgedrukt?

A: TSP is het gemakkelijkst uit te drukken als een grafiek die de locaties van een reeks knooppunten beschrijft.

V: Wie heeft het TSP voor het eerst gedefinieerd?

A: Het travelling salesman problem werd in de jaren 1800 gedefinieerd door de Ierse wiskundige W. R. Hamilton en de Britse wiskundige Thomas Kirkman.

V: Wie heeft het in de jaren 1930 verder bestudeerd?

A: In de jaren 1930 hebben de wiskundigen Karl Menger in Wenen en Harvard het probleem verder bestudeerd.

V: Wat introduceerde Hassler Whitney kort daarna?

A: Hassler Whitney van de Princeton University introduceerde de naam "reizend koopmanprobleem" kort na de definitie ervan.

V: Wat betekent "betere oplossing" in deze context?

A: In deze context betekent betere oplossing vaak een oplossing die goedkoper, korter of sneller is.

V: Welk algoritme werd door Menger voor de hand liggend geacht toen hij het TSP bestudeerde?

A: Menger beschouwde een voor de hand liggend brute-force algoritme bij het bestuderen van TSP en merkte op dat het gebruik van de dichtstbijzijnde buurheuristiek niet altijd optimale resultaten oplevert.