Het handelsreizigersprobleem uitgelegd

Geef een handelsreiziger een lijst met steden en vraag naar de kortste reis die elke stad één keer bezoekt en weer thuis eindigt. Iedereen kan een voorgestelde route controleren, en iedereen kan een slechte route op het oog verbeteren, maar niemand kent een snelle methode die altijd de beste vindt. Het handelsreizigersprobleem is het standaardvoorbeeld van een moeilijk probleem geworden, en de methoden die zijn bedacht om het aan te pakken, plannen nu bezorgingen, boren printplaten en zetten genomen in elkaar.

Een kaart met steden die verbonden zijn door een gesloten route, met de beginstad gemarkeerd en daaronder vaag een kortere route
Een kaart met steden die verbonden zijn door een gesloten route, met de beginstad gemarkeerd en daaronder vaag een kortere route

Het probleem

Een route bezoekt elke stad precies één keer en eindigt waar ze begon; haar lengte is de som van de afstanden onderweg. De opgave is de kortste route te vinden. In de versie hier zijn de afstanden rechte lijnen op een kaart, dus van A naar C is nooit langer dan via B: dit is het metrische handelsreizigersprobleem. Het vraagstuk werd rond 1930 besproken door de wiskundige Karl Menger, en de naam raakte in de decennia daarna ingeburgerd, toen wiskundigen van de RAND Corporation het oppakten.

Karl Menger in 1970. Rond 1930 besprak hij het handelsreizigersprobleem.
Karl Menger in 1970. Rond 1930 besprak hij het handelsreizigersprobleem.

De explosie van routes

Leg de beginstad vast. Er zijn n − 1 keuzes voor de volgende stad, n − 2 voor de stad daarna, enzovoort, en elke route kan in twee richtingen worden afgelegd, dus er zijn (n − 1)! / 2 routes. Voor 10 steden zijn dat er 181.440, makkelijk voor een computer. Voor 20 zijn het er ongeveer 6 × 10¹⁶, en voor 70 zijn het er meer dan er atomen in het waarneembare heelal zijn. Snellere computers helpen weinig: elke extra stad vermenigvuldigt het werk met ongeveer n.

NP-moeilijk

In 1972 toonde Richard Karp aan dat de vraag of een graaf een rondreis door elk hoekpunt heeft, een hamiltoncykel, behoort tot een familie van NP-volledige problemen die allemaal even moeilijk zijn. Het handelsreizigersprobleem bevat die vraag, dus het is NP-moeilijk. Een snelle methode ervoor zou snelle methoden opleveren voor duizenden andere problemen in planning, logistiek en cryptografie. Of zo'n methode bestaat, is de vraag P versus NP, een van de Millennium Prize Problems.

Een exacte methode: Held–Karp

In 1962 gebruikten Michael Held en Richard Karp, en onafhankelijk van hen Richard Bellman, dynamisch programmeren. Bereken voor elke verzameling S van steden en elke stad j in S het kortste pad dat in de thuisstad begint, precies de steden van S bezoekt en in j eindigt. Elke waarde volgt uit de waarden voor S zonder j, dus de tabel wordt gevuld van kleine naar grote verzamelingen, en aan het eind komt de kortste route eruit. Er zijn ongeveer n² · 2ⁿ stappen nodig in plaats van n!, wat voor 30 steden het verschil is tussen minuten en de leeftijd van het heelal, maar het groeit nog altijd exponentieel.

Richard Bellman in 1962, gefotografeerd door Alfred Eisenstaedt. Hij gaf dynamisch programmeren begin jaren vijftig zijn naam, toen hij bij de RAND Corporation werkte.
Richard Bellman in 1962, gefotografeerd door Alfred Eisenstaedt. Hij gaf dynamisch programmeren begin jaren vijftig zijn naam, toen hij bij de RAND Corporation werkte.

Snelle constructieregels

