Home | Sitemap | Kontakt | english  | Impressum | KIT
Informatik mit Profil.
 
KIT on on iTunes U
Immer auf dem Laufenden - mit unserem RSS-Angebot
RSS-Feed

Unsere Nachrichten stehen auch als RSS-Newsfeed zur Verfügung.
RSS-Feed abonnieren

Problem des Monats: Juni 2017

Problem des Monats: Juni 2017
Autor:

Janka Kuhfuß

Links:
Datum: 08.06.2017

Das Problem des Handlungsreisenden

Urlaubsplanung mit dem Travelling Salesman Problem (TSP)
Alice' geplante Urlaubsorte

Alice hat endlich ihre Bachelorarbeit abgegeben und die letzte Prüfung bestanden. Nun hat sie noch neun Wochen bis zum Beginn ihres Masters Zeit und möchte ein wenig ausspannen. Sie beschließt, einfach mal ihre Freunde zu besuchen, die an anderen Hochschulen studieren. Bob hat sie schon so lange nicht mehr gesehen, und Carla hat sie noch nie besucht – sie beginnt eine Liste:

  • Bob – Stuttgart
  • Carla – Aachen
  • Dana – Kiel
  • Eric – Berlin
  • ...

Schnell hat sie eine Liste von 15 Städten zusammen. Da sie mit dem Wohnmobil ihrer Eltern fahren darf, aber nicht unnötig viel Geld für Diesel ausgeben möchte, muss sie nun die kürzeste Strecke finden. Sie erinnert sich daran, im dritten Semester mal vom Travelling Salesman Problem gehört zu haben.

Schon seit 1930 betrachten Mathematiker das Problem des Handlungsreisenden. Dieser möchte ähnlich wie Alice mehrere Orte in einer Rundreise besuchen und dabei den kürzesten Weg nehmen. Intuitiv erscheint es eine einfache Lösung, alle möglichen Wege zu berechnen und dann den Kürzesten auszuwählen. Beziehen wir uns auf Alice’ Urlaub mit 15 Städten, gibt es 43 Milliarden Möglichkeiten, die wir berechnen müssen. Das wird also schnell zu komplex, um es in der Praxis einzusetzen.

Es gibt exakte Lösungsverfahren für das TSP, meist verwendet man jedoch Heuristiken*. Heuristiken sind bedeutend schneller, liefern jedoch meist nicht das beste Ergebnis. Bei einigen Heuristiken lässt sich beweisen, wie „schlecht“ das gelieferte Ergebnis maximal ist. Außerdem kann man Verbesserungsverfahren anwenden, die versuchen, durch kleine Änderungen eine Verbesserung herbeizuführen. Damit erhält man auch in großen Problemstellungen Ergebnisse, die „gut genug“ sind.

In der Industrie werden solche Heuristiken vielfach für Problemstellungen verwendet, die sich durch  das TSP modellieren lassen. In der Logistik ist die naheliegendste Anwendung, etwa bei der Routenfindung für einen Lieferdienst. Hier spielen verschieden Faktoren eine Rolle, nicht nur, wie bei Alice, der Kraftstoffverbrauch, sondern auch Kühlketten und ähnliches. Weg- oder Zeiteinsparung bedeutet hier Geldeinsparung. Aber auch beim Design von Mikrochips lässt sich das TSP einsetzen, um Material- und damit Geldeinsparung zu erzielen.

Für Alice, die nur 15 Städte besuchen möchte, ist das alles etwas zu aufwendig. Sie druckt eine Deutschlandkarte aus und verbindet intuitiv die Punkte auf der Karte. Dieses Ergebnis ist für sie gut genug.

 

Selbst reisen: https://www-m9.ma.tum.de/games/tsp-game/index_de.html

*Heuristik bezeichnet die Kunst, mit begrenztem Wissen und wenig Zeit dennoch zu wahrscheinlichen Aussagen oder praktikablen Lösungen zu kommen.