Näher an der optimalen Tour

Mit einem neu entwickelten Algorithmus kann man Touren durch beliebig viele Städte ermitteln, die der kürzesten Tour „möglichst nah“ kommen.

Das „Problem des Handlungsreisenden“ ist weltberühmt und wurde erstmals im Jahr 1930 formuliert: Gegeben sind ein Anfangs- und ein Endpunkt und weitere Punkte, die unterwegs besucht werden sollen. Ziel ist es, die kürzeste Tour durch all diese Punkte zu finden, indem man die Reihenfolge der zu besuchenden Punkte optimiert. Anwendungen findet das Problem etwa in der Logistik oder Tourenplanung: Man kann sich beispielsweise fragen, wie man auf kürzestem Weg von Kiel nach München reist, wenn man unterwegs alle weiteren 14 Hauptstädte der deutschen Bundesländer besuchen möchte. Für sehr wenige Punkte kann man noch alle möglichen Reihenfolgen ausprobieren, doch bereits bei der Tour durch die Landeshauptstädte gibt es über 80 Milliarden theoretische Möglichkeiten.

Ein NP-schweres Problem

Das Problem, die beste Reihenfolge für eine solche Tour zu finden, ist als besonders schwer klassifiziert. Probleme, die man algorithmisch „verhältnismäßig schnell“ (in sogenannter Polynomialzeit) lösen kann, zählen zur Klasse P. Probleme, deren gegebenen Lösungen man „verhältnismäßig schnell“ überprüfen kann, zählen zur Klasse NP. Bis heute weiß man nicht, ob man solche Probleme der Klasse NP dann auch „verhältnismäßig schnell“ lösen kann, ob also P=NP gilt. Dieses sogenannte „P-NP-Problem“ gilt als eines der wichtigsten ungelösten Probleme der Informatik und wurde vom Clay Mathematics Institute in die Liste der Millennium-Probleme aufgenommen. In der Klasse NP gibt es nun ausgezeichnete, als besonders schwer anzusehende Probleme, auf die sich alle anderen Probleme dieser Klasse zurückführen lassen. Probleme, die mindestens so schwer sind wie diese ausgezeichneten Probleme, werden als „NP-schwer“ bezeichnet. Das „Problem des Handlungsreisenden“ ist ein solch „NP-schweres“ Problem.

Ein neuer Algorithmus

Für den Spezialfall, bei dem Anfangs- und Endpunkt des Weges gleich sind – es sich also um eine Rundreise handelt – fand der zypriotische Mathematiker Nicos Christofides bereits im Jahr 1976 einen effektiven Algorithmus. Die dadurch ermittelte Rundreise ist höchstens um die Hälfte länger als die optimale Tour. Diese Garantie an die Güte des Rundwegs stellt eine Art natürliche Grenze da. Es erwies sich bislang als deutlich schwieriger, diese Grenze auch für Wege mit unterschiedlichem Anfangs- und Endpunkt zu erreichen. Mit einem neuen Ansatz, einem sogenannten „rekursiven dynamischen Programm“, gelang es nun Vera Traub und Jens Vygen auch in diesem Fall beliebig nah an die natürliche Grenze zu gelangen: Die mit dem neuen Algorithmus ermittelten Touren sind höchstens x-mal so lang wie die optimale Tour, wobei x beliebig nah an 1,5 liegt. Der neue Algorithmus könnte zukünftig auch bei anderen Optimierungsaufgaben Anwendung finden.

Publikation:

Vera Traub, Jens Vygen: Approaching 3/2 for the s-t-path TSP. Submitted. Preliminary version in the Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (2018), 1854-1864 (Best Paper Award)

 

Die Arbeit wurde mit dem "Best Paper Award" des ACM-SIAM Symposium on Discrete Algorithms (SODA) ausgezeichnet. (Pressemitteilung vom 9. Januar 2018)