Analiza porównawcza operatorów krzyżowania w algorytmach genetycznych dla optymalizacji tras: studia przypadku z Ałmaty i Szymkentu, Kazachstan

Dlaczego inteligentniejsze trasy autobusowe mają znaczenie

Każdy, kto długo czekał na przystanku lub musiał przebijać się przez liczne przesiadki, wie, że dotarcie z jednego końca miasta na drugi to nie tylko kwestia odległości. Dwa miejsca mogą wydawać się bliskie na mapie, a w praktyce być trudno dostępne, jeśli linie autobusowe ich nie łączą. Artykuł bada, jak klasa metod poszukiwawczych inspirowanych ewolucją — algorytmy genetyczne — może być dostrojona do projektowania lepszych tras autobusowych uwzględniających rzeczywiste sieci komunikacyjne w miastach takich jak Astana i Szymkent w Kazachstanie. Praca koncentruje się na jednym kluczowym elemencie tych algorytmów, zwanym krokiem krzyżowania, i pokazuje, jak jego przemyślany wybór może decydować o tym, czy powstaną nieporadne, okrężne przejazdy, czy szybkie, realistyczne trasy.

Od nieuporządkowanych map miasta do inteligentnego poszukiwania

Tradycyjne narzędzia planowania tras często traktują miasta tak, jakby podróżni mogli poruszać się swobodnie między dowolnymi dwoma punktami, licząc tylko odległość fizyczną. Rzeczywiste systemy autobusowe nie działają w ten sposób: można jechać tylko tam, gdzie rzeczywiście kursują linie, a każdy brak połączenia czy wymuszona objazd powoduje stratę czasu i pieniędzy. Autorzy modelują tę rzeczywistość, reprezentując ważne lokalizacje jako punkty, drogi i połączenia autobusowe jako krawędzie, a pełną podróż jako ścieżkę odwiedzającą każdy punkt dokładnie raz. Następnie stawiają dwuczęściowy cel: po pierwsze unikać „nielegalnych” kroków, gdzie nie ma bezpośredniego autobusu; po drugie, spośród legalnych tras wybierać tę o jak najmniejszej całkowitej odległości. To tworzy trudne zadanie z wieloma możliwymi ścieżkami, gdzie sprawdzenie wszystkich opcji szybko staje się niemożliwe wraz ze wzrostem skali miasta.

Jak ewolucja pomaga znaleźć lepsze trasy

Algorytmy genetyczne atakują takie zagadnienia, naśladując dobór naturalny. Zamiast testować pojedynczą trasę po kolei, utrzymują populację kandydackich rozwiązań. W każdym pokoleniu faworyzowane są lepsze trasy, a nowe powstają przez mieszanie i niewielkie modyfikacje istniejących. Kluczowy krok mieszania — krzyżowanie — decyduje, jak fragmenty dwóch tras-rodziców łączone są w nową trasę-dziecko. Dla planowania autobusowego ten etap jest krytyczny: jeśli zostanie przeprowadzony dobrze, przekaże użyteczne wzorce połączeń przystanków; jeśli źle, może zniszczyć połączenia i wygenerować trasy ignorujące istniejącą sieć. Autorzy testują dziewięć różnych stylów krzyżowania, które różnią się tym, jak zachowują kolejność przystanków, ich dokładne pozycje lub rzeczywiste krawędzie między przystankami.

Testowanie wielu sposobów łączenia tras

Aby sprawdzić, które style krzyżowania działają najlepiej, zespół przeprowadza szeroki zestaw eksperymentów na rzeczywistych danych komunikacyjnych z Konya (miasto referencyjne z wcześniejszych badań) oraz z Ałmaty i Szymkentu. Dla każdego miasta wybierają 14 ważnych punktów docelowych, łączą je z pobliskimi przystankami i budują trzy kluczowe tabele danych: odległości między lokalizacjami, pary posiadające bezpośredni kurs autobusowy oraz kary za próby podróży tam, gdzie autobus nie kursuje. Następnie badają setki konfiguracji, zmieniając rozmiar populacji, częstotliwość stosowania krzyżowania oraz jak często stosowane są drobne losowe zmiany (mutacje). Dla każdej konfiguracji powtarzają algorytm wielokrotnie, by uwzględnić losowość, i mierzą nie tylko długość uzyskanych tras, ale też jak często metoda znajduje w ogóle jakąś legalną trasę oraz jak szybko do tego dochodzi.

Zwycięska strategia dla realistycznych podróży

We wszystkich trzech miastach wyróżnia się jeden styl krzyżowania: rekombinacja krawędzi (edge recombination). W przeciwieństwie do metod skupiających się głównie na kolejności przystanków, rekombinacja krawędzi zwraca uwagę na to, które przystanki są bezpośrednio połączone i stara się zachować te połączenia podczas tworzenia nowych tras. Badanie pokazuje, że to podejście skoncentrowane na krawędziach znacznie częściej generuje wykonalne trasy autobusowe, częściej odtwarza rzeczywiście najlepsze znane trasy i zwykle robi to w zaledwie kilku pokoleniach. Drugi styl, zwany krzyżowaniem opartym na kolejności, także radzi sobie dobrze i jest szybszy w obliczeniach, oferując dobry kompromis, gdy potrzebne są bardzo duże liczby uruchomień. Inne popularne operatory, które silniej przestawiają przystanki, mają zwykle trudności, wymagają więcej czasu i dostarczają mniej wysokiej jakości rozwiązań.

Co to oznacza dla codziennych podróży

Dla osoby niebędącej specjalistą sedno sprawy jest takie, że „przepis” stosowany wewnątrz algorytmu genetycznego może znacząco wpłynąć na to, jak dobrze zaprojektuje on rzeczywiste trasy autobusowe. Uprzywilejowując reguły krzyżowania, które zachowują realistyczne połączenia, a jednocześnie eksplorują nowe kombinacje, planujący mogą wygenerować trasy, które zarówno przestrzegają istniejącej sieci, jak i minimalizują całkowitą odległość podróży. W testach na niewielkich, ale realistycznych obrazach miasta najlepiej dostrojony algorytm genetyczny nie tylko dorównywał trasom znalezionym metodami matematycznymi dokładnego rozwiązania, lecz robił to szybko i powtarzalnie. Sugeruje to, że w miarę jak miasta stają się bardziej złożone i bogate w dane, starannie zaprojektowane poszukiwanie ewolucyjne może pomóc agencjom transportowym planować trasy, które wydają się bardziej bezpośrednie, wymagają mniej niewygodnych przesiadek i lepiej wykorzystują pojazdy oraz paliwo.

Cytowanie: 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

Słowa kluczowe: trasowanie transportu publicznego, algorytmy genetyczne, mobilność miejska, optymalizacja tras, planowanie inteligentnego miasta