Die Tabu-Suche verständlich erklärt

Wer eine Lieferroute verkürzt, steht irgendwann in einer Sackgasse: Jede kleine Änderung macht sie länger. Ein Merkzettel mit verbotenen Wegen kann trotzdem weiterhelfen. Diese Seite erklärt, wie dieses Verfahren, die Tabu-Suche, arbeitet, was es kostet und wann es sich lohnt.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Eine Route, die nicht mehr besser wird

Ein Lieferwagen soll morgens viele Kunden nacheinander anfahren und dann zum Lager zurückkehren. Gesucht ist die Reihenfolge mit dem kürzesten Weg. Zum Verbessern probiert man kleine Änderungen aus. Eine solche Änderung löst zwei Straßenverbindungen der Route und fährt das Stück dazwischen rückwärts. Dabei kann sich eine Kreuzung auflösen.

Das einfachste Verfahren heißt Abstieg. Es behält eine Änderung nur, wenn die Route kürzer wird. Stellen Sie sich die Länge der Route als Höhe in einem Hügelland vor. Der Abstieg läuft nur bergab und bleibt irgendwann in einer Mulde stehen. Dort führt jede einzelne Änderung bergauf, also zu einer längeren Route. Hinter dem nächsten Hügel kann trotzdem ein tieferes Tal liegen.

Warum ein Schritt bergauf allein nicht reicht

Naheliegend wäre, aus der Mulde den kleinsten Schritt bergauf zu gehen. Das ist die Änderung, die die Route am wenigsten verlängert. Danach beginnt das Problem. Die beste verfügbare Änderung ist nun meist, den eben gemachten Schritt zurückzunehmen. Das verkürzt die Route genau um das, was sie vorher länger wurde. Die Suche tanzt auf der Stelle: hinauf, hinunter, hinauf, hinunter. In der Messung war sie so im Mittel nur wenig besser als ein einziger Abstieg.

Der Merkzettel gegen den Rückweg

Die Tabu-Suche führt einen Merkzettel. Jede Änderung löst zwei Straßenverbindungen. Beide kommen auf den Zettel und sind tabu, also verboten. Eine Änderung, die eine davon wieder einsetzt, ist für eine feste Zahl von Runden nicht erlaubt. Danach streicht man die Verbindung vom Zettel. Die Suche kann also nicht sofort zurück in die Mulde und muss einen anderen Weg nehmen.

Sonst gilt eine einfache Regel: In jeder Runde prüft man alle erlaubten Änderungen und führt die beste aus, auch wenn die Route dadurch länger wird. Zwei Ausnahmen gibt es. Ein Verbot gilt nicht, wenn die Änderung die kürzeste Route ergäbe, die je gefunden wurde. Denn das Verbot soll nur das Pendeln stoppen, keinen Rekord verhindern. Und sind alle Änderungen verboten, führt man die beste davon trotzdem aus. Sonst stünde die Suche still.

Weil die Suche auch bergauf geht, merkt sie sich die beste Route, die ihr unterwegs begegnet.

Wie das gemessen wurde

Gemessen wurde mit einem Programm zum Ausprobieren im Browser, der Demo. Sie erzeugt zufällig 60 Kundenorte und lässt jedes Verfahren eine Route suchen. Das ist ein stark vereinfachtes Rechenbild: Luftlinie, ein Fahrzeug, keine Zeitfenster. „Gemessen“ heißt: im Mittel über viele solche Aufgaben. Die Demo öffnet der erste Knopf unten. Zum Verstehen brauchen Sie sie nicht. Der zweite Knopf führt zum zweiten Teil für Fachleute.

Als Maßstab dient eine Untergrenze: eine Länge, unter die keine Route kommen kann. Eine Rechnung liefert sie, ohne die beste Route zu kennen. Angegeben ist, um wie viel % eine Route länger ist. Außerdem wird der Aufwand gezählt, also wie viele Änderungen ein Verfahren insgesamt prüft. Die Tabu-Suche trat gegen zwei Gegner an. Der erste ist ein einziger Abstieg, der ohne Limit zu Ende läuft. Der zweite sind Neustarts: viele Abstiege von zufälligen Startrouten, wobei die beste Route zählt. Die Neustarts bekamen denselben Aufwand wie die Tabu-Suche.

Was die Messung zeigte

