Comparison of Evolutionary and Traditional Algorithms for Flight Route Optimization
This study investigates flight route optimization in a large airline network by comparing traditional path-finding algorithms with an evolutionary approach under realistic constraints. Using a real-world dataset of 6,817 routes, Dijkstra’s algorithm, the A ${}^{\ast }$ search algorithm with precomputed heuristics, and a Genetic Algorithm (GA) were implemented. All methods were evaluated on identical origin–destination pairs while enforcing an exact number of layovers, and on scenarios where direct flights were removed or newly introduced. The results show that, although Dijkstra’s algorithm always returns the optimal shortest-time route when one exists, its computation time increases rapidly as the number of required layovers increases. A ${}^{\ast }$ improved the efficiency in dense subgraphs but sometimes failed under strict layover constraints owing to heuristic misalignment. In contrast, GA consistently produced near-optimal routes with stable runtimes across varying connectivity levels and constraint settings. Route removal experiments highlighted the vulnerability of sparsely connected regions, whereas adding direct flights mainly benefited airport pairs previously linked only by long multi-stop paths. These findings indicate that evolutionary algorithms are well-suited for large-scale, dynamically changing airline networks, whereas classical algorithms remain preferable for smaller, well-structured subproblems.