Сравнительный анализ операторов скрещивания в генетических алгоритмах для оптимизации маршрутов: примеры из Астаны и Шымкента, Казахстан

Почему важны продуманные автобусные маршруты

Тот, кто когда-либо слишком долго ждал на автобусной остановке или перебирал несколько пересадок, знает: добраться через город — это не только вопрос расстояния. На карте два места могут выглядеть близко, но быть неудобными для доступа, если их не соединяют подходящие линии. В этой статье рассматривается, как класс поисковых методов, вдохновлённых эволюцией — генетические алгоритмы — можно настроить для проектирования более удачных автобусных маршрутов, учитывающих реальную структуру сети в таких городах, как Астана и Шымкент в Казахстане. Работа сосредоточена на одном ключевом элементе этих алгоритмов — шаге скрещивания — и показывает, как правильный выбор этого шага может означать разницу между громоздкими, объездными поездками и быстрыми, реалистичными маршрутами.

От запутанных городских карт к умному поиску

Традиционные планировщики маршрутов часто трактуют город так, как будто путешественники могут свободно перемещаться между любыми двумя точками, заботясь лишь о физическом расстоянии. Реальные автобусные системы устроены иначе: можно ехать только там, где действительно пролегают линии, и любая недостающая связь или вынужденный объезд стоят времени и денег. Авторы моделируют эту реальность, представляя важные городские точки как узлы, дорожные и автобусные связи — как ребра, а полный маршрут — как путь, который посещает каждую точку ровно один раз. Они ставят двухчастную цель: сначала избегать «нелегальных» ходов, где прямого автобуса нет; затем среди легальных маршрутов выбирать тот, у которого суммарное расстояние минимально. Это создаёт сложную задачу с множеством возможных путей, при которой перебор всех вариантов быстро становится невозможным по мере роста города.

Как эволюция помогает находить лучшие маршруты

Генетические алгоритмы решают такие задачи, подражая естественному отбору. Вместо того чтобы проверять по одному маршруту, они держат целую популяцию кандидатных маршрутов. В каждом поколении предпочтение получают лучшие маршруты, и новые создаются путём смешивания и небольших изменений существующих. Ключевой шаг смешивания — скрещивание — определяет, как фрагменты двух родительских маршрутов комбинируются в новый маршрут-потомок. Для планирования автобусов этот шаг критичен: при удачном выполнении он передаёт полезные паттерны связанных остановок; при неудачном — ломает связи и даёт маршруты, игнорирующие реальную сеть. Авторы тестируют девять различных стратегий скрещивания, отличающихся тем, насколько они сохраняют порядок остановок, их точные позиции или фактические связи между ними.

Тестирование множества способов смешивания маршрутов

Чтобы выяснить, какие стили скрещивания работают лучше, команда проводит обширную серию экспериментов на реальных данных по перевозкам из Коньи (опорный город из предыдущих работ) и из Астаны и Шымкента. Для каждого города они выбирают 14 важных направлений, связывают их с ближайшими остановками и формируют три ключевые таблицы данных: расстояния между локациями, какие пары соединены прямым автобусом и штрафы за попытки проехать там, где автобуса нет. Затем они исследуют сотни настроек, варьируя размер популяции, частоту применения скрещивания и частоту небольших случайных изменений (мутаций). Для каждой настройки алгоритм запускается многократно, чтобы учесть случайность, и измеряют не только длину финальных маршрутов, но и то, как часто метод находит хоть какой‑то легальный маршрут и как быстро он этого достигает.

Победная стратегия для реалистичных поездок

Во всех трёх городах выделяется одна стратегия скрещивания: рекомбинация рёбер (edge recombination). В отличие от методов, которые в первую очередь ориентируются на порядок остановок, рекомбинация рёбер обращает внимание на то, какие остановки связаны напрямую, и старается сохранить эти связи при построении новых маршрутов. Исследование показывает, что этот подход, ориентированный на рёбра, значительно чаще порождает выполнимые автобусные поездки, чаще заново обнаруживает действительно лучшие известные маршруты и обычно делает это за несколько поколений. Второй стиль, называемый order‑based crossover, тоже показывает хорошие результаты и требует меньше вычислений, что делает его подходящим компромиссом при необходимости очень большого числа запусков. Другие распространённые операторы скрещивания, которые более агрессивно переставляют остановки, как правило, испытывают трудности, требуют больше времени и дают меньше качественных маршрутов.

Что это значит для повседневных поездок

Для неспециалиста вывод прост: «рецепт», используемый внутри генетического алгоритма, может существенно повлиять на то, насколько удачно он проектирует реальные автобусные маршруты. Отдавая приоритет правилам скрещивания, которые сохраняют реалистичные связи, но при этом позволяют исследовать новые комбинации, планировщики могут генерировать маршруты, которые одновременно соответствуют существующей сети и минимизируют общее расстояние поездки. В испытаниях на небольших, но реалистичных городских фрагментах лучше настроенный генетический алгоритм не только сопоставлялся с маршрутами, найденными точными математическими методами, но и делал это быстро и надёжно. Это указывает на то, что по мере усложнения городов и накопления данных тщательно продуманный эволюционный поиск может помочь транспортным агентствам планировать маршруты, которые кажутся более прямыми, требуют меньше неудобных пересадок и эффективнее используют подвижной состав и топливо.

Цитирование: 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

Ключевые слова: маршрутизация общественного транспорта, генетические алгоритмы, городская мобильность, оптимизация маршрутов, планирование умного города