Bei 200 Tausend geprüften Änderungen lag die beste Route der Tabu-Suche im Mittel gut 4 % über der Untergrenze. Der einzelne Abstieg endete knapp 8 % darüber, die Neustarts knapp 5 %. Wie viel Aufwand man hat, ändert das Bild stark. Denn jede Runde prüft alle Änderungen und ist deshalb teuer. Mit wenig Aufwand passen nur wenige Runden hinein:

• Knapper Aufwand (höchstens 50 Tausend): Es reichten nur 6 bis 29 Runden. Eine zufällige Startroute ist sehr lang, weil sie kreuz und quer durchs Gebiet springt. Jede Runde ändert nur eine Kleinigkeit, bis zur ersten Mulde sind viele nötig. Die beste Route lag mehr als 50 % über der Untergrenze, weit hinter dem Abstieg, der dafür ohne Limit bis zur Mulde lief.
• Mittlerer Aufwand (200 Tausend): Die Runden reichen, um die Mulde zu verlassen und weiterzusuchen. Die Tabu-Suche lag im Mittel vor beiden Gegnern, vor den Neustarts aber nur knapp. Einzelne Läufe lagen weit auseinander, sicher ist dieser Vorsprung nicht.
• Großer Aufwand (viel mehr als 200 Tausend): Der knappe Unterschied zu den Neustarts verschwand, und die Tabu-Suche und die Neustarts lagen im Mittel nahe beieinander. Vermutlich finden auch die Neustarts dann bei vielen Versuchen eine gute Mulde.

Auch die Dauer des Verbots zählt. Ohne Verbot pendelt die Suche, und das Ergebnis lag nahe beim einzelnen Abstieg. Bei 20 Runden war das Ergebnis im Mittel am besten, bei 200 Runden etwas schlechter. Der Unterschied dazwischen ist klein gegenüber der Streuung der Läufe. Gemessen ist nur: Der Lauf dauerte rund hundert Runden, ein Verbot von 200 Runden lief darin also nie ab. Warum das schadet, ist eine Vermutung: Viele Dauerverbote könnten sinnvolle Änderungen blockieren.

Schließlich zählte die Startroute. Wer nicht zufällig, sondern immer zum nächstgelegenen Kunden weiterfuhr, kam mit der Tabu-Suche unter 2 % über die Untergrenze statt auf gut 4 %. Bei nur gut hundert Runden bleibt ein guter Start offenbar erhalten.

Wie ernst ist das Rechenbild zu nehmen?

Die Aussagen beschreiben die Messung mit zufälligen Kundenorten, Luftlinie und einem Fahrzeug, nicht die Wirklichkeit mit Straßen und Zeitfenstern. Ob die beste Dauer des Verbots auch bei anderen Kundenzahlen gilt, wurde nicht gemessen. Als Gegner diente nur ein Abstieg, der jedes Mal alle Änderungen prüft; wie der Vergleich mit einem schlaueren ausgeht, der nur nahe Kunden prüft, ist offen.

Häufige Missverständnisse

• „Ein Verbot macht die Suche zufällig.“ Nein, es wird nie gewürfelt. Bei gleicher Startroute und gleicher Einstellung läuft sie jedes Mal gleich ab. Nur die Startroute wird zufällig gewählt.
• „Die Tabu-Suche ist besser als Neustarts.“ Gegen den einzelnen Abstieg gewann sie bei mittlerem Aufwand. Gegen die Neustarts lag sie nur im Mittel knapp vorn, und das nicht sicher. Bei knappem Aufwand verlor sie klar, bei großem lagen beide nahe beieinander.
• „Die Route am Ende ist das Ergebnis.“ Die Suche steht am Ende irgendwo auf ihrem Weg, und der führte auch bergauf. In der Messung war die Route am Ende im Mittel länger als die beste unterwegs.

Woran Sie das im Alltag erkennen

• Beim Umräumen oder an einer Sitzordnung wechseln Sie zwischen zwei Anordnungen hin und her, weil jede Änderung die letzte rückgängig macht. Das ist das Pendeln.
• Sie setzen sich eine Frist: Was ich gerade geändert habe, fasse ich erst später wieder an. Das ist ein Merkzettel mit Verfallsdatum.
• Sie fotografieren die beste Anordnung, bevor Sie Neues probieren. So darf der Versuch auch mal schlechter werden, ohne dass der beste Stand verloren geht.

Was Sie mitnehmen

