Problem des Handlungsreisenden

Datei:TSP Deutschland 3.PNG

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

Das Problem des Handlungsreisenden (engl. Traveling Salesperson Problem bzw. Traveling Salesman Problem, kurz TSP) ist ein kombinatorisches Problem der Mathematik und der theoretischen Informatik. Es behandelt die Aufgabe eines Handlungsreisenden, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass nach der Rückkehr zum Ausgangsort die gesamte Reisestrecke möglichst kurz ist.

Geschichte

Es ist bemerkenswert, dass die Ursprünge dieses Problems beziehungsweise die Frage nach ihrer erstmaligen wissenschaftlichen Untersuchung unklar sind. Obgleich ihm ähnliche oder gar identische Probleme im alltäglichen Tun und Schaffen der Menschheit wohl schon seit ihrer Existenz aufgetreten sind, wurden alle wesentlichen algorithmischen Ansätze zur Lösung erst seit Mitte des 20. Jahrhunderts entwickelt.

Als frühe Vorläufer können das Königsberger Brückenproblem (1736) von Leonard Euler oder auch das Icosian Game von Hamilton im 19. Jahrhundert gesehen werden. Die erste explizite Erwähnung scheint jedoch auf Karl Menger zurückführbar zu sein, der dieses 1930 in einem mathematischen Kolloquium in Wien folgendermaßen formulierte:

„Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden.“

Schon bald darauf wurde die heute übliche Bezeichnung als Traveling Salesman Problem durch H. Whitney an der Princeton University eingeführt.

Aufgrund seiner intellektuellen Herausforderung und der praktischen Relevanz gewann das Problem in den 1950er und 1960er Jahren zunehmend an wissenschaftlicher Popularität, sowohl in Europa als auch in den USA. Besonders herausragende Beträge entstammen G.B. Dantzig, D.R. Fulkerson und S.M. Johnson, die 1954 die Grundlagen der Polyedrischen Kombinatorik ebneten und sowohl das Schnittebenenverfahren als auch eine Formulierung als lineares Programm entwickelten. Oder auch R.M. Karp, dem im Jahr 1972 der Nachweis, dass das Problem zur Klasse der NP-vollständigen Probleme gehört, gelang.

Seit den 1960er und 1970er Jahren entwickelte sich die Erforschung des Problems allmählich zu einem Vorreiter interdisziplinärer wissenschaftlicher Zusammenarbeit und brachte zahlreiche Publikationen auf den Gebieten der Mathematik, Informatik, Wirtschaftswissenschaften, Chemie, Biologie und anderen hervor.

Allgemeine Definition

Die klassische Formulierung, die üblicherweise zur Einführung dieses Problems verwendet wird und der sie ihren Namen verdankt beschreibt einen Handlungsreisenden, der auf seiner Rundreise bestimmte Städte in beliebiger Reihenfolge zu besuchen hat. Um unnötige Strecken zu vermeiden, plant er seine Reise mit einer möglichst kurzen Gesamtstrecke.

Dieser Kontext beschreibt jedoch nur einen sehr speziellen Fall. Zugunsten einer allgemeinen Definition werden die betrachteten Städte deshalb als beliebige gleichartige Objekte und ihre Abstände zueinander als paarweise Bewertungen interpretiert. Zudem soll nunmehr auch der Fall betrachtet werden, dass die Reisestrecke nicht minimiert wird, sondern lediglich kleiner als eine vorgegebene maximale Strecke sein soll.

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

Endlich viele gleichartige Objekte, die jeweils einer paarweisen Bewertung unterliegen, sollen in einer zyklischen Sequenz so angeordnet werden, dass der Betrag der aufsummierten Bewertungen unmittelbar aufeinanderfolgender Objekte minimiert wird, oder einer gegebenen oberen Schranke genügt.

Mathematische Modellierung

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

Mit kombinatorischen Mitteln kann unter Verwendung der vorhergehenden Definition direkt eine solche mathematische Formulierung des Problems gegeben werden:

