WIE DAS ‘TSP’ UND OSTERN ZUSAMMENHÄNGEN

BLOG – NEWS, PRODUKTUPDATES UVM.

29.
März

| Frohe Ostern – oder wie der Osterhase durch Smartlane einen stressfreieren Tag bekommen könnte! |

Das Problem kennt vermutlich jeder: Der Osterhase – ein um diese Jahreszeit begehrter pelziger Freund mit langen Ohren – muss alle Kinder (zumindest in christlich geprägten Teilen dieser Welt) innerhalb eines Tages besuchen und diverse Dinge vor Ort ablegen; noch besser: verstecken. Doch wie soll das zu schaffen sein? Wir wissen es nicht! Allein in Deutschland leben ca. 11 Mio. Kinder unter 14 Jahren (Quelle), die mit Osternestern und Schokoladeneiern versorgt werden wollen.

Die Informatik kann aber einen Beitrag dazu leisten, dass es für das arme Tier nicht ganz so stressig wird. Durch eine optimierte Planung können hier ordentlich Zeit und vor allem aber auch unnötige Hoppelwege eingespart werden. Kern des Themas ist das sog. Travelling Salesman Problem – oder ordentlich und politisch korrekt gegendert: das Travelling Salesperson Problem, kurz TSP. Dieses befasst sich mit der Optimierung der Besuchsreihenfolge verschiedener Orte, so dass unnötige Umwege vermieden werden und die kürzestmögliche Strecke gefunden wird, die alle gewünschten Stationen beinhaltet; außerdem sollte das kleine Häschen auch wieder dort ankommen, wo es angefangen hat zu hoppeln.

Das dahinterstehende mathematische Problem wird seit den 1930er Jahren wissenschaftlich untersucht. Da es bei zu vielen Stationen keine Lösung gibt, die in endlicher Zeit zu berechnen ist, wird auf diverse Hilfsmittel, sog. Heuristiken zurückgegriffen, um zumindest sehr nahe an ein mögliches Optimum heranzukommen. Man kann sich vorstellen, wenn es bereits bei 10 Stationen ca. 3,6 Mio. mögliche Varianten gibt, dass 11 Mio. Stationen sehr aufwändig in der Berechnung sind; ganz zu schweigen von weiteren Parametern wie der Zeit, die der Hase vor Ort zum Verstecken der Eier benötigt oder der Berücksichtigung des vielen Verkehrs auf deutschen Straßen während der Osterzeit.

Im Vergleich zu unserem pelzigen Freund würden wir Menschen ohne ordentliche Rechenkapazitäten schnell an unsere Grenzen stoßen. Daher sind wir stets dabei unsere Algorithmen zu verbessern sowie weitere Parameter zu integrieren, um noch bessere Tourenplanungs-Ergebnisse zu liefern. Unser wichtigstes Ziel ist es nämlich, dem Osterhasen so viel Freiraum zu schaffen, dass er am Nachmittag des Ostersonntags noch Zeit dazu hat auch die Erwachsenen mit schokoladigen Köstlichkeiten zu versorgen und danach natürlich noch sich selbst.

In diesem Sinne – FROHE OSTERN!

#Smartlane #froheOstern #TSP #TravellingSalesmanProblem #Tourenplanung

Social Media