Hybrid-Optimierungsalgorithmus zur Lösung von Wegplanungsproblemen basierend auf dem Grey-Wolf-Optimierungsalgorithmus

Intelligentere Routen in überfüllten Städten

Tagtäglich stehen Autofahrer, Lieferwagen und Roboter vor derselben Herausforderung: Wie gelangt man schnell, sicher und ohne Zeit- oder Energieverschwendung von A nach B? Diese Arbeit stellt eine neue Rechenmethode vor, die kürzere, gleichmäßigere Routen durch komplexe Straßennetze mit Hindernissen und Stau plant. Indem sie Ideen aus dem Jagdverhalten von Grauwölfen in Rudeln und aus der Suchstrategie von Goldsuchern verbindet, zeigen die Autorinnen und Autoren, wie Fahrzeuge und Roboter effizienter durch belebte städtische Umgebungen gesteuert werden können.

Warum bessere Wege wichtig sind

Mit dem Wachstum der Städte und zunehmendem Verkehr können schon kleine Verbesserungen bei der Routenwahl große Einsparungen bei Zeit, Energie und Emissionen bringen. Traditionelle Pfadsuchmethoden funktionieren gut bei einfachen Karten, verlangsamen sich jedoch oder bleiben stecken, sobald die Umgebung mit vielen Abbiegungen und Hindernissen überfrachtet ist. Moderne „intelligente“ Suchverfahren versuchen, die Natur nachzuahmen – etwa Vogelschwärme oder Ameisenkolonien –, indem sie viele Optionen parallel erkunden und zu sinnvollen Lösungen konvergieren. Ein solches Verfahren, der Grey-Wolf-Optimierungsalgorithmus, ist wegen seiner Einfachheit und Flexibilität beliebt, hat aber drei Hauptschwächen: Er kann in zweitbesten Lösungen stecken bleiben, zu früh konvergieren und die Suchfläche nicht immer gründlich genug durchkämmen.

Wölfe, Chaos und Goldsucher kombinieren

Um diese Schwächen zu überwinden, entwerfen die Autorinnen und Autoren eine verbesserte Version namens CGGWO. Sie behält die Grundidee eines Rudels virtueller Grauwölfe bei, die nach der besten Route suchen, verändert jedoch, wie sich das Rudel verteilt und lernt. Statt die Wölfe zufällig zu platzieren, nutzt die Methode zunächst eine mathematische Technik, die chaotische Abbildung genannt wird, um sie gleichmäßiger über den Suchraum zu streuen. Das erhöht die Wahrscheinlichkeit, dass einige Wölfe vielversprechende Regionen der Karte entdecken. Als Nächstes übernimmt die Methode eine Regel aus einer anderen, von Goldwäschern inspirierten Technik: Das führende „Alpha“-Tier wird in Richtung besonders ergiebiger Bereiche des Suchraums gelenkt, ähnlich wie Bergleute allmählich in Regionen mit mehr Gold vorrücken. Dieser Schritt bringt kontrollierte Zufälligkeit und Vielfalt ein und hilft dem Rudel, schlechten lokalen Lösungen zu entkommen.

Kluge Kreuzaustausche und sanftes Erschüttern

CGGWO ergänzt zwei Arten von „Kreuz“-Bewegungen, die Informationen zwischen den Wölfen austauschen. Bei der horizontalen Bewegung tauschen zwei Kandidatenpfade Teile ihrer Routen, wodurch blinde Flecken verkleinert und die Suche vollständiger über die Karte verteilt wird. Bei der vertikalen Bewegung vermischen sich verschiedene Abschnitte innerhalb eines einzelnen Pfades, was stagnierende Teile der Lösung wiederbeleben und verhindern kann, dass das Rudel zu früh auf einer fehlerhaften Route verharrt. Schließlich sorgt eine leichte gaußsche Mutation – kleine, zufällige Stöße, gesteuert durch die Leistungsbewertung jedes Wolfes – für fortgesetzte Erkundung. Ist die Route eines Wolfes schlechter als der Durchschnitt, erhält er einen stärkeren Ruck, wodurch die gesamte Gruppe weniger anfällig dafür wird, in einer Ecke der Lösungslandschaft stecken zu bleiben.

Erprobung der neuen Methode

Die Forschenden prüfen CGGWO zuerst an 23 standardisierten mathematischen Testfunktionen, die häufig zur Beurteilung von Suchalgorithmen verwendet werden. Diese Aufgaben reichen von glatten Landschaften mit einem einzigen besten Tal bis zu rauen Terrains mit vielen lokalen Tälern. In den meisten Tests findet CGGWO bessere Lösungen, konvergiert schneller und zeigt stabileres Verhalten als mehrere bekannte Vergleichsverfahren, darunter der ursprüngliche Grey-Wolf-Algorithmus, Partikelschwarmoptimierung und genetische Algorithmen. Anschließend wenden sie die Methode auf ein realistisches Wegplanungsproblem an, das auf einem vereinfachten Straßenraster in der Nähe eines geschäftigen Handelsviertels in Lhasa basiert. Hindernisse repräsentieren gesperrte oder stark befahrene Abschnitte; Ziel ist es, Start- und Zielpunkt mit einer kurzen, gleichmäßigen Route zu verbinden, die diese Bereiche umgeht.

Kürzere, gleichmäßigere Fahrten

Im verkehrsähnlichen Test erzeugt CGGWO durchweg kürzere Wege mit weniger scharfen Kurven als die anderen Methoden, bei moderatem Rechenaufwand. Im Vergleich zum ursprünglichen Grey-Wolf-Algorithmus und mehreren Konkurrenzverfahren sind die geplanten Routen geradliniger und leichter zu befahren; in einigen Vergleichen reduziert sich die zurückgelegte Distanz um bis zu etwa ein Viertel. Für die interessierte Leserschaft ist die Botschaft klar: Durch die clevere Kombination von Ideen aus Chaos, Gruppenjagd und Goldsuche durchsucht die neue Methode Karten gründlicher und vermeidet das Festfahren bei lediglich zufriedenstellenden Lösungen. Das macht sie zu einem vielversprechenden Werkzeug für künftige Navigationssysteme, Lieferroboter und andere intelligente Maschinen, die schnell sichere und effiziente Wege durch die dichten, sich wandelnden Labyrinthe moderner Städte finden müssen.

Zitation: Cheng, G., Liu, Y. Hybrid optimization algorithm for solving path planning problems based on grey wolf optimization algorithm. Sci Rep 16, 8479 (2026). https://doi.org/10.1038/s41598-026-35037-z

Schlüsselwörter: Wegplanung, Optimierungsalgorithmus, intelligenter Verkehr, Schwarmintelligenz, Roboter-Navigation