Sei $V$ eine endliche Menge n gleichartiger Objekte, und $D=\{d(v_{i},v_{j})|v_{i},v_{j}\in V\}$ eine Menge ihr zugeordneter nichtnegativer Distanzen, dann ist die Permutation $p:\{v_{1},...,v_{n}\}\rightarrow \{p_{1},...,p_{n}\}$ eine Lösung ihres zugehörigen TSP genau dann, wenn die Funktion $z=d(p_{1},p_{2})+d(p_{2},p_{3})+...+d(p_{n-1},p_{n})+d(p_{n},p_{1})$ minimiert wird oder einer gegebenen oberen Schranke genügt.

Diese knappe und exakte Formulierung bietet jedoch nur wenige Ansatzpunkte zur Lösung des Problems. Naheliegend ist es Interpretationen zugrunde zu legen, die sich durch ihre gute Anwendbarkeit auszeichnen. Die wichtigsten Modelle des TSP werden mit Hilfe der Graphentheorie und der ganzzahligen linearen Optimierung beschrieben.

Graphentheoretische Interpretation

Die Graphentheorie liefert ein Modell, welches sich durch seine hohe Anschaulichkeit von anderen hervorhebt und besonders für eine abstrakte Diskussion der Problematik eignet.

In dieser Interpretation werden die Städte als Knoten eines gerichteten Graphen sowie die Distanzen von einer Stadt zu einer anderen als gewichtete Kanten aufgefaßt.

Dabei kann es vorkommen, dass eine Kante nur in eine Richtung weist, wie bei einer Einbahnstraße, mehrere Kanten zwischen zwei Knoten existieren, die Kanten für den Hinweg und den Rückweg unterschiedliche Gewichte haben oder sogar dass zwischen zwei Knoten gar keine Kante existiert. Gibt es mehrere Wege zwischen zwei Städten, so würde man in der Praxis stehts den mit dem geringeren Kantengewicht wählen.

Für den Fall, dass Städte mehrfach besucht werden dürfen, kann man aus dem so entstandenen Graphen stets einen Distanzgraphen bilden. Dieser hat die Eigenschaft, metrisch zu sein. Durch mehrfache Anwendung des Algorithmus von Dijkstra berechnet man hierzu zwischen allen Paaren von Knoten den kürzesten Weg und bildet einen vollständigen kantengewichteten Graphen.

In gerichteten Graphen mit Kantengewichten bezeichnet eine Traveling-Salesman-Tour einen Kreis der alle Knoten miteinander verbindet (Hamiltonkreis). Ein solcher Kreis existiert genau dann, wenn der Graph stark zusammenhängend ist.

Sei nun ein solcher Graph gegeben, so bezeichnet das TSP die Aufgabe in diesem, eine Traveling-Salesman-Tour mit minimaler Länge oder im Falle einer oberen Schranke, eine kürzere als diese zu finden.

Interpretation als lineares Programm

Entgegen dem vorhergehend beschriebenen Modell orientiert sich die Interpretation als ganzzahliges lineares Programm an einer technischen Umsetzung des Problems. Bei diesem Ansatz werden die Bedingungen aufgrund ihrer Linearität sämtlich als lineare Gleichungen oder Ungleichungen aufgefasst.

Es soll eine Bedingung formuliert werden, die auschließlich Distanzen aufsummiert, die in der angestrebten Rundreise enthalten sind. Zu diesem Zweck werden den Distanzen zugehörige binäre Variablen eingeführt:

$\sum _{i=1}^{n}\sum _{j=1}^{n}d_{ij}x_{ij}\!$, mit $d_{ij}x_{ij}\in \{0,d_{ij}\}\!$

Da dieser Ansatz im Allgemeinen jedoch noch keine zulässigen Rundreisen bestimmt, werden die binären Variablen nun mit zusätzlichen Bedingungen belegt. Durch die Eindeutigkeit jeden Objektes in der Rundreise müssen diese genau einmal als Startobjekt und einmal als Zielobjekt zur Ermittlung einer Distanz aufteten:

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

Um schließlich das Auftreten mehrerer getrennter Rundreisen zu vermeiden, müssen sog. Subtour-Eliminationsbedingungen (SEB) formuliert werden. Eine Variante verwendet die Eigenschaft, dass zwischen jeder Teilmenge der Objekte und den restlichen Objekten mindestens zwei Distanzen auftreten, insofern es sich um eine einzelne Rundreise handelt:

$\sum _{i\in S,j\not \in S}x_{ij}\leq 2,\;\forall S\subset V$, mit $2\leq |S|\leq \lfloor n/2\rfloor \!$

