🚚 Lieferrouten-Optimierer — Simuliertes Ausglühen live

Simuliertes Ausglühen ist eine probabilistische Optimierungstechnik, inspiriert vom metallurgischen Prozess, ein Metall zu erhitzen und langsam abzukühlen, sodass sich seine Atome in einer energiearmen Kristallstruktur einfinden. Angewendet auf das Handlungsreisenden-/Fahrzeugrouting-Problem ist die „Energie“ die gesamte Tourdistanz. Bei hoher Temperatur akzeptiert der Algorithmus viele verschlechternde Züge, was ihm erlaubt, breit zu erkunden und aus schlechten lokalen Anordnungen herauszuspringen; mit fallender Temperatur wird er zunehmend gierig und verfeinert die Tour, bis sie nahe einer kurzen Route konvergiert. Er ist beim Routing beliebt, weil der Suchraum möglicher Stopp-Reihenfolgen fakultätsgroß ist, viel zu groß für erschöpfende Suche, doch 2-opt-Nachbarschaften kombiniert mit Ausglühen finden zuverlässig Touren innerhalb weniger Prozent des Optimums.

Ein 2-opt-Zug entfernt zwei Kanten aus der Tour und verbindet die vier Endpunkte auf die einzige andere Weise neu, die eine einzelne geschlossene Schleife erhält, was der Umkehrung der Reihenfolge der Stopps zwischen den zwei Schnittpunkten entspricht. Es ist der einfachste lokale Suchzug, der eine Tour entkreuzen kann: Wo immer sich zwei Routensegmente auf der Karte kreuzen, begradigt genau ein 2-opt-Zug sie und verkürzt die Gesamtdistanz. Da sich nur zwei Kanten ändern, lässt sich die Änderung der Tourlänge (das Delta) berechnen, indem nur diese zwei alten und zwei neuen Kantenlängen verglichen werden, ohne die gesamte Route neu zu summieren.

Nachdem das Kosten-Delta eines Kandidatenzugs berechnet wurde, akzeptiert der Algorithmus immer Züge, die die Tour verkürzen (Δ < 0). Für Züge, die sie verlängern, akzeptiert er mit Wahrscheinlichkeit e^(−Δ/T), wobei T die aktuelle Temperatur ist. Das bedeutet, ein stark verschlechternder Zug wird selten akzeptiert, aber kleine verschlechternde Züge sind früh, wenn T hoch ist, noch recht wahrscheinlich. Während T gegen null zerfällt, kollabiert e^(−Δ/T) für jedes positive Δ gegen null, sodass der Algorithmus effektiv zu reinem gierigem Abstieg wird — Bergaufsteigen ist nicht mehr erlaubt, und nur verbessernde Züge überleben.

Diese Simulation nutzt geometrische Abkühlung: T wird nach jedem vorgeschlagenen Zug mit einer Abkühlungsrate α (nahe, aber unter 1) multipliziert, sodass T mit der Iterationszahl exponentiell zerfällt. Eine Abkühlungsrate sehr nahe 1 (z. B. 0,9995) kühlt langsam und gibt der Suche viele Iterationen bei höheren Temperaturen, um breit zu erkunden, bevor sie sich auf die Verfeinerung einer Lösung festlegt — das findet typischerweise kürzere Touren, braucht aber länger, um sich einzupendeln. Eine niedrigere Abkühlungsrate (z. B. 0,985) kühlt schnell und verhält sich fast wie gierige 2-opt-Lokalsuche, konvergiert schnell, bleibt aber eher in einem mittelmäßigen lokalen Minimum stecken.

Das ist der ganze Sinn des Ausglühens: Bei hoher Temperatur akzeptiert das Metropolis-Kriterium absichtlich einige längenerhöhende Züge. Eine Tour kann lokal optimal aussehen (kein einzelner 2-opt-Zug verbessert sie), während sie dennoch weit von der kürzestmöglichen Tour entfernt ist — das ist ein lokales Minimum. Indem gelegentlich ein schlechterer Zug akzeptiert wird, kann die Suche aus dem Becken dieses lokalen Minimums herausklettern und später in ein anderes, kürzeres fallen. Beim Betrachten des Distanzdiagramms sehen Sie typischerweise zunächst einen schnellen Abfall, gelegentliche Ausschläge nach oben, während T noch hoch ist, und dann eine glatte, monotone Abnahme, während sich T null nähert.

Echte Logistikunternehmen lösen Fahrzeugrouting-Probleme (VRPs) mit Hunderten oder Tausenden von Stopps, mehreren Fahrzeugen, Zeitfenstern und Kapazitätsgrenzen — ein NP-schweres kombinatorisches Problem, bei dem exakte Lösungen jenseits weniger Dutzend Stopps rechnerisch unpraktikabel sind. Metaheuristiken wie simuliertes Ausglühen, zusammen mit genetischen Algorithmen, Ameisenkolonie-Optimierung und Tabu-Suche, sind branchenübliche Werkzeuge, um sehr gute (wenn auch nicht nachweislich optimale) Routen in Sekunden bis Minuten zu finden. Diese Simulation modelliert den Einzelfahrzeug-Kern dieses Problems — das klassische Problem des Handlungsreisenden —, welches dieselbe kombinatorische Maschine im Herzen produktiver Routingsoftware ist.