Rundreiseproblem

Das Rundreiseproblem oder Travelling Salesman Problem, ein Problem des Operations Research, besteht darin, daß von einem Ausgangsort aus mehrere Orte in beliebiger Reihenfolge nur einmal besucht werden, um dann zum Ausgangsort zurückzukehren. Es ist die Reihenfolge der Orte zu ermitteln, bei der die anfallenden Kilometer, Zeiten oder Kosten ein Minimum ergeben.

Dem R. in seiner elementaren Variante (Traveling Salesman Problem) liegt folgende Aufgabenstellung zugrund e: Von einem Ort O aus hat eine Person n andere Orte in beliebiger Reihenfolge genau einmal zu beslichen und zum Ausgangsort der Reise zurückzukehren. Die R und reise besteht aus Teilreisen zwischen je zwei Orten und (i,= 0, 1, 2,. . ., n; Ą j), die unterschiedliche Kosten kjj verursachen. Zu ermitteln ist eine Reihenfolge der Orte, die die geringsten R und reisekosten K zur Folge hat. Für dieses verbal leicht beschreibbare Problem existieren verschiedene mathematische Modelle, die jedoch mit heute bekannten Algorithmen nur in Ausnahmefällen Lösungen von Problemen realer Größe in vertretbarer Rechenzeit ermöglichen. Lösungen des R. werden daher durch Enumera-tion zulässiger Folgen der n + 1 Teilreisen einer geschlossenen R und reise und Vergleich der R und reisekosten.

<< vorhergehender Begriff

nächster Begriff >>

Rundreise

Russel-Index