Eine vergleichende Analyse von Crossover-Operatoren in genetischen Algorithmen zur Routenoptimierung: Fallstudien aus Astana und Schymkent, Kasachstan

Warum bessere Buslinien wichtig sind

Wer schon einmal lange an einer Bushaltestelle gewartet oder mehrere Umstiege organisiert hat, weiß: Städte überwinden ist nicht nur eine Frage der Distanz. Zwei Orte können auf der Karte nahe beieinanderliegen und dennoch schwer zu erreichen sein, wenn die passenden Buslinien nicht verbinden. Diese Arbeit untersucht, wie sich eine Klasse von suchbasierten Verfahren, die von der Evolution inspiriert sind – genetische Algorithmen – so anpassen lässt, dass sie bessere Buslinien entwerfen, die reale Verkehrsnetze in Städten wie Astana und Schymkent in Kasachstan berücksichtigen. Im Mittelpunkt steht ein zentrales Element dieser Algorithmen, der Crossover-Schritt, und es wird gezeigt, wie dessen kluge Wahl den Unterschied zwischen umständlichen, weiten Fahrten und schnellen, realistischen Routen ausmachen kann.

Von unübersichtlichen Stadtplänen zu smarter Suche

Traditionelle Routenplaner behandeln Städte oft so, als könnten Reisende sich frei zwischen beliebigen Punkten bewegen und nur die physische Entfernung zähle. Reale Bussysteme funktionieren nicht so: Man kann nur dorthin gelangen, wo Linien tatsächlich verkehren, und jede fehlende Verbindung oder erzwungene Umweg kostet Zeit und Geld. Die Autoren modellieren diese Realität, indem sie wichtige Stadtorte als Punkte darstellen, Straßen- und Busverbindungen als Kanten und eine vollständige Reise als einen Pfad, der jeden Punkt genau einmal besucht. Sie setzen sich ein zweistufiges Ziel: Erstens sollen „illegale“ Schritte, bei denen es keine Direktverbindung gibt, vermieden werden; zweitens soll unter den legalen Routen diejenige mit der geringsten Gesamtdistanz gewählt werden. Das ergibt ein schwieriges Puzzle mit vielen möglichen Pfaden, bei dem das Durchprobieren aller Möglichkeiten schnell unmöglich wird, sobald die Stadt wächst.

Wie die Evolution hilft, bessere Routen zu finden

Genetische Algorithmen greifen solche Probleme an, indem sie die natürliche Selektion nachbilden. Anstatt eine Route nach der anderen zu testen, halten sie eine ganze Population von Kandidatenrouten vor. In jeder Generation werden bessere Routen bevorzugt, und neue entstehen, indem vorhandene gemischt und leicht verändert werden. Der entscheidende Mischschritt – Crossover – legt fest, wie Teile zweier Elternrouten zu einer neuen Kindroute kombiniert werden. Für die Busplanung ist dieser Schritt kritisch: Gut ausgeführt gibt er nützliche Muster verbundener Haltestellen weiter; schlecht ausgeführt kann er Verbindungen zerstören und Routen erzeugen, die das Bussystem ignorieren. Die Autoren testen neun verschiedene Crossover-Varianten, die sich darin unterscheiden, wie sie die Reihenfolge der Haltestellen, die genauen Positionen oder die tatsächlichen Verbindungen zwischen Haltestellen bewahren.

Viele Wege des Mischens im Test

Um zu sehen, welche Crossover-Stile am besten funktionieren, führt das Team eine große Reihe von Experimenten mit realen Fahrplandaten aus Konya (einer Referenzstadt aus früheren Arbeiten) sowie aus Astana und Schymkent durch. Für jede Stadt wählen sie 14 wichtige Ziele aus, verbinden diese mit nahegelegenen Haltestellen und erstellen drei zentrale Datentabellen: Distanzen zwischen Orten, welche Paare eine Direktbusverbindung haben, und Strafen für Versuche, dort zu reisen, wo kein Bus fährt. Dann werden Hunderte von Einstellungen untersucht: Bevölkerungsgröße, wie häufig Crossover eingesetzt wird und wie oft kleine zufällige Änderungen (Mutationen) auftreten. Jede Einstellung wird mehrfach wiederholt, um Zufallseinflüsse auszugleichen; gemessen wird nicht nur die Kürze der finalen Routen, sondern auch wie oft überhaupt eine legale Route gefunden wird und wie schnell dieser Punkt erreicht wird.

Die erfolgreiche Strategie für realistische Fahrten

In allen drei Städten sticht ein Crossover-Stil besonders hervor: die Kantenrekombination (edge recombination). Anders als Methoden, die hauptsächlich die Reihenfolge der Haltestellen beachten, beachtet die Kantenrekombination, welche Haltestellen direkt verbunden sind, und bemüht sich, diese Verbindungen beim Erzeugen neuer Routen zu erhalten. Die Studie zeigt, dass dieser kantenfokussierte Ansatz deutlich wahrscheinlicher gangbare Busfahrten erzeugt, öfter die wirklich besten bekannten Routen wiederfindet und dies meist in nur wenigen Generationen schafft. Ein zweiter Stil, das order-basierte Crossover, schneidet ebenfalls gut ab und ist schneller zu berechnen, was ein guter Kompromiss ist, wenn sehr viele Durchläufe nötig sind. Andere häufig eingesetzte Crossover, die Haltestellen aggressiver umordnen, haben tendenziell Schwierigkeiten, benötigen mehr Zeit und liefern seltener hochwertige Routen.

Was das für den Alltag bedeutet

Für Nichtfachleute lautet die Quintessenz: Die „Rezeptur“, die in einem genetischen Algorithmus verwendet wird, kann großen Einfluss darauf haben, wie gut er reale Busverbindungen entwirft. Indem man Crossover-Regeln bevorzugt, die realistische Verbindungen intakt halten und gleichzeitig neue Kombinationen erkunden, können Planer Routen erzeugen, die sowohl das vorhandene Busnetz achten als auch die Gesamtreisedistanz gering halten. In Tests an kleinen, aber realistischen Stadtausschnitten erreichte der bestoptimierte genetische Algorithmus nicht nur Routen, die mit exakten mathematischen Methoden übereinstimmen, sondern tat dies schnell und zuverlässig. Das deutet darauf hin, dass mit zunehmender Komplexität und Datenverfügbarkeit in Städten sorgfältig gestaltete evolutionäre Suche Verkehrsbehörden dabei unterstützen kann, Routen zu planen, die direkter wirken, weniger umständliche Umstiege benötigen und Fahrzeuge sowie Treibstoff effizienter nutzen.

Zitation: Kazbek, R., Sergaziyev, M., Kenzhe, D. et al. A comparative analysis of crossovers in genetic algorithms for route optimization: case studies from Astana and Shymkent, Kazakhstan. Sci Rep 16, 13816 (2026). https://doi.org/10.1038/s41598-026-43898-7

Schlüsselwörter: Routenplanung im öffentlichen Verkehr, genetische Algorithmen, städtische Mobilität, Routenoptimierung, Smart-City-Planung