… ist der Titel des 1. Platzes des Roland-Mittermeir-Preises 2018 und wurde vom Förderverein Technische Fakultät mit EUR 1.000,–ausgezeichnet. Der Autorin und Preisträgerin, Frau Dipl.-Ing.in Anna Jellen B.Sc., wurde der Preis im Rahmen Generalversammlung 2019 übergeben und die Arbeit wird hier kurz vorgestellt:
In meiner Masterarbeit beschäftige ich mich mit einer Erweiterung des Problems des Handlungsreisenden. Diese Erweiterung wird als Problem des Handlungsreisenden mit verbotenen Nachbarschaften bezeichnet und mit TSPFN (Traveling Salesperson Problem with Forbidden Neighborhoods) abgekürzt.
Es werden gleichmäßig angeordnete Punkte betrachtet, z.B. die Mittelpunkte der Felder eines Schachbretts. Diese Anordnung von Punkten wird reguläres Gitter genannt. Die Aufgabe ist nun, ausgehend von einem beliebigen Punkt, alle anderen Punkte genau einmal zu besuchen und zum Startpunkt zurückzukehren, wobei der kürzest mögliche Weg gesucht wird. Zusätzlich gibt es noch die Bedingung, dass die Distanz zwischen je zwei aufeinanderfolgenden Punkten größer als ein vorgegebener Radius sein muss.
Dieses Problem entstammt einem Verfahren namens Laser-Beam-Melting, welches ähnlich dem 3-D-Druck ist. Ein Werkstück wird schichtweise erzeugt, wobei in jeder Schicht gitterförmig angeordnete Punkte erhitzt werden. Hier gilt es, dass aufeinanderfolgend erhitzte Punkte zumindest eine vorgegebene Distanz voneinander entfernt liegen, um interne Spannungen des Werkstücks zu vermeiden. Weiters muss der kürzest mögliche Weg gefunden werden, um die Herstellungskosten zu minimieren.
In meiner Masterarbeit wurde das TSPFN, welches ursprünglich auf zweidimensionalen, regulären Gittern eingeführt wurde, auf drei Dimensionen erweitert. Für dreidimensionale Quader wurden die Radien der Länge null, eins, Wurzel aus zwei und Wurzel aus drei gewählt und untersucht. Es wurden für bestimmte Größen von Gittern und Radien optimale Lösungen des TSPFN bestimmt. Zur Bestimmung wurden zuerst Beweise für Längen unterer Schranken erforscht und schließlich zugehörige Konstruktionsschemen entwickelt und visualisiert. Mit Hilfe dieser Konstruktionsschemen ist es nun für eine Vielzahl an Gittern möglich, das TSPFN in linearer Zeit zu lösen.
Alle Details zu meinem Forschungsthema, zugehörige Publikationen und Code finden sich unter https://www.philipphungerlaender.com/tspfn/.
