Modellierung als Graph

Damit mathematische Verfahren zur Lösung verwendet werden können, muss eine reale Situation zunächst durch ein einfaches Modell abgebildet werden. Das Problem des Handlungsreisenden lässt sich mit Hilfe eines Graphen modellieren, das heißt: durch Knoten und Kanten. Dabei repräsentieren die Knoten (im Bild: A bis D) die Städte, während jede Kante ${\displaystyle (i,j)}$ zwischen zwei Knoten ${\displaystyle i}$ und ${\displaystyle j}$ eine Verbindung zwischen diesen Städten beschreibt. Zu jeder Kante ${\displaystyle (i,j)}$ gibt es eine Länge ${\displaystyle c_{ij}\geq 0}$ (im Bild: 20, 42, …), die sich je nach Zusammenhang beispielsweise als geographische Länge einer Verbindung, als Reisezeit oder als Kosten einer Reise zwischen zwei Städten interpretieren lässt. Eine Tour (auch Hamiltonkreis genannt) ist ein Kreis in diesem Graphen, der jeden Knoten genau einmal enthält. Ziel ist es, eine möglichst kurze Tour zu finden.

Um die Untersuchung des Problems zu vereinfachen und um sicherzustellen, dass es eine Tour gibt, wird meist angenommen, dass der Graph vollständig ist, dass also zwischen je zwei Knoten immer eine Kante existiert. Dies lässt sich dadurch erreichen, dass überall dort, wo keine Kante existiert, eine künstliche, sehr lange Kante eingefügt wird. Aufgrund ihrer hohen Länge wird eine solche Kante nie in einer kürzesten Tour vorkommen, es sei denn, es gäbe sonst keine Tour.

Je nach Eigenschaften der Kantengewichte werden noch unterschiedliche Spezialfälle des Problems unterschieden, von denen die wichtigsten das symmetrische und das metrische TSP sind.

Formulierung als ganzzahliges lineares Programm

Ein Ansatz zur Lösung des Problems ist die Formulierung als ganzzahliges lineares Programm, in dem die Entscheidungen durch Variablen und die Bedingungen durch lineare Ungleichungen beschrieben werden. Hierfür gibt es mehrere mögliche Varianten. Beispielhaft soll hier eine Modellierung für das symmetrische TSP mit Knotenmenge ${\displaystyle V}$ vorgestellt werden. Für jede Kante ${\displaystyle \{i,j\}}$ wird eine binäre Variable ${\displaystyle x_{\{i,j\}}\in \{0,1\}}$ eingeführt, die für eine gegebene Tour angibt, ob die Kante ${\displaystyle \{i,j\}}$ in dieser Tour enthalten ist (${\displaystyle x_{\{i,j\}}=1}$) oder nicht (${\displaystyle x_{\{i,j\}}=0}$). Jede Tour lässt sich auf diese Art durch Angabe der zugehörigen Variablenwerte angeben, aber nicht jede 0-1-Belegung der Variablenwerte definiert eine Tour. Die Bedingungen dafür, dass eine Variablenbelegung eine Tour definiert, lassen sich durch lineare Ungleichungen ausdrücken, die im Folgenden vorgestellt werden sollen.

Jeder Knoten muss über genau zwei Tourkanten mit den restlichen Knoten verbunden sein, nämlich durch eine hinein- und eine hinausführende Kante:

${\displaystyle \sum _{j\in V\setminus \{i\}}x_{\{i,j\}}=2\qquad (1)}$

für alle ${\displaystyle i\in V}$. In der Summe ist jeder Summand ${\displaystyle x_{\{i,j\}}}$ entweder 1 (in der Tour enthalten) oder 0 (nicht enthalten). Die Summe zählt daher genau die Zahl der Kanten der Tour, die den Knoten ${\displaystyle i}$ als Endknoten haben. Sie muss den Wert 2 annehmen, da jeweils eine Kante hinein- und hinausführen muss. Im nebenstehenden Bild ist ein Knoten ${\displaystyle i}$ mit ein- und ausgehenden Kanten dargestellt, wobei die Tourkanten fett gekennzeichnet sind. An den Kanten stehen die Werte ${\displaystyle x_{\{i,j\}}}$, die zu den oben genannten Summen beitragen.

