A heuristic algorithm for aircraft conflict resolution based on closed-form analytical solutions of relaxed pairwise problems

Given a set of aircraft, the objective of the aircraft conflict resolution problem is to determine least-deviating conflict-free trajectories. Efficient algorithms for conflict resolution problems are fundamental for automation in air traffic control. We develop a fast heuristic based on the closed-form analytical solutions of convex, bound-relaxed, two-aircraft problems. We leverage this knowledge to constructs feasible and efficient solutions to multi-aircraft problems. Computational benchmarking reveals that the proposed approach is able to find near-optimal solutions in competitive time.