Je hebt een aantal steden die bezocht moeten worden door een handelsreiziger in een auto. Alle steden moeten 1 keer bezocht worden en vervolgens kan de auto weer terug naar het bedrijf. Ieder paar steden heeft uiteraard een bepaalde afstand en deze afstand zorgt voor kosten in geld (meer kilometers zijn uiteraard meer dure liters benzine of diesel) en kosten in tijd (hoe groter de afstand, hoe langer de handelsreiziger onderweg is).
Het probleem voor het bedrijf is dan om de kortste route te vinden. En daar komt de wiskunde om de hoek kijken. Zijn er bijvoorbeeld bepaalde oplossingsmethoden (algoritmen) om dit soort problemen snel te kunnen oplossen?
Het handelsreizigersprobleem is een klassiek probleem met moderne toepassingen. Het gaat tegenwoordig niet meer om een handelsreiziger die een zo kort mogelijke route langs alle twaalf provinciehoofdsteden van Nederland moet maken, maar de instanties vaak veel groter (denk aan een kortste cykel langs de meer dan 600 hoofdsteden van landen op de wereld) en ook zijn de toepassingen heel uiteenlopend. Zo is een probleem waarbij ruim 3000 gaatjes in een printplaat geboord moeten worden te modelleren als handelsreizigersprobleem, waarbij de lengte van het door de boorkop af te leggen traject moet worden geminimaliseerd. Deze specifieke instanties zijn overigens met de huidige algoritmen op te lossen en opgelost.
WvR
zaterdag 15 december 2001
