Das Problem des Handelsreisenden beschäftigt sich damit, die kürzeste Rundtour zwischen einer Anzahl an Orten zu finden, dabei jeden Ort nur einmal zu besuchen und schließlich wieder zum Ausgangsort zurückzukehren. Im beigefügten Video zeigen wir einen einfachen Algorithmus, der einen der gängigen Optimierungsansätze verwendet um diese kürzeste Route zwischen den Mittelpunkten aller Länder zu finden. Die kürzeste Route kann die geographisch kürzeste sein, oder die schnellste oder die kosteneffizienteste. Man kann auch andere Parameter (oder Kombinationen von Parametern) optimieren - das Problem findet nicht nur dann Anwendung, wenn es um die Planung von Rundreisen geht.
Logistik - also der effiziente Transport und die zeitgerechte Zustellung von Gütern - ist natürlich ein Hauptanwendungsgebiet. Aber auch bei der Herstellung von Halbleiterplatten, die das Bohren von tausenden kleinen Löchern erfordert, spart eine optimierte Route des Bohrkopfs über die Platte nicht nur Zeit, sondern auch Geld. Natürlich könnte man die Lösungsansätze für dieses mathematische Problem genauso auf die Optimierung der eigenen Weihnachstshoppingroute anwenden. Für eine kleine Anzahl an Orten ist es noch machbar, alle möglichen Routen zu berechnen, zu vergleichen, und dann die beste zu finden. Allerdings gibt es schon bei 10 Orten 10! (also 3,628,800) mögliche Rundtouren. Für eine große Anzahl an zu besuchenden Orten sind also selbst die besten Computer nicht fähig, in halbwegs kurzer Zeit eine exakte Lösung zu finden. Deshalb wurden bereits viele verschiedene Annäherungen erarbeitet, um wenn auch nicht die beste, dann eine der besten Lösungen zu finden. Das Christkind muss über eine ganz besonders gute Lösung für das Problem des Handelsreisenden verfügen um in einem einzigen Abend alle Haushalte in Österreich besuchen zu können…
Weiterführende Links
10 Lines Of Coding (as shown in video): https://ericphanson.com/blog/2016/the-traveling-salesman-and-10-lines-of-python/
Über die Autoren
Anna Köferle studierte Biochemie in Oxford und machte danach ihr Doktorat am University College London. Sie interessiert sich ganz besonders für Genregulierung, Epigenetik, und alles was mit der Genschere “CRISPR” zu tun hat. Seit sie vor zwei Jahren eine PostDoc-Stelle an der Ludwig-Maximilians-Universität München angetreten hat, kommt sie auch öfters mit Themen aus der Neurobiologie in Kontakt.
Als Architekt hat sich Ralf Bliem auf generatives Entwerfen und modulares Design spezialisiert. Er hat and der TU Wien und TU Berlin Architektur studiert und in Berlin sowie in Wien in renommierten Architekturbüros gearbeitet. Ralf ist Mitbegründer von Biotop und arbeitet zur Zeit mit Biotop an modularen Laboren und einigen weiteren interessanten Aufgaben.