• Wer Verschlechterungen zulässt, braucht eine Bremse gegen den Rückweg, sonst bleibt er bei zwei Zuständen hängen.
• Fragen Sie bei jedem Verfahren, was ein einzelner Schritt kostet und ob der Aufwand für genug Schritte reicht.
• Prüfen Sie bei jeder Stellschraube, ob mehr wirklich besser ist: Ohne Verbot half es kaum, und ein sehr langes brachte nicht mehr.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er beschreibt die Tabu-Suche (Glover 1986, formalisiert 1989/90) so, wie sie an einer Lieferrunde gemessen wurde.

• Problem: kürzeste Rundtour über \(N = n+1\) Knoten (Depot und \(n\) Stopps) in einem Gebiet von 100 × 100 km mit euklidischen Entfernungen \(d_{ij}\), ein Fahrzeug, keine Kapazitäten oder Zeitfenster. \(L(\pi)\) ist die Länge der Tour \(\pi\). Die Stopps liegen gleichverteilt oder zu einem Anteil in fünf Gruppen. Gemessen wird mit 10 bis 200 Stopps, vorausgesetzt sind 60 gleichverteilte.
• Nachbarschaft: nur 2-opt. Ein Zug \((i,j)\) entfernt in der Tourfolge \(t_0, t_1, \dots\) die Kanten \((t_i, t_{i+1})\) und \((t_j, t_{j+1})\), fügt \((t_i, t_j)\) und \((t_{i+1}, t_{j+1})\) ein und kehrt dazu das Stück zwischen den Positionen \(i+1\) und \(j\) um. Gültig sind Paare \(i < j\) mit \(j \ge i+2\), deren Kanten keinen Knoten teilen. Die Nachbarschaft hat rund \(n^2/2\) Züge.
• Verfahren: In jeder Iteration wird die volle Nachbarschaft bewertet und der beste erlaubte Zug ausgeführt, auch wenn er die Tour verlängert. Tabu ist ein Zug, der eine der zuletzt entfernten Kanten wieder einfügen würde. Gemerkt wird die beste besuchte Tour. Das Verfahren ist deterministisch: Bei gleicher Startroute und gleicher Einstellung ist der Lauf gleich, nur die Startroute streut.
• Budget: Gezählt werden bewertete Nachbarn. Eine Iteration verbraucht rund \(n^2/2\) davon, anders als bei Verfahren mit Kandidatenliste, die je Iteration nur wenige Nachbarn bewerten. Der Lauf endet, sobald das Budget \(B\) erreicht ist; die letzte Iteration darf es überschreiten.
• Regler und Voreinstellung: Tenure \(\tau\) von 0 bis 200 (voreingestellt 20); Budget \(B\) von 10 Tausend bis 2 Millionen (voreingestellt 200 Tausend); Startroute zufällig (voreingestellt) oder nach dem Nächster-Nachbar-Verfahren.
• Vergleichsverfahren: Erstens ein einzelner Hill-Climbing-Abstieg, also ein reiner Abstieg, der nur verbessernde Züge ausführt, aus derselben Startroute (2-opt, Regel beste Verbesserung, ohne Budget bis zum lokalen Optimum). Das ist dieselbe Zugauswahl wie die Tabu-Suche ohne Gedächtnis. Zweitens Hill Climbing mit Neustarts: Abstiege aus zufälligen Startrouten mit voller Prüfung der Nachbarschaft (2-opt, Regel erste Verbesserung), bis das Budget \(B\) erreicht ist; der erste läuft immer zu Ende. Warum die Neustarts die andere Regel nutzen, begründet die Demo nicht; ob die Wahl das Ergebnis ändert, ist nicht gemessen. Kandidatenlisten (nur die nächsten Nachbarn je Knoten werden als Zugpartner geprüft) und Don't-Look-Bits (Knoten, an denen zuletzt kein Zug half, werden übersprungen) gibt es in keinem der beiden.
• Kennzahl: Abstand zur 1-Baum-Schranke \(w\) in Prozent. Gemeint ist die verbesserte Schranke nach Held und Karp: Die Knoten bekommen Gewichte (Lagrange-Multiplikatoren), die per Subgradientenverfahren so gewählt werden, dass der minimale 1-Baum möglichst lang wird; der einfache 1-Baum ohne Gewichte läge deutlich tiefer. Die Demo prüft die Schranke gegen Brute-Force (n = 8) und gegen CP-SAT, einen Löser für ganzzahlige Optimierung, der kleine Instanzen exakt löst (n = 20). Alle Befunde beziehen sich auf diese Schranke, nicht auf das Optimum; wie weit sie bei 60 Stopps unter dem Optimum liegt, ist hier nicht angegeben.
• Instanzen: fünf feste Instanzen mit je drei zufälligen Startrouten, zusammen fünfzehn Läufe. Jede Zeile der Befunde ist, wenn nichts anderes steht, das Mittel über diese fünfzehn Läufe.

