Problem des Handlungsreisenden

Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands.

Das Problem des Handlungsreisenden (PdH), auch Traveling Salesman Problem (TSP, politisch korrekt Traveling Salesperson Problem) genannt, ist ein recht alltägliches Problem der theoretischen Informatik. Es modelliert die Frage, wie man möglichst effizient mehrere Orte hintereinander besuchen kann und wieder zum Ausgangsort zurückkehrt, ohne einen dieser Orte mehrfach zu passieren. In der Praxis gestattet man häufig Orte mehrmals zu besuchen, wodurch die Reise günstiger werden kann, oder behandelt verschiedene Variationen des ursprünglichen Problems (Familie der PdH).

Allgemeine Definition

Das klassische PdH ist seiner Natur nach ein knotenorientiertes Reihenfolgeproblem. Dabei ensprechen die Knoten v_i einer endlichen Anzahl n gleichartiger Objekte, die anhand ihrer Distanzen einer paarweisen Bewertung d(v_i,v_j) unterliegen. Durch eine Permutation p:{v₁,...,v_n} → {p₁,...,p_n} sollen diese Objekte in einer zyklischen Sequenz R = (p₁,..., p_n, p₁) so angeordnet werden, dass der Betrag der vollständig aufsummierten Distanzen unmittelbar aufeinanderfolgender Objekte minimiert wird.

Zielfunktion (klassisches PdH):

z_{\rm {PdH}}=D(R)\rightarrow \min ,\;D(R)=\left(\sum _{i=1}^{n-1}d({p_{i},p_{i+1}})\right)+d({p_{n},p_{1}})

Dabei ist:

n die Anzahl der Objekte des PdH
D(R) die Summe der Distanzen der Sequenz R
p_i das i-te in R enthaltene Objekt

Im ersten Teil der Funktion D werden zunächst die einzelnen Distanzen d der in der Rundreise R aufeinanderfolgenden Objekte p_i und p_i+1 iterativ aufsummiert und schließlich im zweiten Teil durch die Distanz des letzten und ersten Objektes d(p_n,p₁) ergänzt, um den geforderten Zyklus zu schließen. Gesucht ist nun eine Rundreise R, welche die Zielfunktion z_PdH minimiert.

Beschreibung: Im Kontext des Handlungsreisenden können die Objekte als Städte und deren Anordnung in einer zyklischen Sequenz als Rundreise zwischen diesen interpretiert werden. Die Distanzen entsprechen dabei zum Beispiel ihren Abständen, den aufzuwendenden Kosten einer Reise oder der benötigten Zeit. Gesucht ist somit eine Rundreise, bei der jede Stadt genau einmal besucht wird und der Betrag der gesamten Distanz möglichst klein wird.

Klassifikation des Problems

Aufgrund des vielfältigen Auftretens dieser Problemstellung bietet sich eine spezifischere Klassifikation an, um die eingeschränkten Probleme gesondert betrachten zu können. Durch die Untersuchung des zugrunde liegenden Raumes der Distanzen (Gewichtungen) ist dies möglich. Hierzu werden die Relationen zwischen den Objekten v_i, v_j und ihren zugeordneten Distanzen d_ij untersucht.

Als Voraussetzung wird dabei die Definion des klassischen PdH verwendet und schrittweise mit Bedingungen an die Distanz erweitert.

Nichtnegativität und Neutralität

Um das Optimierungsproblem sinnvoll lösen zu können, fordern wir eine Normierung der Distanzen in dem Sinne, dass wir positive Werte für verschiedene zugrunde gelegte Objekte, sowie die Neutralität bezüglich ihrer Addition, bei identischen Objekten erwarten.

Nichtnegativitäts- und Neutralitäts-Bedingung:

\forall i,j\in \{1,2,..,n\}:{\begin{cases}d_{ij}>0,&i\;\not =\;j\\d_{ij}=0,&i=j\end{cases}}

Zum Beispiel ist die Entfernung zweier verschiedener Städte immer größer Null, sowie die Enfernung einer Stadt zu sich selber selbstverständlich immer gleich Null.

Symmetrie der Distanzmatrix

