This is a travelling salesman problem. It's true that a conventional computer cannot truly solve this problem for large size inputs because it is NP-hard. Whether the inputs for an actual scheduled aviation company are large enough to make this important I somewhat doubt, but regardless:

We have good heuristics for this problem which are very close to the likely best solution. So instead of an amazing pay off for a true solution you get in fact only a slight improvement or worse in some cases merely confirmation that your existing heuristic answer was actually the best possible.

Quantum computers don’t have such a compelling case for optimization. Classical optimization algorithms are really good. Usually if you look hard enough you can find a sqrt(n) speed up but I don’t think these are the applications that will change the world

Classical computers might not find the optimal schedule but can likely solve for good enough scheduling for a fraction of the price. I’m curious if the difference would result in millions daily for a single air operator company

Right, but it's not possible now, is it?