Das Rundreiseproblem

Das Rundreiseproblem, auch Problem eines Handlungsreisenden, ist eine sehr bekannte Aufgabe. Betrachten wir n+1 Städte mit den Entfernungen c_ij zwischen den zwei Städten i und j. Ein Handlungsreisender soll von einer Ausgangsstadt 0 aus n andere Städte besuchen, dabei jede genau einmal, und anschließend wieder zu 0 zurückkehren.
Das Rundreiseproblem sucht nach der Reihenfolge, in der der Reisende die Städte ansteuern muss, damit der zu durchlaufene Gesamtweg minimal wird.

Das Rundreiseproblem kann aufgefaßt werden als eine Art von Zuordnungsproblem, aufgrund des geforderten Zyklus der Reise ist es jedoch viel komplexer und schwieriger. Das Rundreiseproblem ist auch als ein kombinatorisches Problem bekannt, d.h. Modelle der Kombinatorik können auf diese Sorte von Aufgaben übertragen werden.

Es gibt verschiedene Modellierungen des Rundreiseproblems, betrachten wir es hier als ganzahliges lineares Optimierungsproblem. Die sich damit ergebenden Formeln der Zielfunktion und der Nebenbedingungen weisen eine große Ähnlichkeit zum Transportproblem auf. Es zeigt sich aber, dass trotz fast analoger Formulierung ein total verschiedenes Lösungsverhalten auftritt.

Es seien die Variablen x_ij (i = 0,…,n und j = 0,…,n) definiert mit

Das Rundreiseproblem läßt sich dann beschreiben mit der Zielfunktion (11) und den Nebenbedingungen (12), (13) und (14).

Rundreiseproblem: Gesucht sind die Werte x_ij so, dass gilt:

Die Bedingungen besitzen die folgende Bedeutung: (12) besagt, dass der Reisende jede Stadt j, abgesehen von der Ausgangsstadt, genau einmal anläuft, (13) besagt, dass der Reisende jede Stadt i, abgesehen von der Ausgangsstadt, genau einmal verläßt. (11) kennzeichnet die Zielfunktion, der Gesamtweg, den der Reisende zurücklegt, soll so klein wie möglich sein. In der Doppelsumme werden dabei nur die x_ij berücksichtigt, deren Wert 1 ist, d.h. die beschreiben, dass der Reisende von i nach j fährt.

Die Bedingungen (12) und (13) entwickeln gemeinsam mit der Zielfunktion (11) ein Optimierungsproblem, das aufgrund der Wertbelegung der x_ij auch 0-1-Zuordnungsproblem genannt wird. Dieses Problem enthält jedoch einen Sachverhalt, der nach unserer Definition nicht im Rundreiseproblem zulässig ist. Es ist dem Reisenden möglich, seinen Weg in Teilzyklen zu zerlegen, die voneinander unabhängig sind. Mit anderen Worten: Er kann in 0 starten, von dort aus 9 Städte hintereinander besuchen und dann zu 0 zurückkehren. Anschliessend fährt er von der elften Stadt in die zwölfte usw. um irgendwann wieder in die elfte zurückzukehren. Dieses paradoxe Verhalten (wie gelangt der Reisende von der Anfangsstadt 0 in die elfte Stadt?) wird durch das Bedingungsgefüge (11), (12) und (13) nicht ausgeschlossen. Dann liegt aber eben keine Rundreise vor, die den gestellten Anforderungen entspricht.

Die Bedingung (14) verhindert derartige Teilzyklen.
Angenommen, es gibt als Lösung des Rundreiseproblems zwei unabhängigen Zyklen. Dann ist einer der beiden Zyklen einen Teilzyklus T mit k < n Gliedern, der die Stadt 0 nicht enthält.
Alle x_ij längs des Weges T sind dann gleich 1, addiert man nun alle Ungleichungen (14) mit x_ij = 1 längs des Zyklus T, so erhält man die Ungleichung nk ≤ (n-1)k, da sich alle Differenzen u_i-u_j gegenseitig wegheben. Diese Ungleichung ist falsch. Die Annahme ist widerlegt. Die Bedingung (14) sorgt demzufolge dafür, dass eine beliebige Route für den Reisenden aus genau einem Zyklus besteht, der die Stadt 0 beinhaltet.

Es bleibt noch für eine beliebige Rundreise, ausgehend von der Stadt 0, ein u_i anzugeben, so dass (14) erfüllt wird. Aus diesem Grund setzen wir u_i = p, wenn die Stadt i vom Reisenden im p-ten Schritt seiner Reise besucht wird. Es ist sicher p = 1,…,n. Mit dieser Definition folgt wegen u_i - u_j ≤ n-1 für alle x_ij = 0 die Gültigkeit der Bedingung (14).
Bei x_ij = 1 folgt dann aufgrund der Definition von x_ij mit u_i = p auch u_j = p+1. Dann gilt u_i - u_j + nx_ij = p - (p+1) + n = n - 1.
Damit wäre (14) mit der Definition der u_i für alle x_ij gültig.

Die Zielfunktion (11) und die Bedingungen (12)…(14) beschreiben das Rundreiseproblem äquivalent. Die Verwandschaft zum Transportproblem wird offenbar bei Betrachtung des Transportproblems mit m = n und v_i = b_j = 1 für alle i und j.

Es zeigt sich, dass das Rundreiseproblem NP-vollständig ist, d.h. es gibt keinen Algorithmus, der das Problem in polynomialer Zeit löst. Dies liegt begründet in dem Verlangen nach einem Zyklus, den der Reisende beschreiben soll.