Problem des Handlungsreisenden

Das Problem des Handlungsreisenden (kurz PdH, englisch Traveling Salesman Problem, neuerdings politisch korrekt Traveling Salesperson Problem, kurz TSP) ist ein recht alltägliches Problem der theoretischen Informatik. Es modelliert die Frage, wie man möglichst schnell oder billig mehrere Orte hintereinander besuchen kann und wieder zum Ausgangsort zurückkehrt.

Bei der Modellierung wird häufig nur der Fall zugelassen, dass jeder Ort nur einmal besucht wird. In der Praxis gestattet man meist Orte mehrmals zu besuchen, wodurch die Reise günstiger werden kann. Dadurch kann man das Problem immer so modellieren, dass der zugrundeliegende Graph metrisch wird - drei Knoten erfüllen also stets die Dreiecksungleichung. Dies ist besonders für die algorithmischen Lösung des Problems vorteilhaft.

Allgemeine klassische 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 so angeordnet werden, dass der Betrag der vollständig aufsummierten Distanzen unmittelbar aufeinanderfolgender Objekte minimiert wird.

Zielfunktion (klassisches PdH):

$z=\left(\sum _{i=1}^{n-1}d({p_{i},p_{i+1}})\right)+d({p_{n},p_{1}})\rightarrow \min$

Im ersten Teil der Funktion werden zunächst die einzelnen Distanzen der aufeinanderfolgenden Objekte p_i und p_i+1 iterativ aufsummiert und schließlich im zweiten Teil durch die für den Schluss des Zyklus erforderliche Distanz des letzten und ersten Objektes d(p_n,p₁) ergänzt. Gesucht ist nun diejenige Permutation p, welche die Zielfunktion z minimiert.

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 Distanz entspricht dabei zum Beispiel ihrem geographischem Abstand, den aufzuwändenden Kosten einer Reise oder der benötigten Reisezeit. Gesucht ist somit diejenige Reihenfolge der Städte, bei der jede Stadt in einer Rundreise genau einmal besucht wird und der Betrag der gesamten Strecke (Kosten, Reisezeit) ein absolutes Minimum annimmt.

Analyse des zugrunde liegenden Raumes

Aufgrund der breiten Anwendbarkeit des PdH ist eine spezifischere Klassifikation die den zugrunde liegenden Raum der Distanzen (Gewichtungen) beschreibt notwendig. Hierzu werden die Relationen zwischen den Objekten v_i, v_j und ihrer paarweisen Distanz d_ij untersucht.

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

Nichtnegativität und Identität

Um das Optimierungsproblem durch Minimierung sinnvoll lösen zu können fordern wir, dass alle Distanzen nicht negativ seien und die Distanz eines jeden Objektes in Bezug auf sich selbst neutral zur Addition ist.

Nichtnegativitäts- und Identitäts-Bedingung:

$d_{ij}\in {\begin{cases}\mathbb {R} ^{+},&{\mbox{wenn }}i\not =j\\\{0\},&{\mbox{wenn }}i=j\end{cases}}\quad \forall i,j\in \{1,2,..,n\}$

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:

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

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:

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

Veranschaulicht bedeutet dies, dass der Handlungsreisende bei einem Umweg über eine dritte Stadt stehts eine größere Distanz zurücklegt als bei der Wahl der direkten Verbindung zweier Städte.

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):

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

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 Problem des Handlungsreisenden führt, die City-Block-Metrik (auch Manhatten-Metrik) des rektilinearen Problem des Handlungsreisenden und die Maximum-Metrik (auch Chebyshev-Metrik).

Modellierung als Problem ganzzahliger linearer Optimierung

Ein möglicher Lösungsansatz ist die Modellierung des Problem des Handlungsreisenden als ganzzahliges lineares Programm. Dies ist durch die Linearität der Zielfunktion und deren Nebenbedingungen möglich, die sämtlich als lineare Gleichungen oder Ungleichungen fassbar sind. Wird die Distanzbildung aller Objekte zueinander zugelassen, so spricht man von einem unbeschränkten PdH und es ergibt sich folgender Ansatz:

Zielfunktion:

$z=\sum _{i=1}^{n}\sum _{j=1}^{n}d_{ij}b_{ij}\rightarrow \min \quad b_{ij}\in \{0,1\}$

In der Zielfunktion z bezeichnet die Variable d_ij die Distanz der Objekte v_i und v_j sowie b_ij die ihr zugehörige binäre Variable. Sie gibt Information darüber, ob die Distanz d_ij Bestandteil der zu ermittelneden 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\quad \forall i,j\in \{1,2,..,n\}$

Die Bedingung legt in diesem Sinne zunächst fest, dass jedes Objekt v_i nur einmal als Startknoten und nur einmal als Endknoten 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\quad \forall S\subset \{1,2,..,n\}\ 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 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 PdH 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 Algorithmen (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, dass 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 (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.

Variationen & 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 Variationen, so dass eher von einer Familie als von einem einzelnen PdH gesprochen werden muss.

Entsprechende Modifikationen können sowohl als Veränderung der grundlegenden Formulierung, als auch als zusätzliche Nebenbedingungen auftreten. Dabei lassen sich viele wiederum auf die klassische Definition zurückführen. Da gezeigt werden kann, dass sich mit polynomialen Aufwand sämtliche NP-vollständigen Probleme ineinander transformieren lassen und polynomial verlustfrei transformierte NP-vollständige Probleme wiederum in der Klasse NP liegen existiert bisher auch für die auf das klassische PdH rückführbaren Probleme kein effizienter Lösungsansatz.

Einige explizite und in der Literatur häufig verwendete Varianten sind das Multiple Traveling Salesman Problem oder das Single Vehicle Routing Problem. Andere Mitglieder der Familie des PdH wiederum können als größtenteils unabhängig und eigenständige Probleme betrachtet werden, wie beispielsweise das Bottleneck Traveling Salesman Problem, welches sogar in der Klasse P (polynomial lösbar) liegt. Darüber hinaus reicht die Verwandschaft bis hin zu unabhängigen gedanklichen Konstrukten, wie etwa aus der Linearen Optimierung.

Multiple Traveling Salesman Problem (MTSP)

Eine mögliche Erweiterung des Problems des Handlungsreisenden ist das MTSP. Dieses verallgemeinert das klassische PdH indem es auf die Einschränkung eines einzelnen Handlungsreisenden verzichtet. Dabei wird den n - entweder sämtlich (nonlazy Salesman) oder nur zum Teil eingesetzten - Reisenden ein gemeinsamer Start- und Zielknoten (Depot) zugeordnet. Ziel ist es, dass alle Städte einmal von genau einem Handlungsreisenden besucht werden, und dabei die aufsummierten Distanzen (Reisekosten, Reisezeiten, ...) aller Handlungsreisenden zusammen minimiert werden.

Single Vehicle Routing Problem (VRP)

Das MTSP lässt sich zum Single Vehicle Routing Problem erweitern, indem Kapazitäten und Bestellumfänge hinzugefügt werden. Nachwievor gibt es genau ein Depot, in dem alle Touren starten und enden. Ein Kunde soll von genau einer Tour beliefert werden, auf der die Summe der ausgelieferten Bestellmengen nicht größer sein darf, als die Kapazität des Transporters erlaubt. Außerdem darf eine Tour nicht länger sein als die maximale Fahrleistung, die ein Transporter aufbringen kann. Angestrebt wird dabei die Minimierung der aufsummierte Länge der Touren aller Transporter.

Flaschenhals TSP (Bottleneck TSP, BTSP)

Einen effizient lösbaren Sonderfall beschreibt das Bottleneck TSP. Hier soll unter Veränderung der Zielfunktion nun nicht mehr die gesamte Rundreise, sondern nur die maximale in der Rundreise passierte Kante minimiert werden. Dies bewirkt eine möglichst gleichmäßige Verteilung bzw. Glättung der Distanzen (Reisekosten, Reisezeiten, ...). Eine denkbare Variante um Engpässe zu verhindern wäre die Maximierung der minimalen Kante.

Literatur

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

Siehe auch: Routing-Problem