Bei der weiteren Betrachtung der Distanz zweier Objekte kann zudem unterschieden werden, ob die Reihenfolge der beiden Objekte zur Bildung der Distanz beiträgt, oder vernachlässigt werden kann. Hierzu wird eine Matrix (Distanzmatrix od. Gewichtmatrix) betrachtet, deren Zeilen und Spalten jeweils durch alle Objekte des PdH indiziert, die Distanzen zwischen diesen enthält. Die Neutralität der paarweisen Reihenfolge der Objekte zur Bildung der Distanz, kann damit leicht durch eine symmetrische Distanzmatrix verifiziert werden. Dabei erweisen sich asymmetrische Probleme allerdings grundsätzlich als in symmetrische Probleme überführbar, beziehungsweise als solche lösbar.

Symmetrie-Bedingung:

\forall i,j\in \{1,2,..,n\}:d_{ij}=d_{ji}

Am Beispiel des Handlungsreisenden könnte hier der geographische Abstand zweier Städte für die Neutralität der Reihenfolge herangezogen werden. Sollte jedoch die Reisezeit betrachtet werden kann es möglich sein dass sie von Stadt A nach Stadt B kürzer ist (z.B. bessere Verkehrswege) als von Stadt B nach Stadt A und eine nicht symmetrische Distanzmatrix wäre die Folge.

Erfüllung der Dreiecksungleichung

Hinsichtlich symmetrischer Probleme kann weiterhin differenziert werden, ob die sogenannte Dreiecksungleichung erfüllt ist. Die vorherige Betrachtung wird hierzu um ein zusätzliches drittes Objekt erweitert. Dabei wird die Distanz der ursprünglichen beiden Objekte v_i, v_j mit der aufsummierten Distanz über dass dritte Objekt v_k verglichen.

Dreiecksungleichung:

\forall i,j,k\in \{1,2,..,n\}:d_{ij}\leq d_{ik}+d_{kj}

Veranschaulicht bedeutet dies, dass der Handlungsreisende bei einem Umweg über eine dritte Stadt mindestens die Distanz zurücklegt, wie bei der Wahl der direkten Verbindung zweier Städte. Man denke bei Distanz etwa an die Zeit.

Metrik

Insofern die Distanzen unseres betrachteten PdH sämtlich der Nichtnegativitäts- und Identitäts-Bedingung genügen, die Dreiecksungleichung erfüllen und eine symmetrische Distanzmatrix vorliegt, heißt diese bei Existenz einer Distanzfunktion f metrisch.

Distanzfunktion (m - Dimensionen):

\forall i,j\in \{1,2,..,n\},{\vec {x}}_{i},{\vec {x}}_{j}\in \mathbb {R} ^{m}:d_{ij}=f({\vec {x}}_{i},{\vec {x}}_{j})

Dabei werden die zugrunde liegenden Berechnungsvorschriften verschiedenen Metriken zugeordnet, die Spezialfälle des klassischen PdH darstellen. Gängige in Verbindung mit dem PdH erkennbare Metriken sind:

die Euklidische Metrik die zum euklidischen PdH führt
die City-Block-Metrik (auch Manhatten-Metrik) des rektilinearen PdH
und die Maximum-Metrik (auch Chebyshev-Metrik).

Dimension

Im Falle eines metrischen PdH wird impliziert, dass sich jedes Objekt eindeutig durch einen m-dimensionalen Vektor darstellen lässt. Anhand dieser Eigenschaft wird das PdH weiter klassifiziert.

Die aufgrund seiner Anschaulichkeit wahrscheinlich am häufigsten diskutierte und untersuchte Variante, ist das 2-dimensionale euklidische PdH.

Mathematische Modellierung

Bei der mathematischen Beschreibung des Problems ist eine Darstellung gesucht, die auf überschaubare Weise alle wichtigen Eigenschaften in einem mathematisch beherrschbaren Modell wiedergibt.

Hierfür bieten sich die Sprachen der linearen Optimierung und der Graphentheorie besonders an.

Problem ganzzahliger linearer Optimierung

