Mehrkriterielle Traveling Salesman Probleme und Necklace-Splitting

Kurzfassung: Das Traveling Salesman Problem gehört zu den bekanntesten kombinatorischen Optimierungsproblemen. Zu einer gegebenen Menge von Städten soll hierbei eine Rundreise bestimmt werden, die eine minimale Länge besitzt. In der Praxis spielen jedoch häufig mehrere Kriterien eine Rolle, die gleichzeitig berücksichtigt werden müssen. Möchte man beispielsweise die gesuchte Rundreise mit einem PKW abfahren, so können neben der Distanz auch Mautgebühren oder die typische Verkehrsdichte der Streckenabschnitte eine Rolle spielen. Gesucht ist also eine Lösung, die einen geeigneten Kompromiss zwischen den verschiedenen Kriterien darstellt.

Die Maximierungsvariante des Traveling Salesman Problems ist ebenfalls seit langem Gegenstand der Forschung. Im Laufe der Jahre wurden hier verschiedene einkriterielle Approximationsverfahren entwickelt. Wir zeigen, wie man mit Hilfe von Necklace Splitting solche einkriteriellen Verfahren auch auf mehrkriterielle Problemvarianten übertragen kann.