Die obigen Gradbedingungen werden nicht nur von Touren erfüllt, sondern auch von Variablenbelegungen, die mehrere getrennte Kreise (sogenannte Kurzzyklen) beschreiben, wobei jeder Knoten in genau einem Kreis enthalten ist (siehe Bild). Um so etwas auszuschließen, müssen noch Kurzzyklusungleichungen (auch Subtour-Eliminationsbedingungen genannt) erfüllt werden. Diese von Dantzig, Fulkerson und Johnson 1954 als loop conditions eingeführten Nebenbedingungen besagen, dass jede Knotenmenge ${\displaystyle S\subset V}$, die weder leer ist noch alle Knoten enthält, durch mindestens zwei Kanten der Tour mit den restlichen Knoten verbunden sein muss:

${\displaystyle \sum _{i\in S,\;j\notin S}x_{\{i,j\}}\geq 2\qquad (2)}$

für alle Knotenmengen ${\displaystyle S}$ mit ${\displaystyle 1\leq |S|\leq |V|-1}$. Die Summe zählt alle Kanten der Tour zwischen einem Knoten ${\displaystyle i\in S}$ und einem anderen Knoten ${\displaystyle j\notin S}$. Zur Vermeidung redundanter Ungleichungen kann man sich auch auf Knotenmengen ${\displaystyle S}$ mit mindestens zwei und höchstens ${\displaystyle |V|-2}$ Knoten beschränken. Im nebenstehenden Bild sind wieder die Kanten ${\displaystyle \{i,j\}}$ mit ${\displaystyle x_{\{i,j\}}=1}$ fett gezeichnet, während die übrigen Kanten den Wert ${\displaystyle x_{\{i,j\}}=0}$ haben. Das Hinzufügen der Bedingung (2) für die Knotenmenge ${\displaystyle S}$, die aus den drei linken Knoten besteht, würde dafür sorgen, dass S durch mindestens zwei Tourkanten mit den drei rechten Knoten verbunden sein muss, und damit die beiden gezeigten Kurzzyklen ausschließen. Die Anzahl der Subtour-Eliminationsbedingungen nach Dantzig, Fulkerson und Johnson beträgt ${\displaystyle 2^{n}-2(n-1)}$. Eine 1960 von Miller, Tucker und Zemlin veröffentlichte alternative Darstellung der Nebenbedingungen zur Vermeidung von Subtouren kommt durch Einführung von ${\displaystyle n}$ neuen Variablen, die die Reihenfolge der besuchten Orte angeben, mit nur ${\displaystyle n^{2}-n+1}$ Nebenbedingungen aus. Allerdings bleibt das TSP wegen der Binarität der ${\displaystyle x_{\{i,j\}}}$ auch mit der Formulierung nach Miller, Tucker und Zemlin weiterhin NP-schwer.

Da jeder Vektor ${\displaystyle x=(x_{\{i,j\}})_{i,j\in V,i\neq j}}$ mit Einträgen aus 0 und 1, der alle diese Ungleichungen erfüllt, eine gültige Rundreise definiert, ergibt sich als reformuliertes Problem des Handlungsreisenden: Finde

${\displaystyle \min \;\left\{\sum _{i\in V}\sum _{j\in V\setminus \{i\}}c_{\{i,j\}}x_{\{i,j\}}\;|\;x{\text{ erfüllt (1) und (2) }},\;x_{\{i,j\}}\in \{0,1\}\right\}.\qquad (3)}$

