Problem des Handlungsreisenden

Das Problem des Handlungsreisenden (PdH) (englisch: Traveling Salesperson Problem bzw. Traveling Salesman Problem (TSP)) ist ein recht populäres und alltägliches Optimierungsproblem aus der Kombinatorik. Es behandelt die Aufgabe eines Handlungsreisenden, eine Reihenfolge für den Besuch mehrere Orte so zu wählen, dass nach der Rückkehr zum Ausgangsort die gesamte Reisestrecke möglichst kurz ist. In der Praxis gestattet man dabei häufig, Orte mehrmals zu besuchen, obwohl die klassische Variante des Problems dies ausschließt.

Datei:TSP Deutschland 3.PNG

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

Allgemeine Definition

Als Problem des Handlungsreisenden (PdH) wird folgende Aufgabe bezeichnet:

Endlich viele gleichartige Objekte v_i, die jeweils einer paarweisen Bewertung d(v_i,v_j) (Gewichtung) unterliegen, sollen durch eine Permutation p:{v₁,...,v_n} → {p₁,...,p_n} in einer zyklischen Sequenz R = (p₁,..., p_n, p₁) so angeordnet werden, dass der Betrag der aufsummierten Bewertungen unmittelbar aufeinanderfolgender Objekte minimiert wird.

Zielfunktion (PdH):

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

dabei ist

• n die Anzahl der Objekte des PdH und
• d(p_i, p_j) die Distanz zwischen dem i-ten und j-ten Objekt der Sequenz R.

In der Funktion z_PdH werden im ersten Teil zunächst die durch p_i und p_i+1 bestimmten Distanzen der Sequenz R beginnend mit p₁ iterativ aufsummiert und schließlich im zweiten Teil um d(p_n,p₁) ergänzt.

Veranschaulichung: Im Kontext des Handlungsreisenden werden die Objekte als Städte und deren Anordnung in einer zyklischen Sequenz als Rundreise zwischen diesen interpretiert. Die Distanzen entsprechen dabei ihren Abständen, den aufzuwendenden Kosten oder der benötigten Zeit. Gesucht ist eine Rundreise mit einer möglichst kurzen Gesamtstrecke, bei der jede Stadt genau einmal besucht wird.

Mathematische Modellierung

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

Hierfür bieten sich beim Problem des Handlungsreisenden die Sprachen der linearen Optimierung und der Graphentheorie besonders an.

Interpretation 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.

Lineares Programm

Durch die Einführung zusätzlicher binärer Variablen sollen bei diesem Ansatz nur solche Distanzen aufsummiert werden, die zu einer Minimierung der Zielfunktion führen.

$z=\sum _{i=1}^{n}\sum _{j=1}^{n}d_{ij}x_{ij}\!$

dabei ist:

• d_ij die Distanz der Objekte v_i und v_j
• x_ij eine ihr zugehörige binäre Variable die bestimmt, ob d_ij aufsummiert werden soll (x_ij = 1), oder nicht (x_ij = 0)

Abdeckung aller Objekte

Im weiteren muss durch zusätzliche Nebenbedingungen gesichert werden, dass durch den Ansatz eine zulässige Rundreise bestimmt wird. Das heißt es muss jedes Objekt genau einmal als Startobjekt und genau einmal als Zielobjekt zur Ermittlung einer Distanz auftreten.

$\sum _{i=1}^{n}x_{ij}=1,\;\forall j\!$und $\sum _{j=1}^{n}x_{ij}=1,\;\forall i\!$

Die Nebenbedingungen legen in diesem Sinne fest, dass genau zwei Distanzen eines jeden Objektes in der Zielfunktion berücksichtigt werden:

• d_ij mit v_i als Startobjekt und einem beliebigen Zielobjekt v_j, sowie
• d_ji mit einem belibigen Startobjekt v_j und dem Zielobjekt v_i

Dabei werden 2n lineare Nebenbedingungen benötigt.

Vermeidung von Subtouren

Um zu vermeiden, dass das lineare Programm eine Lösung erzeugt, in der mehrere getrennte Touren auftreten, müssen sog. [Subtour-Eliminationsbedingungen] (SEB) formuliert werden. Eine Variante dieser SEB besagt, dass zwischen einer Menge S von |S| beliebig ausgewählten Objekten maximal |S|-1 Verbindungen verlaufen:

