Multitree Genetic Programming with Behavioral Semantics for Large-Scale Dynamic Air Traffic Flow Management

Dynamic Air Traffic Flow Management (DATFM) is vital to modern aviation industries, requiring real-time routing and sequencing aircraft within constrained airspace to ensure safety and efficiency, particularly during unforeseen disruptions. Multitree Genetic Programming (MTGP) provides an automatic design framework to simultaneously learn routing and sequencing policies. However, the coupling interdependence between the routing and sequencing decisions in MTGP tends to produce structurally valid but semantically ineffective offspring, thereby limiting MTGP’s search ability within the heuristic space. This paper presents a novel Multitree Genetic Programming with Behavioral Semantics (MrGPBS) approach that automatically evolves effective reactive scheduling heuristics for DATFM. First, we develop a specialized multitree representation incorporating informative terminals that enable concurrent evolution of routing and sequencing decisions, coupled with a problem-tailored heuristic template that decodes these representations into executable solutions in an online manner. Second, we propose a behavioral semantics-guided evolutionary mechanism that addresses the coupling interdependence issue of existing MTGP methods. Our method preserves well-evolved tree structures by promoting recombination between behaviorally compatible individuals, thereby enabling incremental improvement within the heuristic search space. We evaluate MrGPBS on comprehensive benchmark instances derived from real-world air traffic data, encompassing diverse problem scales and dynamic operating conditions. Experimental results demonstrate that our approach significantly outperforms state-of-the-art methods.