Da die Variablen ${\displaystyle x_{\{i,j\}}}$ nur die Werte 0 oder 1 annehmen, zählt die Summe genau die Längen ${\displaystyle c_{\{i,j\}}}$ der Kanten ${\displaystyle \{i,j\}}$ zusammen, die in der Tour enthalten sind.

Die Zahl der Ungleichungen vom Typ (2) wächst exponentiell mit der Anzahl der Städte, da fast jede der ${\displaystyle 2^{|V|}}$ Teilmengen von Knoten eine Ungleichung definiert. Dieses Problem kann aber mit Hilfe von Schnittebenenverfahren umgangen werden, bei denen diese Ungleichungen erst dann hinzugefügt werden, wenn sie tatsächlich gebraucht werden. Geometrisch lässt sich jede lineare Gleichung als Hyperebene im Raum der Variablen interpretieren. Die Menge der zulässigen Lösungen bildet in diesem Raum ein Polytop, also ein mehrdimensionales Vieleck, dessen genaue Gestalt von den Kosten ${\displaystyle c_{\{i,j\}}}$ abhängt und meist unbekannt ist. Man kann aber zeigen, dass die meisten der Bedingungen (1) und (2) Facetten des TSP-Polytops definieren, also Seitenflächen des Polytops mit höchstmöglicher Dimension. Damit gehören sie zu den stärksten linearen Ungleichungen, die es zur Beschreibung einer Tour geben kann. Es gibt noch viele weitere Facetten, deren zugehörige Ungleichungen allerdings nur in wenigen Fällen bekannt sind. Obwohl (1) und (2) zusammen mit der Beschränkung auf 0/1-Vektoren das Problem vollständig modellieren, können solche zusätzlichen Ungleichungen innerhalb eines Branch-and-Cut-Verfahrens zur Formulierung hinzugefügt werden, um bestimmte LP-Lösungen mit nicht-ganzzahligen Koordinaten auszuschließen (siehe Abschnitt Exakte Lösungsverfahren).

Exakte Lösungsverfahren

Das Problem des Handlungsreisenden kann exakt gelöst werden, indem man die Weglängen aller möglichen Rundreisen berechnet und dann eine mit der kleinsten Weglänge auswählt. Das ist aber schon bei einer kleinen Zahl von Städten nicht mehr praktisch durchführbar. Bei der einfachsten Variante, dem symmetrischen TSP mit ${\displaystyle n}$ Städten, gibt es ${\displaystyle (n-1)!/2}$ verschiedene Rundreisen, das sind bei 15 Städten über 43 Milliarden und bei 18 Städten bereits über 177 Billionen. Wie schnell die Rechenzeit mit wachsender Anzahl von Städten wächst, zeigt das folgende Beispiel: Hat man einen Rechner, der die Lösung für 30 Städte in einer Stunde berechnet, dann braucht dieser für zwei zusätzliche Städte annähernd die tausendfache Zeit; das sind mehr als 40 Tage.

Mit Methoden der ganzzahligen linearen Optimierung, insbesondere Branch-and-Cut, lassen sich dagegen Instanzen in praktisch relevanten Größenordnungen beweisbar optimal lösen oder zumindest die Güte einer gefundenen Tour im Vergleich zu einer Optimallösung abschätzen. Geometrisch interpretiert betrachten diese Verfahren das Problem als konvexes Polytop, also als mehrdimensionales Vieleck im ${\displaystyle m}$-dimensionalen Einheitswürfel ${\displaystyle [0,1]^{m}}$, wobei ${\displaystyle m}$ die Anzahl der Kanten des Graphen ist. Jede Ecke dieses Einheitswürfels beschreibt eine Tour, sofern der zugehörige 0/1-Vektor die oben beschriebenen linearen Ungleichungen erfüllt. Die zu diesen Ungleichungen gehörenden Hyperebenen schneiden daher Ecken des Einheitswürfels ab, die keine Tour darstellen.