$\sum _{(i,j)\in \{(i,j)\in A:i,j\in S\}}x_{ij}\leq |S|-1,\forall S\subset V,2\leq |S|\leq \lfloor n/2\rfloor$

Graphentheoretische Interpretation

Entgegen der vorhergehend beschriebenen Darstellung des PdH als lineares Programm, die einer technischen Umsetzung entgegenkommt, wird zur abstrakteren Diskussion häufig eine graphentheoretische Interpretation verwendet.

Modellierung als Graph

Um das Problem graphentheoretisch zu beschreiben, werden die Objekte als Knoten v ∈ V eines Graphen G interpretiert. Zwischen je zwei Knoten werden gerichtete Kanten e ∈ E und ein Kantengewicht f eingefügt, wenn zwischen ihren korrespondierenden Objekten ein Weg existiert.

$G=(V,E,f),\;d=f(e)\!$

Dabei kann es vorkommen, dass die Kante nur in eine Richtung weist (gerichtetes PdH, zum Beispiel bei einer Einbahnstraße), es mehrere Kanten zwischen zwei Knoten gibt (zum Beispiel bei Strassen, Landstrassen, Autobahnen zwischen zwei Objeken (Multigraph)), Kanten für die "Hin- & Rückrichtung" unterschiedliche Gewichte haben (asymmetrisches PdH, ), oder zwischen zwei Knoten gar nicht existiert. Gibt es mehrere Wege zwischen zwei Objekten, so würde man in der Praxis immer den minimal gewichteten wählen und trägt in diesem Fall natürlich auch das kleinste entsprechende Kantengewicht ein. Für den Fall, dass Orte mehrfach besucht werden dürfen, kann man aus dem so entstandenen Graphen stehts 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.

Traveling-Salesman-Tour

In gerichteten Graphen mit Kantengewichten bezeichnet man einen Hamiltonkreis, also einen Kreis, welcher alle Knoten miteinander verbindet als Traveling-Salesman-Tour. Diese kann nur existieren wenn der Graph stark zusammenhängend ist was bedeutet, dass zu jedem Knoten v als Endknoten von einem beliebigen Startknoten w ein Weg existiert. Die Eigenschaft eines Graphen stark zusammenhängend zu sein lässt sich relativ leicht in linearer Zeit prüfen (Zusammenhang von Graphen).

Graphentheoretische Definition

Als Problem des Handlungsreisenden (PdH) wird folgende Aufgabe bezeichnet:

Es soll bestimmt werden, ob eine Traveling-Salesman-Tour der Länge höchstens k existiert, wobei k eine beliebige reelle Zahl ist. Neben diesem Entscheidungsproblem gibt es noch das Optimierungsproblem, das kleinste k zu bestimmen, für das eine Traveling-Salesman-Tour existiert, und das Suchproblem, eine kürzeste Traveling-Salesman-Tour zu finden.

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

Eine noch bessere Approximationsgüte liefert die Christofides-Heuristik, die für das metrische TSP 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.

Klassifikation und Einordnung des Problems

Subklassen

Aufgrund des vielfältigen Auftretens dieser Problemstellung bietet sich eine Unterklassifikation zur gesonderten Betrachtung eingeschränkter Spezialformen an. Hierzu werden die Relationen zwischen den Objekten und ihren zugeordneten Distanzen untersucht.

Als Voraussetzung wird die Definion des klassischen PdH verwendet und schrittweise mit zusätzlichen Restriktionen belegt. Die Distanz wird dabei im Sinne einer allgemeinen Betrachtung aller Objekte des Problems durch i, j, k ∈ {1,2,..., n} indiziert. Zusätzlich wird eine Distanzmatrix D = (d_ij) eingeführt.

Des Weiteren fordern wir noch eine Normierung der Distanzen in dem Sinne, dass wir positive Werte d_ij ≥ 0 für verschiedene zugrunde gelegte Objekte, sowie die Neutralität bezüglich ihrer Addition d_ii = 0, bei identischen Objekten erwarten. Dies ist genau dann der Fall, wenn ihre zugehörige Distanzmatrix D positiv semidefinit ist.

Symmetrie der Distanz