Die Formeln

Erlaubt ist ein gültiger Zug, wenn keine der beiden neu eingefügten Kanten tabu ist oder wenn er das Aspirationskriterium erfüllt. Die Iteration wählt unter den erlaubten Zügen den mit der kürzesten Tour danach. In der folgenden Formel steht die Einschränkung auf erlaubte Züge nicht im Index, sondern nur in diesem Satz:

\[\pi' = \arg\min_{(i,j) \text{ gültig}} L(\pi \text{ mit Zug } (i,j))\]

Aspiration heißt: Ein tabuer Zug ist trotzdem erlaubt, wenn er die beste bisher gefundene Tour \(\pi_{\text{best}}\) unterbietet:

\[L(\pi') < L(\pi_{\text{best}})\]

Die Tabu-Liste führt je Kante \(\{u,v\}\) die Iteration \(\text{tabu}(u,v)\), bis zu der sie verboten ist. Nach einem Zug, der die Kanten \(e_1, e_2\) entfernt, werden beide für die Dauer der Tenure \(\tau\) gesperrt:

\[\text{tabu}(e_1) \leftarrow \text{tabu}(e_2) \leftarrow \text{aktuelle Iteration} + \text{Tenure}\]

Sind alle gültigen Züge tabu und keiner erfüllt die Aspiration, wird der beste gültige Zug trotzdem ausgeführt (Notfall-Überschreibung). Bei Tenure 0 tritt das nie auf. Bei sehr langer Tenure kann es auftreten, und der Test der Demo mit zwölf Knoten und einer Tenure von zehntausend zeigt es. Es ist aber nicht zwangsläufig: Nachrechnung dieser Seite mit dem Demo-Code, keine Aussage der Demo, ergab keine Überschreibung in allen fünfzehn Läufen des Standardfalls mit Tenure 50 bis 200, ebenso bei mittleren Instanzen mit einer Tenure weit über der Iterationszahl. Plausibel ist der Grund: Jede Iteration sperrt nur zwei Kanten, bei gut hundert Iterationen also rund zweihundert von rund \(n^2/2\) möglichen Kanten, und ein Zug ist erst tabu, wenn eine seiner beiden neuen Kanten gesperrt ist. Alle Züge zugleich sind nur bei kleinen Instanzen oder sehr langen Läufen tabu. Die Kennzahl der Befunde ist der Abstand zur Schranke \(w\):

\[100 \cdot (L - w)/w\]

Herleitung: Pendeln ohne Tabu und die Kosten einer Iteration

Rechnung dieser Seite, keine Aussage der Demo. Erstens das Pendeln: Sei \(\pi_0\) ein 2-opt-Optimum, kein Zug hat also eine negative Längenänderung. Mit Tenure 0 führt die Suche den Zug \((i,j)\) mit der kleinsten Änderung \(\Delta \ge 0\) aus und erreicht \(\pi_1\). Derselbe Zug \((i,j)\) kehrt dasselbe Stück noch einmal um, ist in \(\pi_1\) gültig und hat die Änderung \(-\Delta\). Er führt zurück nach \(\pi_0\) und ist der beste Zug, solange kein anderer Zug in \(\pi_1\) eine Änderung unter \(-\Delta\) hat. Dann pendelt die Suche zwischen zwei Touren. Ein solcher anderer Zug \(a\) mit Änderung \(\Delta_a < -\Delta\) ist möglich: Die Folge aus \((i,j)\) und \(a\) verkürzt \(\pi_0\) um \(-\Delta - \Delta_a\) und widerspricht der 2-opt-Optimalität von \(\pi_0\) nicht, denn diese betrifft nur einzelne Züge.

Mit Tenure größer als 0 fügt der Rückzug genau die beiden eben entfernten Kanten wieder ein und ist tabu. Aspiration greift hier nicht: Die Tour \(\pi_0\) ist nicht kürzer als \(\pi_{\text{best}}\), die Bedingung ist streng. Die Suche muss also einen anderen Zug nehmen.

Zweitens die Kosten: Die Zahl der Iterationen ist ungefähr das Budget geteilt durch die Größe der Nachbarschaft, \(B/(n^2/2)\). Das passt zu den gemessenen Iterationszahlen: 10 bis 50 Tausend Budget ergeben bei 60 Stopps 6 bis 29 Iterationen, 200 Tausend rund 114, und bei 200 Stopps kostet eine Iteration rund 20 Tausend Bewertungen, 1 Million Budget reicht dann für rund 50 Iterationen. Die Abweichungen nach oben kommen daher, dass die letzte Iteration das Budget überschreiten darf.

Drittens ein Vergleichswert, Nachrechnung dieser Seite mit dem Demo-Code: Ein einzelner Abstieg macht bei 60 Stopps im Mittel gut 50 Züge und verbraucht rund 100 Tausend Bewertungen. Bis zum ersten lokalen Optimum geht also etwa die Hälfte der Iterationen des Standardfalls drauf. Das passt zum Befund unten, dass das Ergebnis bei 100 Tausend Budget etwa dem eines Abstiegs entspricht.

Befunde

Wenn nichts anderes steht, gilt der Standardfall: 60 gleichverteilte Stopps, Tenure 20, Budget 200 Tausend, zufällige Startroute. Angegeben ist der Abstand der besten Tour zur 1-Baum-Schranke in Prozent, gemittelt über 5 feste Instanzen mit je 3 Startrouten. Hill Climbing mit Neustarts bekommt dasselbe Bewertungsbudget wie die Tabu-Suche; der einzelne Abstieg ist nicht budgetiert und läuft bis zum lokalen Optimum.

Frage	Befund
Schlägt die Tabu-Suche die beiden Gegner im Standardfall?	Den einzelnen Abstieg ja: 4,19 % gegen 7,85 %, in vierzehn von fünfzehn Läufen besser (Nachrechnung dieser Seite). Hill Climbing mit Neustarts (4,88 %) nur im Mittel: Der Unterschied liegt innerhalb der Streuung, die Tabu-Suche ist nur in neun von fünfzehn Läufen besser.
Wie stark streuen die einzelnen Läufe?	Standardfall, Nachrechnung dieser Seite mit dem Demo-Code: Die Standardabweichung der fünfzehn Läufe beträgt gut zwei Prozentpunkte, der beste Lauf liegt unter einem Prozent, der schlechteste über neun Prozent. Der Standardfehler des Mittels von 4,19 % ist damit rund ein halber Prozentpunkt.
Wie hängt das vom Budget ab?	Bei 10 / 25 / 50 Tausend Budget 287,8 / 155,1 / 54,7 % (nur 6 bis 29 Iterationen), also weit hinter einem Abstieg. Diese Touren sind unfertig: Die zufällige Startroute liegt mehrere hundert Prozent über der Schranke (Nachrechnung dieser Seite), ein Abstieg braucht gut fünfzig Züge, die Suche macht aber nur 6 bis 29 Iterationen. Hill Climbing mit Neustarts besteht bei diesen Budgets aus dem ersten, immer zu Ende laufenden Abstieg und liegt bei dessen Wert (7,85 %). Bei 100 Tausend 7,9 %, etwa so gut wie ein Abstieg. Bei 200 Tausend / 500 Tausend / 1 / 2 Millionen 4,2 / 3,1 / 2,3 / 1,9 %. Gegen die Neustarts liegt die Tabu-Suche bei 200 Tausend im Mittel vorn (4,19 gegen 4,88 %), bei 2 Millionen sind beide gleichauf (1,94 gegen 1,87 %).
Wie wirkt die Tenure?	Tenure 0 / 5 / 10 / 20 / 50 / 200 ergibt 7,54 / 6,12 / 5,18 / 4,19 / 4,52 / 4,52 % bei 200 Tausend Budget. Tenure 0 liegt weit hinter Tenure 20 (ein Vielfaches des Standardfehlers) und dicht bei einem einzelnen Abstieg. Tenure 20 hat den kleinsten Mittelwert, doch gegenüber 50 und 200 liegt der Unterschied innerhalb der Streuung: Tenure 20 ist nur in sechs von fünfzehn Läufen besser als 50 (Nachrechnung dieser Seite).
Was passiert bei größeren Instanzen?	Bei 200 Stopps und 1 Million Budget (nur rund 50 Iterationen) liegt die beste Tour 307 % über der Schranke, Hill Climbing mit Neustarts bei 9,5 %. Ein Abstieg braucht dort gut zweihundert Züge und mehrere Millionen Bewertungen (Nachrechnung dieser Seite), mehr als das Budget. Die Tabu-Suche endet daher weit vor ihrem ersten lokalen Optimum, und die Neustarts bestehen nur aus dem einen, trotzdem zu Ende laufenden Abstieg.
Zählt die Startroute?	Ja: Nächster-Nachbar-Start 1,50 % gegen zufälligen Start 4,19 % (Standardfall, 200 Tausend Budget).

Was die Messung zeigt und was nicht

Die Befunde sind Aussagen über zufällig erzeugte Instanzen und die Regler der Demo. Was daraus folgt und was offen bleibt:

• Stichprobe: Jede Zeile mittelt über fünfzehn Läufe. Die Läufe streuen stark (Nachrechnung dieser Seite mit dem Demo-Code, Standardfall): der beste lag unter einem Prozent, der schlechteste über acht Prozent. Ein einzelner Lauf kann das Urteil der Demo gegen die Neustarts also kippen; die Mittelwerte stützen die Aussagen, nicht der Einzelfall. Die fünfzehn Läufe teilen sich fünf Instanzen und sind nicht unabhängig, der Standardfehler ist darum nur eine grobe Größe. Die Tests der Demo prüfen die Tabu-Werte als Bänder, nicht als exakte Werte.
• Bezugsgröße: Alle Prozentwerte sind Abstände zur 1-Baum-Schranke. Da die Schranke höchstens das Optimum erreicht, sind die Abstände zum Optimum kleiner.
• Das Fenster gegen die Neustarts: Bei 200 Tausend Budget liegt die Tabu-Suche im Mittel um knapp sieben Zehntel Prozentpunkte vor den Neustarts (4,19 gegen 4,88 %), bei 2 Millionen sind beide gleichauf. Das ist kein abgesicherter Vorsprung: Nachrechnung dieser Seite mit dem Demo-Code, paarweise je Lauf, ist der Standardfehler dieser Differenz rund ein Prozentpunkt, und die Tabu-Suche ist nur in neun von fünfzehn Läufen besser. Für die Budgets dazwischen: Bei 500 Tausend liegen die Neustarts im Mittel vorn, bei 1 Million die Tabu-Suche, beide Unterschiede unter einem Drittel Prozentpunkt, ebenfalls innerhalb der Streuung. Gegen den einzelnen Abstieg dagegen gewinnt die Tabu-Suche ab 200 Tausend Budget (im Standardfall in vierzehn von fünfzehn Läufen). Ein belegter Vorsprung gegen die Neustarts besteht in keinem gemessenen Budget; die Aussage „ab 200 Tausend klar besser“ belegt die Messung nicht.
• Gegner: Die Neustarts prüfen bei jeder Änderung die volle Nachbarschaft. Ein Abstieg mit Kandidatenliste und Don't-Look-Bits, der je Versuch weit weniger Bewertungen braucht, wurde nicht verglichen. Der Vorsprung gegen den Abstieg kann mit einem solchen Gegner kleiner ausfallen oder verschwinden; das ist hier nicht gemessen. Auch die beiden Abstiegsregeln (beste Verbesserung beim einzelnen Abstieg, erste Verbesserung bei den Neustarts) wurden nicht gegeneinander getestet.
• Letzte gegen beste Tour: Nachrechnung dieser Seite mit dem Demo-Code: Im Standardfall liegt die letzte Tour der Suche nahe beim Niveau eines einzelnen Abstiegs, die beste deutlich darunter. Das Ergebnis ist ein Rekord auf dem Weg, nicht der Endpunkt der Suche.
• Tenure: Die Zahlen für 50 und 200 sind gleich, bei nur rund 114 Iterationen im Standardfall. Nachrechnung dieser Seite: Die beste Tour ist bei beiden Werten in allen fünfzehn Läufen dieselbe, die Läufe unterscheiden sich erst nach dem Bestwert; bis dahin ist offenbar keine Sperre abgelaufen, die für die Wahl des Zuges gezählt hätte. Dass Tenure 20 der beste Wert ist, ist in den Befunden nur für ein Budget (200 Tausend) belegt und gegenüber 50 und 200 innerhalb der Streuung; eine weitere Messung bei 1 Million Budget im Quelltext der Demo, die ich nachgerechnet habe, zeigt einen größeren Abstand zugunsten von 20, steht aber nicht in der Dokumentation. Dass lange Verbote „zu viele sinnvolle Züge blockieren“, ist eine Erklärung, keine Messung.
• Ohne Tabu: Tenure 0 pendelt in einem Test der Demo am Ende zwischen zwei Touren, geprüft an einer kleinen Instanz. Nachrechnung dieser Seite: Im Mittel liegt Tenure 0 etwas vor dem Abstieg (7,54 gegen 7,85 %), und in einzelnen der fünfzehn Läufe ist es besser. Die Suche kommt also gelegentlich über das erste Optimum hinaus, es ist kein reines Pendeln.
• Startroute: Der Vorteil des Nächster-Nachbar-Starts ist nur bei einem Budget gemessen. Die Erklärung, bei rund 114 teuren Iterationen sei ein Vorsprung schwer aufzuholen, ist eine Deutung und kein Test.
• Größe und Nachbarschaft: Die Befunde gelten für 60 Stopps, die Größe 200 ist an einem Budget gemessen. Es gibt nur die 2-opt-Nachbarschaft und keine Variante mit Kandidatenliste; sie wäre der naheliegende nächste Schritt, ist aber nicht gebaut.
• Szenario und Rechenzeit: synthetische euklidische Instanzen, ein Fahrzeug, keine Kapazitäten oder Zeitfenster. Rechenzeiten hängen vom Rechner und der Python-Version ab und sind nur als Größenordnung geprüft.

Wie die Demo geprüft ist

• Tabu-Verwaltung: Eine unabhängige Nachrechnung baut die Tabu-Liste allein aus der öffentlichen Regel neu auf und bestätigt: Ohne Notfall-Überschreibung ist der gewählte Zug in jeder geprüften Iteration der beste erlaubte (eine Instanz mit sechzehn Knoten, dazu vierzig kleine Zufallsinstanzen gegen eine Neuimplementierung), eine entfernte Kante ist genau Tenure Iterationen gesperrt, und Aspiration überschreibt ein Verbot nur bei einem neuen Bestwert.
• Grenzfälle: Bei Tenure 0 greift die Notfall-Überschreibung nie. Bei sehr langer Tenure greift sie im Test an einer Instanz mit zwölf Knoten und einer Tenure von zehntausend; für größere Instanzen gibt es keinen solchen Test.
• Kern: 2-opt gegen Brute-Force, Abstieg strikt monoton und im lokalen Optimum, Bewertungsbudget, 1-Baum-Schranke gegen Brute-Force (n = 8) und CP-SAT (n = 20).
• Messzahlen: Die Tabu-Werte der Befunde stehen als Bänder in Tests (teils sehr weit, etwa um hundert Prozentpunkte bei den extremen Budgets), jeweils als Mittel über die festen Instanzen und Startrouten. Die Werte der Neustarts sind nur im Standardfall getestet; 9,5 % bei 200 Stopps und 1,87 % bei 2 Millionen Budget stehen in keinem Test.

Quellen

• Glover, F. (1986): Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13(5), 533–549.
• Glover, F. (1989, 1990): Tabu Search, Teil I und II. ORSA Journal on Computing 1(3), 190–206 und 2(1), 4–32.
• Glover, F., & Laguna, M. (1997): Tabu Search. Kluwer.
• Held, M., & Karp, R. M. (1970): The traveling-salesman problem and minimum spanning trees. Operations Research 18(6), 1138–1162.
• Croes, G. A. (1958): A method for solving traveling-salesman problems. Operations Research 6(6), 791–812.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/tabu-search-demo.

Die Jahre bei Glover (1986, 1989/90) stehen in der README der Demo. Titel, Zeitschriftenangaben, das Buch sowie Held–Karp und Croes stammen aus dem Gedächtnis und sind nicht gegen die Originale geprüft. Die Herleitung des Pendelns und die Nachrechnungen mit dem Demo-Code sind Rechnungen dieser Seite und stehen nicht in der Dokumentation. Die Erklärungen zur Notfall-Überschreibung und zu Tenure 50 und 200 sind ebenfalls Nachrechnung beziehungsweise Deutung dieser Seite.