Das nebenstehende Bild illustriert dies für das (sehr einfache) TSP mit drei Knoten. Entsprechend den drei möglichen Kanten zwischen diesen Knoten gibt es auch drei binäre Variablen ${\displaystyle x_{1},\,x_{2}}$ und ${\displaystyle x_{3}}$. Es gibt in diesem Fall nur eine mögliche Tour, nämlich diejenige, die alle drei Kanten benutzt. Diese Tour erfüllt die Ungleichung ${\displaystyle x_{1}+x_{2}+x_{3}\geq 2}$, die besagt, dass jede Tour mindestens zwei Kanten haben muss. Außer dieser Tour, die dem Punkt (1,1,1) entspricht, erfüllen auch alle Punkte im rot eingegrenzten Bereich diese Ungleichung. Die zugehörige Schnittebene, die durch die rot gestrichelten Linien aufgespannt wird, schneidet also alle Ecken ab, die unmöglichen Touren mit höchstens einer Kante entsprechen, nämlich den Nullvektor (0,0,0) und die Einheitsvektoren (1,0,0), (0,1,0) und (0,0,1). Die stärkere Ungleichung ${\displaystyle x_{1}+x_{2}+x_{3}\geq 3}$ würde vom Einheitswürfel alles außer dem einzigen zulässigen Punkt (1,1,1) abschneiden. In diesem speziellen Fall lässt sich derselbe Effekt auch schon durch die drei Ungleichungen vom Typ (1) erzielen.

Durch Lösen vieler linearer Programme, Abschneiden nicht benötigter Teile des Einheitswürfels mit Hilfe weiterer Schnittebenen (zum Beispiel vom Typ (2) oder auch Kamm-, Cliquenbaum- und Domino-Parity-Ungleichungen) sowie durch Aufteilung in mehrere Teilpolytope mit Hilfe von Branch-and-Bound wird versucht, eine zulässige 0/1-Ecke mit minimalem Zielfunktionswert zu bestimmen. Eine genauere Beschreibung dieser Verfahren ist im Artikel Ganzzahlige lineare Optimierung zu finden.

Die alleinige Anwendung dieser Verfahren reicht meist nicht aus, um schnell gute Rundreisen zu finden. Ihr Hauptvorteil liegt darin, dass sie Angaben liefern, wie lang eine kürzeste Tour mindestens sein muss. Mit einer solchen unteren Schranke für den optimalen Lösungswert lässt sich abschätzen, wie gut eine gefundene Tour im Vergleich zu einer optimalen Rundreise ist, ohne diese zu kennen. Hat man beispielsweise eine untere Schranke von 100 und eine Tour der Länge 102 gefunden, kann eine optimale Tour nur zwischen 100 und 102 liegen. Die sogenannte Optimalitätslücke, also der maximale relative Abstand zwischen der optimalen Tourlänge und der kürzesten bekannten Tourlänge, beträgt daher (102-100)/100 = 2 %, d. h; der gefundene Lösungswert 102 ist höchstens 2 % vom Optimalwert entfernt. Wenn die Länge einer gefundenen Tour genauso groß ist wie die untere Schranke, ist damit bewiesen, dass die gefundene Lösung optimal ist. Um gute Touren zu finden, können diese exakten Verfahren mit Heuristiken kombiniert werden, von denen einige im nachfolgenden Abschnitt beschrieben werden.

Heuristiken

Um schnell zu brauchbaren Lösungen zu kommen, sind meist durch Heuristiken motivierte Näherungsverfahren notwendig, die aber in der Regel keine Güteabschätzung für die gefundenen Lösungen liefern. Je nachdem, ob eine Heuristik eine neue Tour konstruiert oder ob sie versucht, eine bestehende Rundreise zu verbessern, wird sie als Eröffnungs- (auch Konstruktions-) oder Verbesserungsverfahren bezeichnet. Darüber hinaus gibt es Dualheuristiken, die Mindestlängen für eine Tour berechnen. Metaheuristiken können mehrere dieser Einzelheuristiken unterschiedlich kombinieren. Eine Übersicht über die meisten der hier vorgestellten Heuristiken ist im Abschnitt Übersicht zu finden.

