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 je 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 aufgefasst 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}$ mit $i=0,\dots ,n$ und $j=0,\dots ,n$ folgendermaßen definiert:

$$x_{ij}=\left\{\begin{array}{cc}1& \text{wenn der Reisende von der Stadt }i\text{ direkt in die Stadt }j\text{ fährt,}\hfill \\ 0& \text{sonst.}\hfill \end{array}\right.$$

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

Rundreiseproblem: Gesucht sind die Werte $x_{ij}$ so, dass gilt:

$\sum _{i=0}^n\sum _{j=0}^n{c}_{ij}\cdot x_{ij}=\text{Min!}$				(11)
$\sum _{i=1}^n{x}_{ij}=1$         $j=1,\dots ,n$				(12)
$\sum _{j=1}^n{x}_{ij}=1$         $i=1,\dots ,n$				(13)
$u_i-u_j+n\cdot x_{ij}\le n-1$	$i=1,\dots ,n$	$j=1,\dots ,n$	$i\ne j$	(14)

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ässt. (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. Anschließend 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ängige Zyklen. Dann ist einer der beiden Zyklen ein 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 $n\cdot k\le \left(n-1\right)\cdot 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,\dots ,n$. Mit dieser Definition folgt wegen $u_i-u_j\le 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+n\cdot x_{ij}=p-\left(p+1\right)+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.