Ein mögliches Modell zur Darstellung des Problem des Handlungsreisenden ist die Interpretation als ganzzahliges lineares Programm. Bei diesem Ansatz werden die Zielfunktion und deren Nebenbedingungen aufgrund ihrer Linearität sämtlich als lineare Gleichungen oder Ungleichungen dargestellt. Wird die Distanzbildung aller Objekte zueinander zugelassen, so spricht man von einem unbeschränkten PdH und es ergibt sich folgender Ansatz:

Zielfunktion:

z_{\rm {PdH}}=\sum _{i=1}^{n}\sum _{j=1}^{n}d_{ij}x_{ij}\rightarrow \min ,\;x_{ij}\in \{0,1\}

In der Zielfunktion z bezeichnet die Variable d_ij die Distanz der Objekte v_i und v_j sowie x_ij eine ihr zugehörige binäre Variable, die Information darüber gibt, ob d_ij Bestandteil der zu ermittelnden optimalen Rundreise sein soll. Somit werden bei der Aufsummierung der Distanzen nur noch solche berücksichtigt, die tatsächlich in der Rundreise enthalten sind und zu einer Minimierung der Zielfunktion führen. Im weiteren muss durch zusätzliche Nebenbedingungen gesichert werden, dass eine zulässige Rundreise, die jedes Objekt genau einmal passiert (Hamiltonpfad) durch den Ansatz bestimmt wird.

Hamiltonpfad-Bedingung:

\sum _{i=1}^{n}b_{ij}=1,\sum _{j=1}^{n}b_{ij}=1,\;\forall i,j\in \{1,2,..,n\}

Die Bedingung legt in diesem Sinne zunächst fest, dass jedes Objekt v_i nur einmal als Startobjekt und nur einmal als Zielobjekt zur Ermittlung einer Distanz auftritt und somit genau über zwei Distanzen mit anderen Objekten in Relation steht. Bei einer Beschränkung auf die bisherigen Bedingungen entspräche der Ansatz dem linearen Zuordnungsproblem, jedoch wäre die Bildung von Subzyklen erlaubt. Dies muss durch eine weitere zusätzliche Restriktion vermieden werden.

Zyklus-Bedingung:

\sum _{i,j\in S}b_{ij}\leq |S|-1,\;\forall S\subset \{1,2,..,n\}\ {\rm {mit\ 2\leq |S|\leq n-2}}

Zuerst werden dabei die Indizes einer beliebigen Teilmenge unserer betrachteten Objekte fixiert und danach die Anzahl der fixierten Objekte mit der Anzahl der in der Rundreise von diesen Objekten bestimmten Distanzen verglichen. Sollte die Anzahl der Distanzen nicht echt kleiner als die Anzahl der Objekte sein, so enthalten die von unserer Teilmenge bestimmten Objekte unter der Erfüllung der Hamiltonpfad-Bedingung mindestens zwei Subzyklen und unsere Zyklus-Bedingung wird nicht erfüllt. Dieser Vergleich wird für alle Indexteilmengen durchgeführt, die mindestens zwei und höchstens n-2 Elemente enthalten.

Im Rahmen der obigen Formulierung des unbeschränkten PdH als lineares Programm, ist dieses grundsätzlich durch das Simplex-Verfahren lösbar. Dabei zeigt sich jedoch die Anzahl der Zyklusbedingungen als exponentiell von der Größe des Problems abhängig.

Modellierung des Problems als Graph

Um das Problem graphentheoretisch zu beschreiben, werden die zu besuchenden Orte sowie der Ausgangsort als Knoten eines Graphen interpretiert. Zwischen je zwei Knoten werden gerichtete Kanten eingefügt, wenn zwischen ihren korrespondierenden Orten ein Weg existiert. Es kann dabei vorkommen, dass nur ein Weg in eine Richtung existiert (zum Beispiel bei einer Einbahnstraße) oder zwischen zwei Orten gar kein Weg vorhanden ist.

