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

Editor’s note: This story covers findings from an unedited manuscript released for early access. The paper will undergo additional editing before final publication. Conclusions or details may change, and all legal disclaimers apply.

Designing bus routes that balance speed, cost, fuel use, and vehicle wear is a classic optimization puzzle—one that cities tackle daily under tight constraints. A new study takes a closer look at how genetic algorithms (GAs) handle this challenge, zeroing in on the role of crossover operators, a key mechanism that blends candidate solutions to evolve better routes over time. The researchers focus on a Path-TSP (Traveling Salesman Problem) framing tailored to real transit networks and validate their approach using datasets from Astana and Shymkent, Kazakhstan.

Why this matters

Transit agencies rarely optimize for a single goal. In practice, they juggle on-time performance, operating costs, resource constraints, and rider experience. Traditional optimization can struggle with this complexity, especially when real-world feasibility—like respecting fixed stops and service patterns—must be preserved. Genetic algorithms offer a flexible way to search large solution spaces efficiently. But the quality and speed of that search often depend on the crossover operator, which determines how traits from two “parent” routes combine into a new “child” route.

The research at a glance

This work presents a comparative analysis of a GA using different crossover operators, applied to bus routing problems cast as Path-TSP instances derived from existing networks. Instead of theoretical or synthetic graphs, the study uses real-world data from Astana and Shymkent, two major Kazakhstani cities with practical routing constraints. The goal is not just to find short paths, but to generate solutions that are feasible for transit operations and discovered efficiently within limited compute budgets.

What the team did

• Formulated route optimization as a Path-TSP problem grounded in current bus networks, ensuring solutions reflect actual stops and connections.
• Implemented a genetic algorithm and systematically varied the crossover operator to see how it affects performance.
• Evaluated outcomes using real datasets from Astana and Shymkent, focusing on runtime, rate of feasible solutions, and how often optimal routes are recovered.
• Benchmarked findings against results previously reported in the literature to gauge external validity.

Why crossover operators matter

In a GA, crossover is the step where two candidate solutions are combined to form a new one, ideally mixing strong features from both. For routing problems like Path-TSP, the challenge is to preserve valid sequences of stops while improving total cost or travel time. Some crossover schemes are better at maintaining feasibility; others explore the space more aggressively but risk producing invalid or inferior routes. By directly comparing crossover methods under the same conditions, the study clarifies which strategies best balance feasibility, exploration, and speed for urban bus routing.

Key findings

• Runtime efficiency: The framework delivers competitive run times, making it practical for planners working with limited compute resources.
• Feasibility rates: Across crossover variants, the algorithm consistently produces a strong number of valid routes aligned with real network constraints.
• Optimal route recovery: The GA frequently rediscovers optimal or near-optimal routes, reinforcing its reliability for operational use.
• External consistency: Results are in good agreement with prior studies, suggesting that the approach generalizes beyond the specific datasets examined.

Case study context: Astana and Shymkent

Astana and Shymkent present diverse urban topologies and transit demands, offering a robust test bed for the method. By grounding the analysis in real data from both cities, the authors demonstrate that their GA-based approach is not limited to a single network structure or scale. The model’s performance across these contrasting settings highlights its adaptability and practical relevance for different urban environments.

What sets this framework apart

• Practicality: Tailored for users with limited time and resources, the method prioritizes computational efficiency and solution feasibility—key for real-world planning cycles.
• Versatility: By examining multiple crossover operators, the study offers guidance on algorithm design choices that can improve outcomes without overhauling entire systems.
• Grounded evaluation: Validation on real datasets provides confidence that the gains are not artifacts of synthetic benchmarks.

Implications for cities and operators

For transit agencies, the findings suggest that careful selection of GA crossover operators can accelerate planning workflows, yield more feasible route options, and improve the odds of reaching optimal solutions—without requiring vast compute budgets. This could aid scenario testing, network redesigns, or incremental improvements, especially in rapidly growing cities where service patterns evolve frequently.

Limitations and next steps

As an early, unedited release, the manuscript may contain errors or areas requiring clarification. Future work could extend evaluation to dynamic conditions (e.g., time-of-day congestion), integrate multi-objective optimization more explicitly, or test transferability across additional cities. Still, the current results provide a strong baseline and a practical playbook for teams considering GA-based routing.

Bottom line

This study sharpens our understanding of how genetic algorithm crossover choices shape performance in real urban bus routing. By demonstrating strong runtime behavior, high feasibility, and frequent recovery of optimal routes on datasets from Astana and Shymkent—and aligning with published benchmarks—it offers clear, actionable insights for transit planners and operations researchers alike.

Disclaimer: The manuscript summarized here is unedited and subject to change before final publication. All legal disclaimers apply.