{"id":2176,"date":"2011-11-15T13:50:14","date_gmt":"2011-11-15T11:50:14","guid":{"rendered":"http:\/\/www.foerderverein-technische-fakultaet.at\/?p=2176"},"modified":"2014-02-26T14:46:20","modified_gmt":"2014-02-26T12:46:20","slug":"a-bundle-method-for-the-traveling-salesman-problem","status":"publish","type":"post","link":"https:\/\/www.ftf.or.at\/?p=2176","title":{"rendered":"A Bundle Method for the Traveling Salesman Problem"},"content":{"rendered":"

\"\"<\/a><\/p>\n

\u2026 ist der Titel der besten Diplom- bzw. Magisterarbeiten aller Studien der Technischen Fakult\u00e4t an der Universit\u00e4t Klagenfurt<\/strong> und wurde vom F\u00f6rderverein Technische Fakult\u00e4t mit EUR 1500,\u2013 ausgezeichnet. Der Autorin und Preistr\u00e4gerin, Frau Dipl.-Ing. Karin Kruggel, wurde der Preis im Rahmen der Er\u00f6ffnung des akademischen Jahres 2011\/2012 \u00fcbergeben und die Arbeit wird hier kurz vorgestellt:<\/p>\n

Das Rundreiseproblem, auch als Problem des Handlungsreisenden, kurz TSP, bekannt, ist ein kombinatorisches Optimierungsproblem. Dieses mathematische Problem ist sehr einfach zu beschreiben. Die Aufgabe besteht darin eine Reihenfolge f\u00fcr den Besuch mehrerer Orte so zu w\u00e4hlen, dass die Gesamtreisestrecke nach der R\u00fcckkehr zum Ausgangspunkt m\u00f6glichst kurz ist. Weiters muss jeder Ort genau einmal besucht werden.<\/p>\n

Die einfache Beschreibung dieses Problems macht das TSP zur idealen Plattform um neue algorithmische Ideen zu entwickeln. Daher ist das Traveling Salesman Problem wohl eines der popul\u00e4rsten und meist erforschten Probleme der Mathematik.<\/p>\n

Derartige Fragestellungen spielen in der Praxis eine gro\u00dfe Rolle wie beispielsweise im Design von Mikrochips, der Verteilung von Waren, der kostenoptimalen Belegung von Maschinen, bei der optimalen Wegplanung eines Bohrers auf einer Leiterplatte oder bei der Tourenplanung eines Kunden- oder Pannendienstes. In vielen praktischen Anwendungen m\u00fcssen zudem Zusatzbedingungen wie eingeschr\u00e4nkte Ressourcen, Zeitfenster oder automatisierte Bohrer, die sich nur vertikal und horizontal bewegen k\u00f6nnen beachtet werden, was die L\u00f6sung des Problems erheblich erschwert.<\/p>\n

Die Probleme mit denen man sich in der kombinatorischen Optimierung besch\u00e4ftigt sind meist sehr schwierig. Komplexit\u00e4tstheoretisch geh\u00f6rt das TSP zur Klasse der NP-vollst\u00e4ndigen Probleme. Es stellt sich die Frage, wie man mit solchen Problemen umgeht, da es f\u00fcr diese Klasse von Problemen keine effizienten Algorithmen gibt. Die Laufzeit des worst-case-Szenarios jedes deterministischen Algorithmus, der f\u00fcr dieses Problem stets optimale L\u00f6sungen liefert, h\u00e4ngt im besten Fall exponentiell von der Anzahl der St\u00e4dte ab. Solch ein Algorithmus ben\u00f6tigt bereits f\u00fcr eine geringe Anzahl von St\u00e4dten enorm viel Zeit. Aus diesem Grund ist man an der Berechnung von guten und zufrieden stellenden Approximationen interessiert.<\/p>\n

Zur L\u00f6sung dieser Optimierungsprobleme k\u00f6nnen Methoden der differenzierbaren Optimierung wie das Verfahren des steilsten Abstiegs nicht angewendet werden, weil mathematische Eigenschaften wie Stetigkeit und Differenzierbarkeit in der kombinatorischen Optimierung nicht gelten. In der Literatur wird zur Minimierung von nichtglatten Funktionen h\u00e4ufig auf die Subgradienten Methode verwiesen. Die Idee meiner Masterarbeit war es f\u00fcr die Minimierung anstatt dieser die Bundle Methoden zu verwenden.<\/p>\n

\"\"<\/a><\/p>\n

Das Ziel war es mit Hilfe der Bundle Methoden eine gute untere Schrankenberechnung f\u00fcr das TSP zu finden. Umfangreiche numerische Berechnungen lieferten sehr gute Resultate und zeigten die praktische Brauchbarkeit dieses Zugangs. So konnte zum Beispiel bei einem getesteten St\u00e4dteproblem mit 2392 Knoten eine untere Schranke von lediglich 1,19 Prozent Abweichung zur optimalen Rundreise gefunden werden. Weiters wurde bei einer Problemgr\u00f6\u00dfe von 100 zuf\u00e4llig gew\u00e4hlten Knoten eine Abweichung von 0,13 Prozent zum Optimum erzielt.
\nZusammenfassend kann somit gesagt werden, dass die Bundle Methoden eine gute Wahl zur Berechnung von brauchbaren unteren Schranken f\u00fcr das Rundreiseproblem darstellen.<\/p>\n","protected":false},"excerpt":{"rendered":"

\u2026 ist der Titel der besten Diplom- bzw. Magisterarbeiten aller Studien der Technischen Fakult\u00e4t an der Universit\u00e4t Klagenfurt und wurde vom F\u00f6rderverein Technische Fakult\u00e4t mit EUR 1500,\u2013 ausgezeichnet. Der Autorin und Preistr\u00e4gerin, Frau Dipl.-Ing. Karin Kruggel, wurde der Preis im … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":33,"featured_media":0,"comment_status":"open","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":[9,12],"tags":[],"class_list":["post-2176","post","type-post","status-publish","format-standard","hentry","category-studienabganger","category-news"],"_links":{"self":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/2176","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\/33"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2176"}],"version-history":[{"count":16,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/2176\/revisions"}],"predecessor-version":[{"id":4936,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/2176\/revisions\/4936"}],"wp:attachment":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2176"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2176"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2176"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}