Zur Vermeidung redundanter Rechenschritte genügt es sich bei der Auswahl der Teilmengen auf solche zu beschränken, die mindestens zwei und höchstens die Hälfte aller Objekte beinhalten.

Wichtige Spezialfälle

Das Problem tritt in praktischen Anwendungsproblemen in einer Vielzahl von Varianten auf, die im folgenden kurz vorgestellt werden. Dabei wird die allgemeine Fassung des Problems – mit beliebigen Knotenpositionen und Distanzwerten – mit verschiedenen Einschränkungen versehen.

Symmetrisches TSP

Im Gegensatz zum allgemeinen asymmetrischen TSP hat ein symmetrisches TSP für alle Knotenpaare (i,j) dieselbe Distanz in beide Richtungen, d. h $d_{ij}=d_{ji}$. Als Konsequenz davon hat jede Tour in beide Richtungen dieselbe Länge. Die Symmetrie halbiert also die Anzahl der möglichen Touren und wird üblicherweise mit Hilfe eines ungerichteten Graphen modelliert. Ein TSP zwischen realen Städten kann asymmetrisch oder symmetrisch sein, je nachdem, ob beispielsweise durch Baustellen oder Einbahnstraßen der Weg in eine Richtung länger dauert als in die andere oder nicht.

Metrisches TSP

Ein symmetrisches TSP heißt metrisch, wenn seine Distanzen die Dreiecksungleichung erfüllen. Dies bedeutet, dass die direkte Verbindung von i nach j nicht länger sein darf als der Weg von i über einen dritten Knoten k nach j:

$d_{ij}\leq d_{ik}+d_{kj}$

Anschaulich bedeutet dies, dass sich Umwege nicht lohnen. Mehrere, in der Praxis häufig auftretende Distanzfunktionen sind metrisch:

• die Euklidische Metrik des euklidischen TSP,
• die Manhattan-Metrik (auch City-Block-Metrik) des rektilinearen TSP,
• oder die Maximum-Metrik (auch Chebyshev-Metrik).

Position der Objekte

Durch zusätzliche Restriktionen der Position der Objekte erreichen wir stark eingeschränkte TSP, die sich möglicherweise sogar effizient lösen lassen. Durch solche Einschränkungen gewonnene Lösungsverfahren können dann wiederum verwendet werden, um in allgemeineren Problemen teiloptimale Lösungen oder lokal beschränkte optimale Lösungen zu finden.

Die Position der Objekte wird dabei zum Beispiel auf den Rand eines konvexen Polytops oder auf bestimmte geometrische Figuren beschränkt.

Lösungsverfahren

Bei der Suche nach einer Lösung des TSP ist eine der wohl grundlegendsten Fragen die nach der Anzahl der möglichen Rundreisen. Ausgehend von einem vollständigen TSP, stehen dem Handlungsreisenden beginnend mit der Ausgangsstadt jeweils alle Städte zur Auswahl, die er noch nicht besucht hat. Somit ergeben sich insgesamt $(n-1)!$ und im Falle eines symmetrisches TSP $(n-1)!/2$ mögliche Rundreisen für n Städte.

Das Problem des Handlungsreisenden ist NP-vollständig. Dabei erweisen sich die Optimierungs- und Suchvariante als NP-äquivalent, woran sich auch nichts ändert, wenn man sich auf eine bestimmte Metrik beschränkt. Für metrische TSP gibt es jedoch verschiedene polynomiale Heuristiken.

Exakte Lösungsverfahren

Da es nur endlich viele Rundreisen gibt, ist es theoretisch möglich, alle zu enumerieren und sich die kürzeste herauszusuchen. Praktisch ist dies jedoch nicht durchführbar, da es beispielsweise schon bei nur 15 Städten über 87 Milliarden mögliche Rundreisen gibt.

Mit Hilfe von Methoden der ganzzahligen linearen Optimierung, insbesondere Branch-and-Bound in Verbindung mit Schnittebenenverfahren, lässt sich der Lösungsraum auf geschickte Weise einschränken, ohne dabei zulässige Lösungen zu verlieren. Dadurch lassen sich deutlich größere TSP als mit reiner Enumeration beweisbar optimal lösen. Auch wenn in annehmbarer Zeit keine Optimallösung gefunden werden sollte, kann mit Hilfe dieser Verfahren zu jeder zwischendurch gefundenen Rundreise eine Abschätzung angegeben werden, wie viel länger als eine kürzeste Rundreise diese maximal ist.