Übersicht

In der folgenden Übersichtstabelle sind für die meisten hier vorgestellten Heuristiken der Typ des Verfahrens, die maximale Laufzeit bei ${\displaystyle n}$ Städten sowie evtl. Gütegarantien für die berechneten Lösungen aufgeführt. Da die Laufzeit und Qualität von Metaheuristiken stark von der Wahl der Teilalgorithmen abhängig sind und sich nicht allgemein angeben lassen, sind sie hier nicht aufgeführt.

Verfahren	Typ	Laufzeit	Max. Abweichung vom Optimum
Nearest-Neighbor-Heuristik	Eröffnungsheuristik	${\displaystyle {\mathcal {O}}(n^{2})}$	Faktor (log(n)+1)/2 (metrisches TSP)
Farthest-Neighbor-Heuristik	Eröffnungsheuristik	${\displaystyle {\mathcal {O}}(n^{2})}$	beliebig groß
Farthest-Insertion-Heuristik	Einfügeheuristik	${\displaystyle {\mathcal {O}}(n^{2})}$	beliebig groß
Nearest-Insertion-Heuristik	Einfügeheuristik	${\displaystyle {\mathcal {O}}(n^{2})}$	beliebig groß, Faktor 2 (metrisches TSP)
Minimum-Spanning-Tree-Heuristik	Eröffnungsheuristik	${\displaystyle {\mathcal {O}}(n^{2}\log(n))}$	wie Nearest-Insertion
Christofides-Heuristik	Eröffnungsheuristik	${\displaystyle {\mathcal {O}}(n^{3})}$	Faktor 1,5 (metrisches TSP)
K-Opt-Heuristik	Verbesserungsheuristik	${\displaystyle {\mathcal {O}}(k!)}$ pro Schritt	beliebig groß
Summe der n kürzesten Kanten	Dualheuristik	${\displaystyle {\mathcal {O}}(n^{2}\log(n))}$	beliebig groß
Länge eines minimalen aufspannenden Baumes	Dualheuristik	${\displaystyle {\mathcal {O}}(n^{2}\log(n))}$	beliebig groß

Praktische Grenzen der Berechenbarkeit

Die größte nicht-triviale Instanz eines (symmetrischen) Rundreiseproblems, die bisher nachweisbar optimal gelöst wurde, ist ein Planungsproblem für das Layout integrierter Schaltkreise mit 33.810 Knoten. Dieser Rekord wurde im Jahre 2005 von William Cook und anderen mit Hilfe einer Kombination aus verschiedenen Heuristiken und dem Branch-and-Cut-basierten Programm Concorde aufgestellt, wobei frühere Teilergebnisse verschiedener universitärer Arbeitsgruppen als Grundlage verwendet wurden. Die bis dahin größte optimal gelöste Instanz bestand aus 24.978 schwedischen Städten, gelöst im Jahre 2004. Mit Hilfe spezieller Dekompositionstechniken und dem Einsatz mehrerer paralleler Computer haben William Cook unter anderem Touren für ein TSP auf über 526 Millionen Sternen gefunden, deren Länge nachweislich höchstens 0,798 % vom Optimum abweicht.

