It is kind of funny though, because as usual, the answer is just "add more compute" - it seems these days that everything is compute constrained. So what if the thing you have to implement can only be reduced to O(n!) or whatever, just throw compute at it! Out of compute? Apply pruning heuristic then throw more compute at it! Still out of compute? Well... buy more compute!
I do think it would actually be fantastic to build a "route builder" tool that could sequence with some reasonable level of accuracy. You could honestly probably get like 90% of the way there by having airplanes go direct to some nearby fixes to slot one in front of the other, etc. A* over some graph of fixes where you they all have to get to the terminal node (which is the arrival gate) in some optimal time? You could probably get pretty damn close to an optimal solution with some constraint programming stuff.
I've been working on a tool for a customer right now that finds the "cheapest" altitude for a given flight by pulling the winds, but also factoring in the cost per hour of the airplane dry, then the fuel burns. Think "cost index for dummies." I have totally BS performance data in there, I'd need to do a lot of data entry to make it work nicely, but:
View attachment 89667
Like, imagine you could shave off a bit of cost on every single leg, and not just "oh, I went to foreflight and picked the best tailwind" but likely actually found the best cost altitude given fuel burn, time to climb, etc. That's another knapsack problem, but honestly, on anything that's not a really long flight, this would be useful to figure out. My main customer did thousands of individual legs last year. Imagine if they could shave off $20/leg on average? Now we're talking being able to hire hire another ramper, or buy a new prop, etc.
The knapsack problem and google's OR tools goes a long way towards saving money, and in an oil constrained world, you're going to want to know how much each flight costs.
Likewise for ATC, you're constrained by space and time. If can give an airplane Direct to a fix that's near by the arrival gate then direct from 1000NM away so that you don't have to sequence manually, that's insanely valuable.