Handelsreiziger

Maandag, 2 december 2002
Er bestaat geen perfecte oplossing voor het probleem van de rondreizende verkoper.

Wat is de kortst mogelijke route
voor een verkoper die vanaf thuis vertrekt,
langs een aantal steden moet reizen,
en 's avonds naar huis terugkeert?

Bekijk de routeplanner voor Nederland die via punten sorteert.
Een optimale route langs 5 punten

Deze demo van het handelsreizigers probleem heeft een Java plug-in nodig.
In deze browser is deze Java plug-in nog niet actief.

Advies: Download de gratis Java plug-in van:
java.sun.com/getjava/download.html

Het probleem van de handelsreiziger is NP-complete.
Aantal mogelijkheden groeit exponentieel met het aantal punten
Aantal mogelijkheden
neemt exponentieel toe
met het aantal punten.

Er is één algoritme bekend dat de optimale oplossing bepaalt: met brute kracht alle mogelijkheden aflopen. Voor grotere problemen is dat ondoenlijk door de combinatorische explosie van het aantal mogelijkheden.

Toch ziet u hierboven een Java applet die razendsnel een uitstekende oplossing zoekt, zelfs langs honderden of zelfs duizend punten.

Hoe kan dat?

De applet hierboven toont niet altijd de optimale oplossing, wel altijd eentje die op z'n minst uitstekend is. Soms een 10, meestal een 9,9!

Het achterliggende geavanceerde algoritme is behoorlijk complex. Het heeft mij diverse sessies met de kikker gekost om het uit te denken. Het algoritme vraagt aardig wat rekenwerk, maar bepaalt toch razendsnel een uitstekende oplossing, een route met lage, of zelfs mimimale kosten.

Toepassingen

  • routeplanning voor zakenmensen, storingsmonteurs, bezorgdiensten, vliegtuigen, schepen, containers, trucks en bussen langs verschillende locaties,
  • werkvolgordeplanning voor robots die werk op een aantal locaties moeten repeteren,
  • picklist om goederen zo snel mogelijk uit een magazijn te halen.
Heeft u een situatie waar dit algoritme kan helpen om uw bedrijf te optimaliseren? Neem contact op met SUMit!

Tot de volgende week,
Henk Jan Nootenboom

Nieuw op het web: Turnvereniging ODIN, Amstelveen.
Proficiat Web designer Lassie.