Heuristiken

Um schnell zu brauchbaren Lösungen zu kommen, sind meist Heuristiken, also Näherungsverfahren, notwendig, die aber meist keine Güteabschätzung für die gefundenen Lösungen liefern. Je nachdem, ob eine Heuristik eine neue Lösung konstruiert oder ob sie versucht, eine bestehende Lösung zu verbessern, wird sie als Eröffnungs- (auch Konstruktions-) oder Verbesserungsverfahren bezeichnet.

Eröffnungsverfahren

Dem intuitiven Vorgehen eines Handlungsreisenden entspricht wohl am ehesten die Nearest-Neighbor-Heuristik (nächster Nachbar). Von einer Stadt ausgehend wählt diese jeweils die nächstgelegene als folgenden Ort aus. Dieses wird sukzessive fortgesetzt, bis alle Städte bereist wurden und der Handlungsreisende zum Ausgangsort zurückgekehrt ist. Dass dies im allgemeinen jedoch nicht die beste Lösung liefert, liegt daran, dass die Distanz zwischen der Ausgangsstadt und der letzten besuchten Stadt bis zuletzt nicht berücksichtigt wird.

Ein ganze Klasse weiterer Eröffnungsverfahren bilden die sogenannten Einfüge-Heuristiken. Die einfachsten Varianten davon sind die Nearest-Insertion-Heuristik (nächste Einfügung) und die Farthest-Insertion-Heuristik (entfernteste Einfügung). Gegeben seien (wenige) einander benachbarte Städte des TSP, für die sich durch exakte Verfahren schnell eine optimale Rundreise ermitteln lässt. Nun wird schrittweise überprüft, welche noch nicht besuchte Stadt am nächsten (beziehungsweise am entferntesten) zu einer der Verbindungslinien der bisherigen Rundreise liegt. Ist diese Stadt gefunden, so wird sie zwischen den ihr am nächsten liegenden Städten in die Tour eingebaut. Das Verfahren wird solange fortgesetzt, bis die Rundreise alle Städte umfasst.

Im Falle eines metrischen TSP kann mit der Minimum-Spanning-Tree-Heuristik (MST) eine Lösung konstruiert werden, die höchstens doppelt so lang ist wie eine kürzeste Tour. Diese Heuristik berechnet zunächst einen minimal aufspannenden 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 für metrische TSP wird durch die Christofides-Heuristik erreicht. Mit ihr kann eine Rundreise berechnet werden, die höchstens 1,5 mal so lang wie eine optimale ist. Hierbei wird statt der Verdopplung der Kanten zusätzlich zur MST-Heuristik eine kleinste perfekte Paarung auf den Knoten ungeraden Grades im minimal aufspannenden Baum berechnet, um einen eulerschen Graphen zu erzeugen. Dieser Algorithmus ist jedoch aufwändiger.

Verbesserungsverfahren

Verbessernde Optimierungsverfahren, auch Post-Optimization-Verfahren (Nach-Optimierung) versuchen, eine bestehende Tour durch kleine Modifikationen zu verkürzen. Führt keine mögliche Abänderung mehr zu einer Verbesserung, so ist ein lokales Optimum gefunden (aber in der Regel kein globales). Die k-Opt-Heuristiken verfolgen diesen Ansatz, indem sie Gruppen von $k$ Kanten in der Tour austauschen (wobei $k$ üblicherweise kleiner als 5 ist).

Problematisch bei solchen Verfahren wird jedoch schnell die Tatsache, dass bei einer vollständigen Durchführung der Aufwand im Vergleich zur Enumeration nicht gesenkt würde. Daher wird das Problem häufig in einzelne Partitionen unterteilt, die jeweils teiloptimiert werden. Eine so gefundene beste Lösung ist in der Regel ein lokales Optimum handelt, welches gegenüber dem globalen wesentlich schlechter sein kann.

Metaheuristische Verfahren