Die Kanten erhalten ein Gewicht, das den Kosten entspricht, die entstehen, wenn man den Weg in entsprechender Richtung nutzt, der zwischen den korrespondierenden Orten existiert. Hier kann es auch vorkommen, dass die Kanten in entgegengesetzter Richtung zwischen zwei Knoten unterschiedliches Gewicht enthalten. Gibt es mehrere Wege zwischen zwei Orten, so würde man in der Praxis immer den billigsten wählen. Daher trägt man in diesem Fall natürlich auch das kleinste entsprechende Gewicht an einer Kante ein.

Für den Fall, dass Orte mehrfach besucht werden dürfen, kann man aus dem so entstandenen Graphen einen Distanzgraphen bilden. Dieser hat die Eigenschaft metrisch zu sein. Durch mehrfache Anwendung des Algorithmus von Dijkstra berechnet man dabei zwischen allen Paaren von Knoten den kürzesten Weg und bildet einen vollständigen kantengewichteten gerichteten Graphen, wobei die Kantengewichte die Länge der entsprechenden kürzesten Wege bilden. Voraussetzung ist hierbei natürlich, dass der ursprüngliche Graph stark zusammenhängend ist. Dies ist aber insofern keine Einschränkung, als dass auch eine Rundreise nur unter dieser Bedingung existiert.

Graphentheoretische Beschreibung

In gerichteten Graphen mit Kantengewichten bezeichnet man einen Hamiltonkreis, also einen Kreis, welcher alle Knoten miteinander verbindet als Traveling-Salesman-Tour. Das Problem, zu einem solchen Graphen zu entscheiden, ob eine Traveling-Salesman-Tour der Länge höchstens $k$ existiert, wobei $k$ eine beliebige reelle Zahl ist, bezeichnet man als Problem des Handlungsreisenden (PdH). Neben diesem Entscheidungsproblem gibt es noch das Optimierungsproblem, das kleinste $k$ zu bestimmen, für das eine Traveling-Salesman-Tour der Länge $k$ existiert, und das Suchproblem, eine kürzeste Traveling-Salesman-Tour zu finden. Eine Traveling-Salesman-Tour kann nur existieren, wenn der Graph stark zusammenhängend ist. Diese Eigenschaft lässt sich aber relativ leicht in linearer Zeit prüfen (siehe Zusammenhang von Graphen).

In der Praxis betrachtet man häufig nur metrische Graphen $G=(V,E,f)$ , in denen also die Kantengewichtsfunktion $f$ die Dreiecksungleichung erfüllt, das heißt für drei beliebige verschiedene Knoten $x,y,z$ aus $V$ gilt $f(x,y)+f(y,z)\geq f(x,z)$ . Der Distanzgraph zu einem stark zusammenhängenden gerichteten Graphen besitzt immer diese Eigenschaft.

Beschränkt man sich auf Graphen, in denen diese Bedingung erfüllt ist, so spricht man vom metrischen Problem des Handlungsreisenden. Zwei Speziallfälle sind das euklidische Problem des Handlungsreisenden und das rektilineare Problem des Handlungsreisenden. Diese Fälle liegen vor, wenn es eine Funktion gibt, die den Knoten des Graphen einen Punkt in der euklidischen Ebene zuordnet, so dass die Kantengewichte gerade dem Abstand der zugeordneten Punkte in der Ebene nach 2-Norm (für euklidisches PdH) bzw. 1-Norm (für rektilineares PdH) entsprechen.

Algorithmische Komplexität

Das Problem des Handlungsreisenden ist NP-vollständig. Die Optimierungs- und Suchvariante sind NP-äquivalent. Daran ändert sich nichts, wenn man sich auf das metrische PdH oder sogar noch spezieller auf das euklidische oder rektilineare PdH beschränkt. Für das metrische PdH gibt es aber verschiedene polynomielle Heuristiken.

Die einfachste Heuristik ist die so genannte Nächster-Nachbar-Heuristik, die bei einem beliebigen Knoten beginnend den jeweils am nähesten noch nicht besuchten Nachbarn aufsucht und so eine Traveling-Salesman-Tour (Hamilton-Tour) generiert. Die Güte der so erzeugten Tour kann aber beliebig schlecht werden.