Aus der Tatsache, dass ein TSP einer bestimmten Größe optimal gelöst werden konnte, folgt jedoch nicht, dass jede Instanz dieser Größe optimal gelöst werden kann, da – wie bei den meisten kombinatorischen Optimierungsproblemen – die Schwierigkeit der Lösung stark von den Eingabeparametern (in diesem Fall den Kantengewichten) abhängt. Ein kleineres Problem kann deutlich schwerer lösbar sein; beispielsweise gibt es in der TSPLIB eine aufgrund ihrer vielen Symmetrien schwer optimal zu lösende Instanz mit nur 225 Städten. Bei TSPs, die aus praktischen Anwendungen entstehen, müssen oft noch weitere Nebenbedingungen, wie beispielsweise Zeitfenster, berücksichtigt werden. Daher sind in der Regel die größten optimal lösbaren Probleminstanzen solcher Varianten deutlich kleiner als beim klassischen Problem des Handlungsreisenden, so dass in der Praxis oft auf heuristische Ansätze zur Lösung zurückgegriffen wird. Kombinationen von heuristischen Verfahren mit LP-basierten Verfahren wie Branch-and-Cut werden vor allem im Forschungsumfeld eingesetzt, um mit Hilfe unterer Schranken für die Tourlänge die Qualität von Lösungen und Lösungsverfahren beurteilen zu können.

Mehrere Handlungsreisende

Beim multiple TSP (mTSP) werden die Städte auf mehrere Handlungsreisende aufgeteilt, wobei alle ihre Rundreisen in derselben Stadt starten und dort auch beenden. Jede Stadt muss von genau einem Handlungsreisenden besucht werden. Ziel ist die Minimierung der zurückgelegten Gesamtstrecke. In der Variante mTSP with nonlazy Salesmen werden nur Rundreisen mit mindestens zwei Städten zugelassen, so dass sich jeder Rundreisende tatsächlich fortbewegen muss. Die klassische Version ergibt sich als Spezialfall mit nur einem Handlungsreisenden.

Das Vehicle Routing Problem (VRP) ist ein multiple TSP mit zusätzlichen Transportkapazitätsrestriktionen. Es entstand direkt aus der praktischen Notwendigkeit der Tourenplanung, bei der Waren aus einem zentralen Depot an Kunden ausgeliefert werden sollen. Die Rundreisen entsprechen den Touren von Transportern, die von dem gemeinsamen Depot aus starten und wieder dorthin zurückkehren. Ziel des VRP ist es, alle Kunden möglichst kostengünstig zu beliefern. Dabei kann ein Kunde zwar mehrfach, aber jeweils nur von einem Transporter beliefert werden. In dem Spezialfall, dass die Kapazitäten der Transporter größer sind als die Summe aller Bestellmengen, entspricht das VRP dem mTSP und ist daher ebenfalls NP-schwer. Vom Vehicle Routing Problem (VRP) abgeleitete Varianten sind:

Capacitated VRP (CVRP)

Alle Transporter haben eine maximale Kapazität.

Multiple Depot VRP (MDVRP)

Die Transporter können von mehreren verschiedenen Depots starten.

VRP with Time Windows (VRPTW)

Die Kunden können jeweils nur innerhalb vorgegebener Zeitfenster beliefert werden.

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.

Dynamisches VRP (DVRP)

Zusätzlicher Bedarf kann während der Berechnung entstehen, was vorzeitig zu berücksichtigen ist.

Städtecluster

Beim generalized TSP (GTSP) (deutsch: verallgemeinertes TSP) werden mehrere Städte zu einem Cluster zusammengefasst. Der Handlungsreisende muss aus jedem Cluster genau eine Stadt besuchen. Das TSP ist ein Spezialfall des GTSP, in dem jede Stadt in einem Cluster liegt, der eben nur diese eine Stadt enthält. Jede Instanz des GTSP lässt sich in eine Instanz des einfachen TSP überführen und mit den für dieses Problem bekannten Algorithmen lösen. Aus diesem Grund ist auch das GTSP NP-schwer.

In der Praxis werden die Lösungsalgorithmen des GTSP zum Beispiel dazu verwendet, den Leerweg von CNC-Schneidemaschinen zu optimieren. Diese werden unter anderem in der Textilbranche eingesetzt, um aus einer großen Bahn Stoff kleinere Teile für Kleidungsstücke auszuschneiden. Hierbei stellen die auszuschneidenden Konturen die Cluster und die möglichen Ansatzpunkte des Schneidwerkzeuges auf den Konturen die Städte dar.

