Air Traffic Control Area Configuration Advisories from Near-Optimal Distinct Paths

Area of Specialization supervisors dynamically configure available air traffic control resources so that air traffic can operate safely and efficiently. We propose to as-sist supervisors with this process by presenting them with a set of near-optimal and meaningfully-different configuration advisories. To find such a set of advisories, we define a problem that is equivalent to finding an optimal and other near-optimal and distinct paths in a time-expanded graph. We show that this problem is NP-hard and then motivate and specify four algorithms. One is a benchmark that solves the prob-lem to optimality, one is a novel heuristic based on value iteration, and the third is a novel heuristic based on the A ∗ algorithm. The fourth algorithm solves to opti-mality the lowest-cost paths problem relaxation of our problem. When used to solve realistic problem instances, the lowest-cost paths algorithm rarely returned feasible so-lutions and the optimal algorithm required excessive computation times, but the two novel heuristics found feasible and often optimal solutions in just a few seconds. The A∗-based heuristic achieved lower computation times while the value iteration-based heuristic typically found more advisories and lower-cost advisories