Für das metrische PdH gibt es zwei Approximationsalgorithmen. Die Minimum-Spanning-Tree-Heuristik -- kurz auch MST-Heuristik genannt -- liefert eine Approximationsgüte mit dem Faktor 2, das heißt die gefundene Traveling-Salesman-Tour ist höchstens doppelt so lang wie die kürzeste. Dazu berechnet sie zunächst einen minimal spannenden Baum und erzeugt dann einen Umlauf um diesen (Verdopplung der Kanten, finden einer Eulertour in dem entstandenen eulerschen Graphen und ersetzen benachbarter Kanten, falls ihr gemeinsamer Nachbar in der Eulertour mehr als einmal besucht wird).

Noch bessere Approximationsgüte liefert die Cristofides-Heuristik, die eine Tour berechnet, die höchstens 1,5 mal so lang wie die kürzeste Tour ist. Hierbei wird statt der Verdopplung der Kanten zusätzlich zur MST-Heuristik eine kleinste perfekte Paarung auf den Knoten ungeraden Grades im minimal spannenden Baum berechnet, um einen eulerschen Graphen zu erzeugen. Dieser Algorithmus ist aber komplizierter und langsamer, nämlich $O(n^{4})$ ).

Eine eigene Klasse von Algorithmen bilden die k-Opt-Heuristiken, die zu den Post-Optimization Algorithmen (engl.: Nach-Optimierung) gehören. Sie zeichnen sich dadurch aus, bereits ermittelte Lösungen des PdH noch weiter zu verbessern. Dies geschieht üblicherweise durch das Entfernen von Kanten, gefolgt vom Einfügen neuer Kanten, um die Rundtour wieder zu schließen.

Familie der PdH

Das in den vorhergehenden Abschnitten beschriebene PdH entspricht der klassischen Definition dieser Problemstellung und wird üblicherweise bei der Einführung dessen präsentiert. Im realweltlichen Bezug existiert aber eine nahezu unerschöpflich große Auswahl an beliebig kombinierbaren Varianten, die sich teilweise in verschiedene Modelle einordnen lassen. Diese Modelle bilden die Familie der PdH.

Entsprechende Modifikationen ihrer einzelnen Mitglieder können sowohl als Veränderung der grundlegenden Formulierung der Zielfunktion, als auch durch zusätzliche Nebenbedingungen auftreten. Dabei zeigt es sich, dass sich viele Mitglieder durch eine Polynomialzeitreduktion auf das klassische PdH reduzieren lassen und somit auch in der Klasse NP liegen. Andere Mitglieder wiederum können als größtenteils unabhängig und eigenständig betrachtet werden, wie beispielsweise das Bottleneck TSP, welches sogar in der Klasse P liegt.

Multiple Traveling Salesman Problem (mTSP)

Beim mTSP werden die n Objekte auf m zyklische Sequenzen R₁,...,R_m aufgeteilt. Diese haben jeweils ausschließlich das Ausgangs- beziehungsweise Zielobjekt p₁ gemeinsam. Es soll der Betrag der Summe aller Distanzen minimiert werden, wobei neutrale Zyklen R_i = (p₁, p₁) entweder zugelassen, oder in der Variante mTSP with nonlazy Salesmen verboten sind.

Zielfunktion (mTSP):

z_{\rm {mTSP}}(m)=\sum _{s=1}^{m}D(R_{s})\rightarrow \min ,\;D(R_{s})=\left(\sum _{i=1}^{n_{s}-1}d({p_{(s,i)},p_{(s,i+1)}})\right)+d({p_{(s,n)},p_{1}})

Dabei ist:

m die Anzahl der zyklischen Sequenzen
D(R_s) die Distanzsumme der s-ten Sequenz R_s
n_s die Anzahl der Objekte in R_s
p_(s,i) das i-te in R_s enthaltene Objekt

Beschreibung: Nun wird auf die Einschränkung auf einen einzelnen Handlungsreisenden verzichtet und das Problem auf mehrere Handlungsreisende erweitert. Dabei werden diese entweder sämtlich oder nur zum Teil eingesetzt. Alle starten in der selben Stadt und beienden ihre Rundreise wieder in dieser. Ziel ist es, dass alle Städte einmal von jeweils genau einem Handlungsreisenden besucht und dabei die zurückgelegte Gesamtstrecke minimiert wird.

