{"id":196,"date":"2013-05-08T14:13:34","date_gmt":"2013-05-08T12:13:34","guid":{"rendered":"http:\/\/www.prolehre.com\/markusheinemann\/wordpress\/?page_id=196"},"modified":"2015-01-20T16:34:20","modified_gmt":"2015-01-20T14:34:20","slug":"tsp","status":"publish","type":"page","link":"https:\/\/markusheinemann.com\/wordpress\/?page_id=196","title":{"rendered":"TSP"},"content":{"rendered":"<p>Beim <strong>T<\/strong>ravelling <strong>S<\/strong>alesman <strong>P<\/strong>roblem wird eine Route gesucht, die eine gegebene Anzahl an Knoten verbindet. Sollen beispielsweise die St\u00e4dte Hamburg, Bremen, Stuttgart, M\u00fcnchen und K\u00f6ln besucht werden, muss eine Besuchsreihenfolge festgelegt werden.<\/p>\n<p>Viele verschiedene M\u00f6glichkeiten sind dabei denkbar. Hier zwei Beispiele:<\/p>\n<ul>\n<li>Berlin &#8211; Hamburg &#8211; Stuttgart &#8211; Bremen &#8211; M\u00fcnchen &#8211; K\u00f6ln &#8211; Berlin <span style=\"color: #ff0000;\"><strong>(rote Tour)<\/strong><\/span><\/li>\n<li>Berlin &#8211; M\u00fcnchen &#8211; Stuttgart &#8211; K\u00f6ln &#8211; Bremen &#8211; Hamburg &#8211; Berlin <strong><span style=\"color: #99cc00;\">(gr\u00fcne Tour)<\/span><\/strong><\/li>\n<\/ul>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/www.Markusheinemann.com\/wordpress\/wp-content\/uploads\/2013\/05\/TSP2-300x243.png\" alt=\"TSP2\" width=\"300\" height=\"243\" class=\"alignright size-medium wp-image-204\" srcset=\"https:\/\/Markusheinemann.com\/wordpress\/wp-content\/uploads\/2013\/05\/TSP2-300x243.png 300w, https:\/\/Markusheinemann.com\/wordpress\/wp-content\/uploads\/2013\/05\/TSP2.png 699w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><br \/>\nHier l\u00e4sst sich leicht erkennen, dass die <span style=\"color: #99cc00;\">gr\u00fcne Tour<\/span> insgesamt viel k\u00fcrzer als die <span style=\"color: #ff0000;\">rote<\/span> ist. Um nun z.B. Kosten oder Zeit zu sparen, w\u00fcrde jeder \u00f6konomisch denkender Mensch, der alle St\u00e4dte besuchen muss die gr\u00fcne Tour nehmen. Das TSP hat hier genau einen Startpunkt an dem der Reisende zum Ende der Tour wieder ankommen muss.<\/p>\n<p>Dieses Beispiel ist so einfach, dass die gr\u00fcne Tour gefunden wird, wenn in jeder Stadt einfach die n\u00e4chstgelegene angefahren wird. Leider liefert diese Heuristik des n\u00e4chsten Nachbarn oft sehr schlechte Routen.<\/p>\n<p>F\u00fcr das TSP gibt es vielf\u00e4ltige L\u00f6sungsalgorithmen. Ein ber\u00fchmtes Beispiel ist der Ameisenalgorithmus. Dabei werden verschiedene Varianten der Rundreise durchgerechnet und die beste vorgeschlagen. Mathematisch wird dabei immitiert, dass bei der Wahl des als n\u00e4chstes zu besuchenden Ortes, Kanten (z.B. Stra\u00dfen) gew\u00e4hlt werden, die sich schon bei vorherigen m\u00f6glichen Rundreisen als sinnvoll erwiesen haben.<\/p>\n<p>Ein weiteres sehr einfaches Verfahren ist der Threshold Accepting Algorithmus, bei dem irgendeine Route durch Ver\u00e4ndern der Besuchsreihenfolge verbessert wird. Dabei werden einfach zwei Orte in der Reihenfolge getauscht und es entsteht eine neue Rundreise.<\/p>\n<p>Beide Algorithmen ist in der folgenden Excel Datei als Macros implementiert. Auf der ersten Seite (&#8222;dij&#8220;) m\u00fcssen dazu die Entfernungen von jeden zu jedem anderen Knoten eingegeben werden.<\/p>\n<p><a href=\"http:\/\/www.Markusheinemann.com\/wordpress\/wp-content\/uploads\/2013\/05\/TSPalgorithmen.xlsm\">TSPalgorithmen<\/a><br \/>\nAuf der Seite <a id=\"ncmi\" title=\"http:\/\/www.gebweb.net\/optimap\/\" href=\"http:\/\/www.gebweb.net\/optimap\/\">http:\/\/www.gebweb.net\/optimap\/ <\/a>l\u00e4sst sich das TSP bedeutend einfacher ausprobieren. Dabei k\u00f6nnen beliebige Orte auf der ganzen Welt zur Generierung einer Rundreise eingegeben werden.<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Beim Travelling Salesman Problem wird eine Route gesucht, die eine gegebene Anzahl an Knoten verbindet. Sollen beispielsweise die St\u00e4dte Hamburg, Bremen, Stuttgart, M\u00fcnchen und K\u00f6ln besucht werden, muss eine Besuchsreihenfolge festgelegt werden. Viele verschiedene M\u00f6glichkeiten sind dabei denkbar. Hier zwei Beispiele: Berlin &#8211; Hamburg &#8211; Stuttgart &#8211; Bremen &#8211; M\u00fcnchen &#8211; K\u00f6ln &#8211; Berlin (rote [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-196","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/196","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=196"}],"version-history":[{"count":3,"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/196\/revisions"}],"predecessor-version":[{"id":438,"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/196\/revisions\/438"}],"wp:attachment":[{"href":"https:\/\/markusheinemann.com\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=196"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}