Bei der Betrachtung der Distanz kann unterschieden werden, ob die Reihenfolge zweier Objekte zu ihrer Bildung beiträgt (asymmetrische PdH), oder vernachlässigt werden kann (symmetrische PdH). Im letzteren Fall impliziert dies zu jeder Rundreise R die Existenz einer identisch bewerteten umgekehrten Rundreise R^-1. Die Symmetrie des Problems kann leicht durch eine symmetrische Matrix D verifiziert werden. Dabei erweisen sich symmetrische PdH allerdings grundsätzlich als in asymmetrische PdH überführbar, beziehungsweise als solche lösbar.

$d_{ij}=d_{ji}\!$

Beispiel: Asymetrische Distanz

$d_{11}=0$

$d_{12}=5$

$d_{21}=2$

$d_{22}=0$

Asymetrische Distanzmatrix: 0 5 2 0

Symetrische Distanz

$d_{11}=0$

$d_{12}=5$

$d_{21}=5$

$d_{22}=0$

Symetrische Distanzmatrix (zugleich zugehörigr asymetrische Distanzmatrix): 0 5 5 0

Am Beispiel des Handlungsreisenden könnte hier der 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. durch bessere Verkehrswege) als von Stadt B nach Stadt A und ein asymmetrisches PdH wäre die Folge.

Erfüllung der Dreiecksungleichung

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

Die Dreiecksungleichung fordert nun:

$d_{ik}\leq d_{ij}+d_{jk}\!$

Veranschaulicht bedeutet dies eine mindestens gleich, wenn nicht längere zurückzulegende Strecke für den Handlungsreisenden, wenn er sich dafür entscheidet auf dem Weg von der Stadt A zur Stadt B die Stadt C zu bereisen. Denkt man bei der Distanz jedoch auch an etwaige Reisekosten, kann es durchaus möglich sein, dass sich diese bei bei einem Umweg verringern.

Metrik und Dimension

Insofern die Distanzen sämtlich den vorhergehenden Bedingungen genügen, heißt dieses bei der Existenz einer zugrunde liegenden Distanzfunktion f metrisch. Dabei werden die Berechnungsvorschriften von f verschiedenen Metriken zugeordnet, die Spezialfälle des betrachteten PdH darstellen.

Gängige in Verbindung mit dem PdH erkennbare Metriken sind:

• die Euklidische Metrik des euklidischen PdH,
• die Manhatten-Metrik (auch City-Block-Metrik) des rektilinearen PdH
• und die Maximum-Metrik (auch Chebyshev-Metrik).

In diesen Fällen wird impliziert, dass sich jedes Objekt v_i eindeutig durch einen m-dimensionalen Vektor x_i darstellen lässt.

$d_{ij}=f({\vec {x}}_{i},{\vec {x}}_{j})$ mit ${\vec {x}}_{i},{\vec {x}}_{j}\in \mathbb {R} ^{m}\!$

Die aufgrund seiner Anschaulichkeit wahrscheinlich am häufigsten diskutierte und untersuchte Variante des klassischen PdH ist das 2-dimensionale euklidische PdH. Darüber hinaus werden aber auch Metriken behandelt, die keiner Dimension bedürfen. Ein Beispiel dafür ist die diskrete Metrik d_ij ∈ {1, ∞}, i ≠ j bzw. d_ij ∈ {0, 1}, i ≠ j

Position der Objekte

Durch zusätzliche Restriktionen der Position der Objekte erreichen wir stark eingeschränkte PdH, die sich effizient lösen lassen. Die dadurch gewonnenen speziellen Lösungsverfahren können dann wiederum verwedet werden um in allgemeineren Problemen teiloptimale Lösungen und lokal beschränkte optimale Lösungen zu finden.

Die Position der Objekte wird dabei zum Beispiel auf den Rand eines konvexen Polytops beschränkt. Des Weiteren werden auch Einschränkung auf bestimmte geometrische Figuren behandelt.

Superklassen und Varianten

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

Entsprechende Modifikationen ihrer einzelnen Mitglieder können sowohl durch zusätzliche Nebenbedingungen als auch durch die grundlegende Veränderung der Zielfunktion auftreten. Dabei zeigt es sich, dass sich viele Mitglieder durch Polynomialzeitreduktion auf das klassische PdH zurückführen lassen und somit auch in der Klasse NP liegen. Andere Mitglieder wiederum können als größtenteils unabhängig und eigenständig betrachtet werden, und benötigen somit eine gesonderte Betrachtung, wie beispielsweise das Bottleneck TSP.

Multiple TSP

