A comparative analysis of crossovers in genetic algorithms for route optimization: case studies from Astana and Shymkent, Kazakhstan

Why smarter bus routes matter

Anyone who has waited too long at a bus stop or juggled multiple transfers knows that getting across a city is not just about distance. Two places may look close on a map, yet be awkward to reach if the right bus lines do not connect them. This paper explores how a class of search methods inspired by evolution—genetic algorithms—can be tuned to design better bus routes that respect real transit networks in cities such as Astana and Shymkent in Kazakhstan. The work focuses on one crucial ingredient of these algorithms, called the crossover step, and shows how choosing it wisely can mean the difference between clumsy, roundabout trips and fast, realistic routes.

From messy city maps to smart search

Traditional route planners often treat cities as if travelers could move freely between any two points, caring only about physical distance. Real bus systems do not work that way: you can only go where lines actually run, and every missing link or forced detour costs time and money. The authors model this reality by representing important city locations as points, the road and bus links as connections, and a complete trip as a path that visits each point exactly once. They then set a two-part goal: first, avoid "illegal" steps where no direct bus exists; second, among the legal routes, pick the one with the shortest total distance. This creates a tough puzzle with many possible paths, where checking every option quickly becomes impossible as the city grows.

How evolution helps find better routes

Genetic algorithms attack such puzzles by mimicking natural selection. Instead of trying one route at a time, they keep a whole population of candidate routes. In each generation, better routes are favored, and new ones are created by mixing and slightly changing existing ones. The key mixing step—crossover—decides how pieces of two parent routes are combined into a new child route. For bus planning, this step is critical: done well, it passes along useful patterns of connected stops; done poorly, it can break links and produce routes that ignore the bus network. The authors test nine different crossover styles that vary in how they preserve the order of stops, the exact positions of stops, or the actual links between stops.

Testing many ways to mix routes

To see which crossover styles work best, the team runs a large battery of experiments on real transit data from Konya (a reference city from earlier work) and from Astana and Shymkent. For each city, they select 14 important destinations, link them to nearby stops, and build three key data tables: distances between locations, which pairs have a direct bus, and penalties for trying to travel where no bus runs. They then explore hundreds of settings, varying population size, how often crossover is used, and how frequently small random changes (mutations) are applied. For each setting, they repeat the algorithm many times to account for luck, and measure not just how short the final routes are, but how often the method finds any legal route at all and how quickly it reaches that point.

The winning strategy for realistic trips

Across all three cities, one crossover style stands out: edge recombination. Unlike methods that mainly care about the order of stops, edge recombination pays attention to which stops are directly linked and tries hard to preserve these links when building new routes. The study shows that this edge-focused approach is far more likely to produce feasible bus trips, more often rediscovers the truly best-known routes, and usually does so in only a few generations. A second style, called order-based crossover, also performs well and is faster to compute, offering a good balance when very large numbers of runs are needed. Other common crossovers that rearrange stops more aggressively tend to struggle, needing more time and delivering fewer high-quality routes.

What this means for daily travel

For a non-specialist, the upshot is that the “recipe” used inside a genetic algorithm can have a big impact on how well it designs real-world bus trips. By favoring crossover rules that keep realistic links intact while still exploring new combinations, planners can generate routes that both obey the existing bus network and keep total travel distance low. In tests on small but realistic city snapshots, the best-tuned genetic algorithm not only matched routes found by exact mathematical methods but did so quickly and reliably. This suggests that, as cities become more complex and data-rich, carefully designed evolutionary search can help transit agencies plan routes that feel more direct, require fewer awkward transfers, and make better use of vehicles and fuel.

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

Keywords: public transport routing, genetic algorithms, urban mobility, route optimization, smart city planning