{"id":6831,"date":"2019-10-24T21:23:59","date_gmt":"2019-10-24T19:23:59","guid":{"rendered":"https:\/\/www.ftf.or.at\/?p=6831"},"modified":"2019-10-24T21:23:59","modified_gmt":"2019-10-24T19:23:59","slug":"the-traveling-salesperson-problem-with-forbidden-neighborhoods","status":"publish","type":"post","link":"https:\/\/www.ftf.or.at\/?p=6831","title":{"rendered":"The Traveling Salesperson Problem with Forbidden Neighborhoods"},"content":{"rendered":"<p>\u2026 ist der Titel des\u00a0<strong>1. Platzes des Roland-Mittermeir-Preises 2018<\/strong>\u00a0und wurde vom F\u00f6rderverein Technische Fakult\u00e4t mit\u00a0<strong>EUR 1.000,\u2013<\/strong>ausgezeichnet. Der Autorin und Preistr\u00e4gerin, Frau\u00a0<strong>Dipl.-Ing.in Anna Jellen B.Sc.<\/strong>, wurde der Preis im Rahmen Generalversammlung\u00a02019 \u00fcbergeben und die Arbeit wird hier kurz vorgestellt:<\/p>\n<p>In meiner Masterarbeit bescha\u0308ftige 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) abgeku\u0308rzt.<\/p>\n<p>Es werden gleichma\u0308\u00dfig angeordnete Punkte betrachtet, z.B. die Mittelpunkte der Felder eines Schachbretts. Diese Anordnung von Punkten wird regula\u0308res Gitter genannt. Die Aufgabe ist nun, ausgehend von einem beliebigen Punkt, alle anderen Punkte genau einmal zu besuchen und zum Startpunkt zuru\u0308ckzukehren, wobei der ku\u0308rzest mo\u0308gliche Weg gesucht wird. Zusa\u0308tzlich gibt es noch die Bedingung, dass die Distanz zwischen je zwei aufeinanderfolgenden Punkten gro\u0308\u00dfer als ein vorgegebener Radius sein muss.<\/p>\n<p>Dieses Problem entstammt einem Verfahren namens Laser-Beam-Melting, welches a\u0308hnlich dem 3-D-Druck ist. Ein Werkstu\u0308ck wird schichtweise erzeugt, wobei in jeder Schicht gitterfo\u0308rmig angeordnete Punkte erhitzt werden. Hier gilt es, dass aufeinanderfolgend erhitzte Punkte zumindest eine vorgegebene Distanz voneinander entfernt liegen, um interne Spannungen des Werkstu\u0308cks zu vermeiden. Weiters muss der ku\u0308rzest mo\u0308gliche Weg gefunden werden, um die Herstellungskosten zu minimieren.<\/p>\n<p>In meiner Masterarbeit wurde das TSPFN, welches urspru\u0308nglich auf zweidimensionalen, regula\u0308ren Gittern eingefu\u0308hrt wurde, auf drei Dimensionen erweitert. Fu\u0308r dreidimensionale Quader wurden die Radien der La\u0308nge null, eins, Wurzel aus zwei und Wurzel aus drei gewa\u0308hlt und untersucht. Es wurden fu\u0308r bestimmte Gro\u0308\u00dfen von Gittern und Radien optimale Lo\u0308sungen des TSPFN bestimmt. Zur Bestimmung wurden zuerst Beweise fu\u0308r La\u0308ngen unterer Schranken erforscht und schlie\u00dflich zugeho\u0308rige Konstruktionsschemen entwickelt und visualisiert. Mit Hilfe dieser Konstruktionsschemen ist es nun fu\u0308r eine Vielzahl an Gittern mo\u0308glich, das TSPFN in linearer Zeit zu lo\u0308sen.<\/p>\n<p>Alle Details zu meinem Forschungsthema, zugeho\u0308rige Publikationen und Code finden sich unter <a href=\"https:\/\/www.philipphungerlaender.com\/tspfn\/\">https:\/\/www.philipphungerlaender.com\/tspfn\/<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u2026 ist der Titel des\u00a01. Platzes des Roland-Mittermeir-Preises 2018\u00a0und wurde vom F\u00f6rderverein Technische Fakult\u00e4t mit\u00a0EUR 1.000,\u2013ausgezeichnet. Der Autorin und Preistr\u00e4gerin, Frau\u00a0Dipl.-Ing.in Anna Jellen B.Sc., wurde der Preis im Rahmen Generalversammlung\u00a02019 \u00fcbergeben und die Arbeit wird hier kurz vorgestellt: In meiner &hellip; <a href=\"https:\/\/www.ftf.or.at\/?p=6831\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"sfsi_plus_gutenberg_text_before_share":"","sfsi_plus_gutenberg_show_text_before_share":"","sfsi_plus_gutenberg_icon_type":"","sfsi_plus_gutenberg_icon_alignemt":"","sfsi_plus_gutenburg_max_per_row":"","footnotes":""},"categories":[12],"tags":[],"class_list":["post-6831","post","type-post","status-publish","format-standard","hentry","category-news"],"_links":{"self":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/6831","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=6831"}],"version-history":[{"count":2,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/6831\/revisions"}],"predecessor-version":[{"id":6856,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/6831\/revisions\/6856"}],"wp:attachment":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6831"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6831"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6831"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}