Die Einschränkung auf einen einzelnen Handlungsreisenden wird aufgehoben und das Problem auf mehrere Handlungsreisende verallgemeinert. Dabei werden diese entweder sämtlich oder nur zum Teil eingesetzt. Alle starten in der selben Stadt und beenden 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.

Definition: Die n Objekte eines klassischen PdH sollen beim multiple TSP (mTSP) auf m zyklische Sequenzen R₁,..., R_m, mit dem gemeinsamen Startobjekt p₁, verteilt werden. Dabei gilt es die Summe aller Distanzen zu minimieren, wobei neutrale Zyklen R_i = (p₁, p₁) entweder zugelassen, oder in der Variante mTSP with nonlazy Salesmen durch eine zusätzliche Restriktion ausgeschlossen sind.

Zielfunktion (mTSP):

$z_{\mathrm {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 Zyklen
• D(R_s) die Distanzsumme des s-ten Zyklus R_s
• n_s die Anzahl der Objekte in R_s
• p_(s,i) das i-te in R_s enthaltene Objekt

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

Einordnung: Das mTSP verallgemeinert das klassische PdH und ist ein Spezialfall des Vehicle Routing Problem.

Vehicle Routing Problem

Im Rahmen der Tourenplanung wird unserer 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.

Einordnung: Das Vehicle Routing Problem (VRP) verallgemeinert das mTSP. Davon abgeleitete Varianten sind:

• Capacitated VRP (CVRP): Die Kapazität der Transporter ist einheitlich.
• Multiple Depot VRP (MDVRP): Die Transporter können von mehreren verschiedenen Depots starten.
• Periodisches VRP (PVRP): Der Bedarf der Kunden wächst in zeitlichen Abständen nach. Betrachtet wird eine bestimmte Zeitdauer.
• Split Delivery VRP (SDVRP): Ein Kunde kann von verschiedenen Transportern beliefert werden.
• VRP with Backhauls (VRPB): Lieferanten und deren Abgabemengen werden berücksichtigt.

Prize Collecting TSP

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

Definition: Aus einem klassischen PdH mit n Objekten soll beim Prize Collecting TSP (PCTSP) eine Untermenge aus k Objekten so gewählt werden, dass die Distanzsumme eines optimalen Zyklus zugleich gegenüber alle k objektigen Zyklen optimal wird. Somit ist auch das Startobjekt p₁ von der Wahl der Objekte abhängig und für jede getroffene Auswahl neu zu bestimmen.

Zielfunktion (PCTSP):

$z_{\mathrm {PCTSP} }(k)=\left(\sum _{i=1}^{k}d({p_{(k,i)},p_{(k,i+1)}})\right)+d({p_{(k,n)},p_{(k,1)}})\rightarrow \min \!$

dabei ist:

• k die Anzahl der Objekte
• p_(k,i) das i-te Objekt in R_k

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

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

Bottleneck TSP

Nicht die gesamte Strecke, sondern nur die längste Einzelstrecke der Rundreise soll minimiert werden. Dies bewirkt eine möglichst gleichmäßige Verteilung beziehungsweise Glättung der einzelnen Strecken, um möglichen Engpässen (Flaschenhals) entgegenzuwirken.

Zielfunktion (BTSP):

$z_{\rm {BTSP}}=\max \left(d(p_{i},p_{i+1})\right)_{i\in \{1,...,n\}}\rightarrow \min \!$

Komplexität: Das Problem ist NP-schwer.

Einordnung: Das Bottleneck TSP (BTSP) ist äquivalent zum maximum scatter TSP.

Literatur

• Lawler, Lenstra, Rinnooy Kan, Shmoys (Hrsg.): The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, 1985, ISBN 0-471-90413-9 +
• W. Domschke: Logistik: Rundreisen und Touren. 4. Aufl., Oldenbourg-Verlag, München - Wien 1997.
• T. Grünert und S. Irnich: Optimierung im Transport, Band II: Wege und Touren. Shaker Verlag, Aachen 2005.

Weblinks

• The Traveling Salesman Problem Home Ausführliche Informationen zum Traveling Salesman Problem
• TSPLIB Sammlung von Beispiel-Instanzen des PdH und verschiedener Varianten
• Spektrum der Wissenschaft: Die optimierte Odyssee Artikel von Martin Grötschel und Manfred Padberg
• The VRP Web Ausführliche Informationen zum Vehicle Routing Problem

Siehe auch: Routing-Problem, Hamiltonkreisproblem, Königsberger Brückenproblem, Tourenplanung