A Grid-Based Optimization Method for Airspace Conflict Detection and Resolution During the Execution Phase

Growing air traffic and dynamic missions require conflict detection and resolution (CD&R) during the execution phase, when ad hoc airspace must be inserted into an already conflict-free baseline plan without global re-optimization. This paper proposes a grid-based online optimization framework built on Geographical Coordinate Subdivision grid with One dimension integer coding on 2n-tree (GeoSOT) discretization that transforms four-dimensional spatiotemporal conflict judgment into efficient grid-code matching and interval comparison. Incremental conflict detection restricts pairwise checks to candidate ad hoc-related pairs, reducing detection scale by over 99% relative to full screening. A lexicographic two-stage resolution policy prioritizes ad hoc adjustments—incorporating horizontal, altitude, temporal, and grid-shrinkage operations—and activates limited baseline coordination only when necessary. The The Incremental Ad-hoc Operation—Tiered Priority Time-Sliced Search (IAO-TPTS) algorithm implements this policy under a hard time budget through Phase A (ad-hoc-restricted Dimension-wise Conflict-Driven Assignment, DCDA-Lite) for fast ad hoc-only feasibilization and Phase B (Hybrid Adaptive Large Neighborhood Search, Hybrid-ALNS) for tiered refinement, with dual validation to prevent secondary conflicts in neighboring airspace. Experiments including visualization, ablation, algorithm comparison, and scalability analysis on Small, Medium, and Large scenarios show 100% feasibility within 180 s, median solve times as low as 0.069 s, competitive objective values versus mixed-integer linear programming (MILP) and Adaptive Large Neighborhood Search (ALNS), and sub-linear scalability from 20 to 300 baseline airspaces. The novelty is this integrated execution-phase framework (incremental detection, lexicographic baseline-protective scheduling, and time-budgeted IAO-TPTS with dual validation), rather than a new grid-coding scheme or a standalone MILP.