I would expect an airline routing problem to be an integer program (because you can't send 2/3 of an aeroplane along one route and 1/3 along another), and integer programming is NP-hard. On the bright side, at all times you have an estimate of the best possible solution so you can terminate early when you're within some percentage (say 1%) of optimal.
Interestingly they still use the simplex method repeatedly during the branch-and-bound solving process, because it only requires a little work to adjust at each step, whereas the methods with guaranteed polynomial worst case tend to take that polynomial time regardless of how "close" they start to the optimum. So, as you say, convential complexity analysis suggests that simplex would be an awful lot less useful than it is.
Interestingly they still use the simplex method repeatedly during the branch-and-bound solving process, because it only requires a little work to adjust at each step, whereas the methods with guaranteed polynomial worst case tend to take that polynomial time regardless of how "close" they start to the optimum. So, as you say, convential complexity analysis suggests that simplex would be an awful lot less useful than it is.