Handelsreizigersprobleem

Het handelsreizigersprobleem is een van de bekendste problemen in de informatica en het operationele onderzoek. Het wordt vaak TSP genoemd, een afkorting van de Engelse benaming travelling salesman problem. Het kan als volgt worden geformuleerd:

Gegeven $n$ steden samen met de afstand tussen ieder paar van deze steden, vind dan de kortste weg die een keer langs iedere stad komt en eindigt bij de eerste stad.^[1]

Het probleem is een onderdeel van de grafentheorie.

Formeel is de invoer van het probleem een volledige, gewogen graaf. De oplossing van het probleem is een pad door de graaf dat iedere knoop precies één keer aandoet, begint en eindigt in dezelfde knoop, en een minimale totale lengte heeft. De eis dat elke knoop precies één keer doorlopen wordt, zorgt ervoor dat elke rondreis hetzelfde aantal stappen bevat, wat mogelijk is omdat de invoer een volledige graaf is, waarin elke knoop in één stap vanuit elke andere knoop bereikt kan worden. Elke samenhangende graaf kan volledig worden gemaakt door een (gewogen) transitieve afsluiting uit te voeren.

Toepassingen bewerken

Het algoritme dat de berekening uitvoert om deze weg te vinden wordt bijvoorbeeld bij het ontwerpen van printplaten gebruikt. De rechtstreekse manier om dit op te lossen is alle mogelijke routes na te gaan en ze te vergelijken, maar aangezien het aantal combinaties $n!$ bedraagt wordt dit snel onmogelijk voor meer dan ca. 25 steden. Er bestaan wel efficiënte algoritmes die een goede oplossing geven, maar of deze de beste is valt niet met zekerheid te zeggen.

In 1998 berekenden wiskundigen van de Universiteit van Princeton de exacte oplossing voor 15.112 steden in Duitsland. De oplossing kostte 22,6 jaar computertijdequivalent op een enkele Alpha-processor van 500 MHz. Maar de berekeningen werden op een netwerk van 110 processors uitgevoerd.^[2] In mei 2004 is de oplossing voor het handelsreizigersprobleem met een afstand van ongeveer 72.500 km^[3] gevonden voor de 24.978 plaatsen in Zweden. Ook deze berekening werd door meerdere computers parallel uitgevoerd en zou op een enkele 2,8GHz-Xeon-computer 84,8 jaar geduurd hebben.^[4]

Complexiteit bewerken

Het handelsreizigersprobleem is NP-moeilijk. De beslissingsvariant van het probleem (gegeven de onderlinge afstanden tussen de steden, bestaat er een oplossing die korter is dan een gegeven maximum afstand?) is NP-volledig.

Het probleem lijkt op het Chinese postbodeprobleem. Bij het handelsreizigersprobleem moeten echter alle plaatsen worden aangedaan, terwijl bij het Chinese postbodeprobleem alle wegen tussen de verschillende plaatsen moeten zijn gebruikt. Het Chinese postbodeprobleem is niet NP-moeilijk.

Bronnen

(en) The travelling salesman problem

Voetnoten

↑ Elaine Rich. Automata, Computability and Complexity, Theory and Applications. Pearson Prentice Hall, 2008.
↑ (en) Solution of a 15,112-city Traveling Salesman Problem
↑ (en) Optimal Tour of Sweden. Gearchiveerd op 26 februari 2023.
↑ Sweden Computation. math.uwaterloo.ca. Gearchiveerd op 29 oktober 2021. Geraadpleegd op 8 juni 2023. "The cumulative CPU time used in the five branch-and-cut runs and in the cutting-plane procedures for the five root LPs was approximately 84.8 CPU years on a single Intel Xeon 2.8 GHz processor."

[1] Elaine Rich. Automata, Computability and Complexity, Theory and Applications. Pearson Prentice Hall, 2008.

[2] (en) Solution of a 15,112-city Traveling Salesman Problem

[3] (en) Optimal Tour of Sweden. Gearchiveerd op 26 februari 2023.

[4] Sweden Computation. math.uwaterloo.ca. Gearchiveerd op 29 oktober 2021. Geraadpleegd op 8 juni 2023. "The cumulative CPU time used in the five branch-and-cut runs and in the cutting-plane procedures for the five root LPs was approximately 84.8 CPU years on a single Intel Xeon 2.8 GHz processor."

[1]

[2]

[3]

[4]