Das Rundreiseproblem
Das Rundreiseproblem, auch Problem eines Handlungsreisenden, ist eine
sehr bekannte Aufgabe.
Betrachten wir Städte mit den Entfernungen
zwischen je zwei Städten und . Ein Handlungsreisender soll von einer
Ausgangsstadt aus andere Städte besuchen, dabei jede genau einmal,
und anschließend wieder zu 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 mit
und
folgendermaßen definiert:
Das Rundreiseproblem lässt sich dann beschreiben mit der Zielfunktion
(11) und den Nebenbedingungen (12), (13) und (14).
Rundreiseproblem: Gesucht sind die Werte so, dass gilt:
|
(11)
|
|
(12)
|
|
(13)
|
|
|
|
|
(14)
|
Die Bedingungen besitzen die folgende Bedeutung: (12) besagt, dass der Reisende jede Stadt ,
abgesehen von der Ausgangsstadt, genau einmal anläuft.
(13) besagt, dass der Reisende jede Stadt , 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 berücksichtigt, deren Wert ist, d.h. die beschreiben,
dass der Reisende von nach fährt.
Die Bedingungen (12) und (13) entwickeln gemeinsam mit
der Zielfunktion (11) ein Optimierungsproblem, das aufgrund der
Wertbelegung der 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 starten, von dort aus 9 Städte hintereinander besuchen und dann zu
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 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
mit Gliedern, der die Stadt nicht enthält.
Alle längs des Weges sind dann gleich
. Addiert man nun
alle Ungleichungen (14) mit längs des Zyklus
, so erhält man die Ungleichung
,
da sich alle Differenzen
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 ,
ein anzugeben, so dass (14) erfüllt wird.
Aus diesem Grund setzen wir , wenn die Stadt
vom Reisenden im -ten Schritt seiner Reise besucht wird.
Es ist sicher .
Mit dieser Definition folgt wegen
für alle die Gültigkeit der Bedingung
(14).
Bei folgt dann aufgrund der Definition von
mit
auch .
Dann gilt
.
Damit wäre (14) mit der Definition der für alle
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 und
für alle und .
Es zeigt sich, dass das Rundreiseproblem NP-vollständig ist, d.h.
es gibt keinen Algorithmus, der das Problem in polynomialer Zeit löst.
|