Metaheuristiken kombinieren lokale und globale Suchverfahren in einer abstrakten Strategie für die heuristische Optimierung eines Problems. Einige Metaheuristiken basieren auf lokalen Suchverfahren und versuchen, z. B. mit Hilfe von Tabu-Listen für bereits besuchte Lösungen (Tabu-Suche) das Steckenbleiben in lokalen Minima zu vermeiden.

Andere Verfahren wurden durch die Natur inspiriert. Das Verfahren der simulierten Abkühlung (engl. simulated Annealing, SA) ahmt den Prozess der Bildung von Kristallstrukturen nach. Dabei wird eine vorhandene Rundreise stochastisch approximiert (z.B. durch Kantenaustausch), wobei abhängig von der Optimierungsstufe (Temperatur des Kristalls) auch Verschlechterungen (anfangs auch stärkere, später nur leichte) akzeptiert werden, um eine möglichst optimale Rundreise zu erhalten. Varianten dieses Verfahrens sind der Sintflutalgorithmus und der Bergsteigeralgorithmus.

Eine ganze Klasse weiterer naturinspirierter Verfahren verwendet Schwarmintelligenzen. Bei so genannten Ameisenalgorithmen (engl. Ant Colony Optimization, ACO), wird hierzu das natürliche Verhalten von Ameisen auf der Wegsuche modelliert und beim Verfahren der Partikelschwarmaoptimierung (engl. Particle Swarm Optimization, PSO) das Verhalten von Vogel- oder Fischschwärmen als Vorbild genommen. Einige der derzeit effizientesten Verfahren entspringen den Familien evolutionärer Algorithmen (EA) und genetischer Algorithmen (GA) sowie der Erforschung Künstlicher Intelligenzen (KI). Ob die Anlehnung an natürliche Selektionsprozesse oder das Verhalten von Schwärmen das Finden guter Lösungen beschleunigt, ist umstritten.

Grenzen der Anwendbarkeit

In der Praxis werden meist verschiedene exakte, heuristische und metaheuristische Verfahren in einem Framework zusammengefasst. Die größte Instanz eines Rundreiseproblems, die bisher nachweisbar optimal gelöst wurde, umfasst 24.978 schwedische Städte. Dieser Rekord wurde im Mai 2004 erreicht. Die Instanz wurde von mehreren unversitären Arbeitsgruppen gemeinsam mit einer Kombination aus verschiedenen Heuristiken und dem Branch-and-Cut-basierten Programm Concorde gelöst. Bis dahin bestand die größte optimal gelöste Instanz aus 15.112 deutschen Städten. Mit Hilfe spezieller Dekompositionstechniken und dem Einsatz mehrerer paralleler Computer haben William Cook u. a. Näherungslösungen für TSPs über 526 Millionen Variablen gefunden, die höchstens 0,798% vom Optimum entfernt sind.

Der praktische Nutzen solcher Frameworks besteht jedoch zumeist in der Lösung wirtschaftlicher oder naturwissenschaftlicher Varianten des Rundreiseproblems. Da diese häufig weitere komplizierte Nebenbedingungen (wie Zeitfenster) haben, sind in der Regel auch die größten optimal lösbaren Probleminstanzen solcher Varianten deutlich kleiner als beim klassischen Rundreiseproblem.

Verallgemeinerungen und Varianten

Das in den vorhergehenden Abschnitten beschriebene TSP entspricht der klassischen Variante dieser Problemstellung. Im realen Bezug existiert aber eine nahezu unerschöpflich große Auswahl an beliebig kombinierbaren Varianten, die sich verschiedenen Modellen zuordnen lassen. Diese Modelle bilden die Familie der TSP.

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 ein klassisches TSP zurückführen lassen und somit auch in der Komplexitätsklasse NP liegen. Andere 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

Beim multiple TSP (mTSP) wird die Einschränkung auf einen einzelnen Handlungsreisenden aufgehoben. Die Städte werden also auf mehrere Handlungsreisendeaufgeteilt, wobei alle in der selben Stadt starten und ihre Rundreise wieder in dieser beenden. Ziel ist es, dass alle Städte von jeweils einem Handlungsreisenden einmal besucht werden und dabei die zurückgelegte Gesamtstrecke minimiert wird. In der Variante mTSP with nonlazy Salesmen werden Rundreisen die nur die Ausgangsstadt beinhalten nicht zugelassen. Beide Varianten des mTSP sind NP-schwer.