Änderungen des Optimierungskriteriums

Beim Prize Collecting TSP (PCTSP) werden dem Handlungsreisenden in jeder Stadt bestimmte Preisgelder bezahlt (beispielsweise Verkaufsumsätze). Um von einer Stadt zur nächsten zu reisen, muss er jedoch Kosten aufbringen. Er soll nun eine vorgegebene Anzahl von Städten und eine Rundreise zwischen diesen Städten so auswählen, dass der Gewinn maximal wird. Da das Problem als Spezialfall die klassische Variante enthält (alle Städte werden besucht und alle Preisgelder sind 0), ist das PCTSP ebenfalls NP-schwer. Eine davon abgeleitete Form ist das Traveling Salesman Selection Problem (TSSP), bei dem zu vorgegebenem ${\displaystyle k}$ eine kürzeste Tour zwischen beliebigen ${\displaystyle k}$ Städten gesucht ist, wobei auf Preisgelder verzichtet wird und metrische Distanzen vorausgesetzt werden.

Beim Bottleneck TSP (BTSP) soll nicht die Summe der Kantenlängen, sondern die Länge der längsten verwendeten Kante minimiert werden. Dies bewirkt eine weniger starke Streuung der einzelnen Distanzen, um möglichen Engpässen, den Flaschenhälsen, entgegenzuwirken. Eine verwandte Variante ist das maximum scatter TSP, bei dem die kleinste verwendete Länge maximiert wird.

Zusätzliche Nebenbedingungen

Eine in Anwendungen häufige Einschränkung sind Zeitfenster, in denen eine Stadt besucht werden muss. Beispielsweise vereinbart ein technischer Kundendienst zur Reparatur von Haushaltsgeräten mit Kunden in der Regel einen Zeitraum, in dem der Besuch des Technikers erfolgt. Dieser Zeitraum muss bei der Tourenplanung berücksichtigt werden.

Beim Online TSP sind nicht alle Städte von vornherein gegeben, sondern werden erst nach und nach bekannt, während der Handlungsreisende schon unterwegs ist. Dieser ändert dann seine Tour so ab, dass neue Städte „möglichst gut“ in seine bisher geplante Tour passen. Diese Variante tritt beispielsweise bei Pannendiensten wie dem ADAC auf, wo Positionen liegengebliebener Autos erst nach und nach bekannt werden und die Zentrale versucht, neue Fälle möglichst günstig in bestehende Touren einzubauen. Da viele Pannenhelfer unterwegs sind und die Zentrale bei der Meldung einer Panne eine ungefähre Zeitangabe macht, wann ein Pannenhelfer eintrifft, handelt es sich um ein Multiple Online TSP mit Zeitfenstern.

Der Paketdienst UPS mit rund 55.000 Kurierfahrern und durchschnittlich 120 Paketen pro Tag und Fahrer verwendete bisher optimierte statische Routen für jedes Fahrzeug, die individuell von den Fahrern gemäß ihrer Erfahrung abgewandelt wurden. Ab 2013 stellt das Unternehmen auf das System ORION (On-Road Integrated Optimization and Navigation) um. Dieses berücksichtigt garantierte Lieferfristen für einzelne Pakete, angemeldete Abholungen und spezielle Kundenklassen mit bevorzugter Bedienung sowie Daten aus dem Verkehrsfluss in Echtzeit. Es lässt erfahrenen Mitarbeitern die Möglichkeit, von der vorgeschlagenen Route abzuweichen. Für dieses Unternehmen kommt als weitere Bedingung hinzu, dass UPS-Fahrer in Städten mit regelmäßigem Straßenraster nicht links abbiegen, weil damit zu große Verzögerungen beim Warten auf Gegenverkehr und ein zu großes Unfallrisiko verbunden sind.