Komplexität: Das Problem ist NP-schwer. Für den Fall m = 1 entspricht es einem klassischen PdH.

Hierarchie: Das mTSP ist eine Verallgemeinerung des klassischen PdH und kann zum Vehicle Routing Problem verallgemeinert werden.

Vehicle Routing Problem (VRP)

Beschreibung: Im Rahmen der Tourenplanung wird unsererer Betrachtung eine Auslieferung von Waren mit maximalen Transportkapazitäten und festen Bestellumfängen verschiedener Kunden zugrunde gelegt. Die Rundreisen entsprechen nun den Touren von Transportern, die von einem gemeinsamen Depot starten. Hierbei darf der Betrag der ausgelieferten Bestellmenge pro Tour die Kapazität des Transporters nicht überschreiten. Angestrebt wird bei einer vollständigen Abdeckung der Bestellumfänge die Summe aller Strecken zu minimieren. Dabei kann ein Kunde zwar mehrfach, jedoch nur jeweils von einem Transporter beliefert werden.

Komplexität: Das Problem ist NP-schwer. Für den Fall, dass die Kapazitäten der Transporter größer als die Summe aller Bestellmengen sind enspricht das Problem dem mTSP

Hierarchie: Das VRP verallgemeinert das mTSP. Davon abgeleitete Varianten sind:

Capacitated VRP (CVRP): Die Transporter haben eine einheitliche Kapazität.
Multiple Depot VRP (MDVRP): Die Transporter können von mehreren verschiedenen Depots starten.
Periodisches VRP (PVRP): Im Gegensatz zum klassischen VRP wächst der Bedarf der Kunden in zeitlichen Abständen nach. Dabei wird eine feste Zeitdauer betrachtet.
Split Delivery VRP (SDVRP): Ein Knoten kann von verschiedenen Transportern beliefert werden.

Prize Collecting Traveling Salesman Problem (PCTSP)

Aus einem klassischen PdH mit n Objekten soll eine Untermenge aus k Objekten so gewählt werden, dass die optimale Lösung des auf diese eingeschränkten PdH einen minimalen Wert annimmt. Somit ist auch das Startobjekt von der Wahl der Objekte abhängig und für jede getroffene Auswahl neu zu bestimmen.

Zielfunktion (PCTSP):

z_{\rm {PCTSP}}(k)=D(R_{k})\rightarrow \min ,\;D(R_{k})=\left(\sum _{i=1}^{k}d({p_{(k,i)},p_{(k,i+1)}})\right)+d({p_{(k,n)},p_{(k,1)}})

Dabei ist:

k die Anzahl der Objekte
D(R_k) die Distanzsumme der optimalen Rundreise mit k Objekten
p_(k,i) das i-te Objekt in R_k

Beschreibung: Bevor der Handlungsreisende seine Rundreise antritt muss er sich also zuerst entscheiden, welche Städte er bereisen will sowie mit welcher dieser Städte er seine Reise beginnt.

Komplexität: Das Problem ist NP-schwer. Für den Fall k = n entspricht es dem klassischen PdH.

Hierarchie: Das PCTSP verallgemeinert das klassische PdH. Eine Variante ist das Traveling Salesman Selection Problem (TSSP), welches die Einschränkung auf eine euklidische Metrik behandelt.

Bottleneck TSP (BTSP)

Einen effizient lösbaren Sonderfall beschreibt das Bottleneck TSP.

Beschreibung: Nun soll nicht mehr die gesamte Strecke der Rundreise, sondern nur noch die längste Einzelstrecke minimiert werden. Dies bewirkt eine möglichst gleichmäßige Verteilung beziehungsweise Glättung der einzelnen Strecken und unterbindet damit das Entstehen möglicher Flaschenhälse.

Literatur

Lawler, Lenstra, Rinnooy Kan, Shmoys (Hrsg.): The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, 1985, ISBN 0-471-90413-9

Weblinks

The Traveling Salesman Problem Home
Spektrum der Wissenschaft: Die optimierte Odyssee von Martin Grötschel und Manfred Padberg
The VRP Web

Siehe auch: Routing-Problem