Definition (mTSP):

Sei $V=\{v_{i}|i\in \{1,\ldots ,n\}\}$ eine endliche Menge gleichartiger Objekte und $D=\{d(v_{i},v_{j})|v_{i},v_{j}\in V\}$ eine Menge ihr zugehöriger Distanzen, so sind die Permutationen $p(j)$, $j\in \{1,2,...,m\}$ verschiedener Partitionen von $V$ genau dann eine Lösung des zugehörigen mTSP, wenn die Summe der Funktionen $z_{j}=d(p_{1},p_{2}(j))+d(p_{2}(j),p_{3}(j))+...+d(p_{n-1}(i),p_{n}(i))+d(p_{n}(i),p_{1})$, $j\in \{1,2,...,m\}$ minimiert wird, oder einer vorgegebenen oberen Schranke genügt.

Für den Fall $m=1$ entspricht diese Definition offensichtlich der des TSP und stellt somit eine mögliche Verallgemeinerung dessen dar. Das mTSP ist ein Spezialfall des Vehicle Routing Problem.

Vehicle Routing Problem

Diese Verallgemeinerung entstand direkt aus der praktischen Notwendigkeit der Tourenplanung. Im Rahmen dieser wird unserer Betrachtung nun eine Auslieferung von Waren an verschiedene Kunden zugrunde gelegt. Die Rundreisen entsprechen nun den Touren von Transportern mit maximalen Transportkapazitäten, die von einem gemeinsamen Depot starten. Angestrebt wird, bei einer vollständigen Abdeckung der Bestellumfänge der Kunden die Summe aller Kosten zu minimieren. Dabei kann ein Kunde zwar mehrfach, jedoch nur jeweils von einem Transporter beliefert werden.

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

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

Beim Prize Collecting TSP (PCTSP) werden dem Handlungsreisenden in jeder Stadt bestimmte Preisgelder bezahlt. Um von einer Stadt zur nächsten zu reisen, muss er jedoch wiederum Kosten aufbringen. Bei einer vorgegebenen Anzahl von Städten, die er besuchen darf, soll er nun versuchen, einen möglichst maximalen Gewinn (bzw. minimalen Verlust) zu erzielen.

Bevor der Handlungsreisende seine Rundreise antritt, muss er sich somit zuerst auf bestimmte Städte festlegen, um ihre optimale Reihenfolge bestimmen zu können.

Definition (PCTSP):

Sei $V=\{v_{i}|i\in \{1,\ldots ,n\}\}$ eine endliche Menge gleichartiger Objekte, $M=\{m(v_{i})|v_{i}\in V\}$ eine Menge ihr zugeorneter Bewertungen und $D=\{d(v_{i},v_{j})|v_{i},v_{j}\in V\}$ eine Menge ihr zugeordneter Distanzen. Zu einer gegebenen Anzahl von k Objekten ist die Permuation p eine Lösung ihres zugehörigen PCTSP genau dann, wenn die Funktion $z=(m_{1}+m_{2}+...+m_{k})-(d(p_{1},p_{2})+d(p_{2},p_{3})+...+d(p_{n-1},p_{n})+d(p_{n},p_{1}))$ maximiert wird, oder einer vorgegebenen unteren Schranke genügt.

Als eine Verallgemeinerung des klassischen TSP, welchem es für den Fall $k=n$ und $m_{1}=m_{2}=...=m_{n}=0$ entspricht, ist das PCTSP ebenfalls NP-schwer. Eine von ihm abgeleitete Spezialform ist das Traveling Salesman Selection Problem (TSSP), welches auf Preisgelder verzichtet und ausschießlich die Einschränkung auf eine euklidische Metrik behandelt.

Bottleneck TSP

Das Botteleneck TSP (BTSP) ist eine weitere Variante des klassischen TSP, welche einer praktischen Anwendung entstammt. Bei diesem soll nicht die Summe der Distanzen, sondern die längste Distanz minimiert werden. Dies bewirkt eine möglichst gleichmäßige Verteilung beziehungsweise Glättung der einzelnen Distanzen, um möglichen Engpässen (Flaschenhälsen) entgegenzuwirken.

Das BTSP ist NP-schwer. Eine zu ihm äquivalente Variante zum TSP ist das 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 TSP 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