3 ms·

Yes, theoretically it is NP, if you approach it naively. In practice it is easier to optimize for sub-problems In practice, crews have their home base, their c

Yes, theoretically it is NP, if you approach it naively. In practice it is easier to optimize for sub-problems In practice, crews have their home base, their corresponding qualifications (though for WN they probably only have one or two types) And you can bet you can start cancelling flights once you don't have enough crew. Problem is, your crew might have gone over their allowed time and them (and your plane) are in Smallville, OH and there are passengers in Chicago waiting to fly.

tgv 4y ago
Also: you can work with sub-optimal solutions. Decent approximations exist for many classes of certain problems. Even running simulated annealing or genetic algorithm will get you close to the optimum. I'm sure such a large airliner has a staff with sufficient knowledge of optimization.
- bodhiandphysics 4y ago
  I do simulated annealing for a living. Simulated annealing on graphs works great when a) the diameter of the graph is small (which for airlines corresponds to hubbie hub and spoke models) and b). when you can accept relatively approximate solutions. The issue it seems here is that southwest doesn't have enough pilots. Algorithmically, that means they can't accept approximate solutions!
  - raverbashing 4y ago
    > Algorithmically, that means they can't accept approximate solutions! Well, of course they can Not enough pilots make the general problem infeasible, so you have to make do what you have In practice this means a) flying the schedule as best as you can b) get people/crew/planes back to hubs c) prioritize based on displaced people/cost/other variables
    - bodhiandphysics 4y ago
      You have to be careful what you mean by approximate. In this context, it means a schedule that requires more than the optimal number of pilots. Another way of meaning approximate is canceling routes till you can find a schedule that fits the pilots you have. That’s actually a harder problem, and is not CS means by an approximation algorithm. Obviously that’s what SW has to do, but part of the reason why things are so disastrous is that this problem is quite difficult (in terms of algorithmic difficulty)
bodhiandphysics 4y ago
"Optimizing for subproblems" itself has issues. For instance with a single hub (a complete hub and spoke model), the problem is algorithmically easy. But a) flight distance is much higher, and b) you run the risk of a single weather disaster taking out your entire network, and c) lots of other problems. My point was to suggest that its useful to understand what's going on in terms of algorithmic complexity. Southwest, because of decisions that they made I should add, is facing an extremely difficult algorithmic problem, and some of the issues of what's going on can be understood by thinking out those problems. I.E. your algorithms class actually matters
akira2501 4y ago
Senior pilots expect to have more choice in their routes and schedules. Junior pilots expect to have no choice.

tgv 4y ago

Also: you can work with sub-optimal solutions. Decent approximations exist for many classes of certain problems. Even running simulated annealing or genetic algorithm will get you close to the optimum. I'm sure such a large airliner has a staff with sufficient knowledge of optimization.

bodhiandphysics 4y ago
I do simulated annealing for a living. Simulated annealing on graphs works great when a) the diameter of the graph is small (which for airlines corresponds to hubbie hub and spoke models) and b). when you can accept relatively approximate solutions. The issue it seems here is that southwest doesn't have enough pilots. Algorithmically, that means they can't accept approximate solutions!
- raverbashing 4y ago
  > Algorithmically, that means they can't accept approximate solutions! Well, of course they can Not enough pilots make the general problem infeasible, so you have to make do what you have In practice this means a) flying the schedule as best as you can b) get people/crew/planes back to hubs c) prioritize based on displaced people/cost/other variables
  - bodhiandphysics 4y ago
    You have to be careful what you mean by approximate. In this context, it means a schedule that requires more than the optimal number of pilots. Another way of meaning approximate is canceling routes till you can find a schedule that fits the pilots you have. That’s actually a harder problem, and is not CS means by an approximation algorithm. Obviously that’s what SW has to do, but part of the reason why things are so disastrous is that this problem is quite difficult (in terms of algorithmic difficulty)

bodhiandphysics 4y ago

"Optimizing for subproblems" itself has issues. For instance with a single hub (a complete hub and spoke model), the problem is algorithmically easy. But a) flight distance is much higher, and b) you run the risk of a single weather disaster taking out your entire network, and c) lots of other problems. My point was to suggest that its useful to understand what's going on in terms of algorithmic complexity. Southwest, because of decisions that they made I should add, is facing an extremely difficult algorithmic problem, and some of the issues of what's going on can be understood by thinking out those problems. I.E. your algorithms class actually matters

akira2501 4y ago

Senior pilots expect to have more choice in their routes and schedules. Junior pilots expect to have no choice.