Yes, it will take a long time to determine the optimal solution, not necessarily a feasible solution.
If you are willing to accept a solution that is no more than twice the optimum, an easy and efficient approximation scheme exists in this case. Airports would form a metric graph (distance...