Dichtstbijzijnde buur reist altijd naar de dichtstbijzijnde stad die nog niet bezocht is. Het is eenvoudig en snel, maar laat vaak een paar steden achter die aan het eind met lange omwegen moeten worden opgehaald, zodat de routes doorgaans ongeveer 25% langer zijn dan de beste. Invoegmethoden houden in plaats daarvan een gesloten lus aan en voegen de overige steden een voor een toe waar ze het minst kosten. In 1976 vond Nicos Christofides een constructie die op elke metrische kaart gegarandeerd hoogstens 1,5 keer het optimum is, een grens die ruim veertig jaar vrijwel onverbeterd bleef.

Een route verbeteren: 2-opt

Lokaal zoeken begint bij een willekeurige route en blijft kleine wijzigingen aanbrengen die haar korter maken. De klassieke zet, 2-opt, verwijdert twee verbindingen en verbindt de twee stukken andersom opnieuw, waardoor het stuk ertussen wordt omgekeerd. Wanneer twee verbindingen elkaar kruisen, haalt deze zet ze uit elkaar en bespaart lengte, dus een route die 2-opt niet kan verbeteren, kruist zichzelf nooit. Op willekeurige kaarten liggen 2-opt-routes doorgaans ongeveer 5% boven het optimum. Sterkere zetten die drie verbindingen verwisselen, of de methode met variabele diepte van Lin en Kernighan uit 1973, komen nog dichterbij.

Simulated annealing

Lokaal zoeken kan vastlopen in een route waarbij elke afzonderlijke zet haar slechter maakt, ook al bestaat er een veel betere route. Simulated annealing, in 1983 op dit probleem toegepast door Scott Kirkpatrick, Daniel Gelatt en Mario Vecchi, leent uit de metallurgie: het accepteert een slechtere zet met een kans die afhangt van een temperatuur, die eerst hoog is en langzaam wordt verlaagd. In het begin dwaalt de route vrij rond; aan het eind worden alleen verbeteringen geaccepteerd. Bij voldoende langzame afkoeling vindt het betrouwbaar zeer goede routes.

Probeer het zelf

Open de demo van het handelsreizigersprobleem om tot 200 steden te plaatsen: willekeurig, op een cirkel, in clusters, op een raster of waar je ook klikt. Kijk hoe dichtstbijzijnde buur zijn laatste steden laat liggen, zie hoe 2-opt elke kruising ontwart, volg de temperatuur van simulated annealing terwijl die afkoelt, en laat Held–Karp de kortste route bewijzen voor maximaal 12 steden. Alles vergelijken laat elke methode op dezelfde kaart lopen en toont hoeveel elke route boven de kortste gevonden route ligt.

Veelgestelde vragen

Waar wordt het handelsreizigersprobleem gebruikt?

Overal waar iets veel plaatsen in een efficiënte volgorde moet bezoeken: bezorg- en ophaalroutes, het pad van een boor of laser over een printplaat, de volgorde waarin een telescoop sterren waarneemt, orderpicking in een magazijn en, met andere afstanden, de volgorde van fragmenten bij het samenstellen van een DNA-sequentie.

Wat is het grootste probleem dat ooit exact is opgelost?

In 1954 bewezen George Dantzig, Ray Fulkerson en Selmer Johnson de kortste route door 49 steden in de Verenigde Staten. In 2006 bewees de solver Concorde van David Applegate, Robert Bixby, Vašek Chvátal en William Cook na jaren rekentijd de optimale route door 85.900 punten uit een chipontwerp.

Is de kortste route altijd vrij van kruisingen?

Ja, op een platte kaart met afstanden in rechte lijn. Als twee verbindingen elkaar zouden kruisen, zou het vervangen ervan door twee zijden van de vierhoek die ze vormen de route korter maken, dus een route met een kruising kan niet de kortste zijn.

Geven de heuristieken elke keer dezelfde route?

Dichtstbijzijnde buur, goedkoopste invoeging en 2-opt zoals hier gebruikt zijn deterministisch: op dezelfde steden geven ze dezelfde route. Simulated annealing begint bij een willekeurige route en doet willekeurige zetten, dus twee runs kunnen op verschillende routes eindigen, meestal van bijna dezelfde lengte.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Open de demo van het handelsreizigersprobleem