Hacker News Reader

Comment by bodhiandphysics | Hacker News Reader

One thing to note is that airline crew scheduling is np-hard (trivially you can reduce Hamiltonian cycle to it). Ak interesting semi-empiricle fact about np-complete problems. Take a decision problem to determine if there is a schedule with k crews. Now there is some k’ that is the minimum such k. For many Np problem problems the difficulty of the decision problem is related to the ratio of k to k’. (Not all decision problems are like this… those that are are on the complexity class APX. As a quick rule of thumb however this works) In terms of airline scheduling this means that if you more crews than you strictly need, your algorithm is probably going to successfully schedule them. When the number of crews drops below some critical value… all hell breaks loose. Thinking about this in complexity terms is useful I think. He issue isn’t just bad software… with a small enough number of crews, all software is bad, unless P = NP

View on HN

I wonder if the difficulty at this point is algorithmic, or if they even have the data to make "reasonable" decisions, never mind optimizing them.

Like what do they do with the bags that are sitting on the plane for cancelled flights? Store them where they are? Figure out their origin and start queuing them to be sent there? Try to get information from the passenger about where to send it?

And then with planes and crews, do they even have "potential" flights where they would be able to reliably seat a worthwhile number of passengers?

I'm sure they know exactly where every plane and every flight crew is at every moment. My point about algorithmic complexity is that even with perfect knowledge, fixing this is a computationally difficult problem. The idea was to show how the properties of algorithms that perform combinatorial optimization actually matter!

> I'm sure they know exactly where every plane and every flight crew is at every moment.

The story being circulated by Sw employees is that this is the failure. The system needs to be manually updated when flights are cancelled or changed, and in this situation with a cascading failure they have completely failed to keep that data accurate. SW employees have said they have spent 24 hours on hold trying to inform the company where they are.

I don’t think this has anything to do with algorithmic complexity.

The statements from employees indicate that SWA does _not_ know where flight crews are at every moment. When a flight is cancelled the downstream information is not updated accordingly. Crew have to call a phone line and speak to another human to update their information and assignments. With the large scale cancellations due to weather, that system was overloaded and fully collapsed. SWA had no choice but to cancel the majority of their flights while they sort out where the crews are at and how to schedule them next. The debacle is a direct result of lack of investment in modern software systems.

heh i wonder if they've asked everyone to use their phones to share their location with their immediate supervisor. Then someone setup a spreadsheet in sharepoint and the supervisors are going at it.

> Like what do they do with the bags that are sitting on the plane for cancelled flights?

Eventually you send them back to the passenger's home address. I've had lost luggage before that turned up on my front porch a week later, some courier service had dropped it off.

yeah it sounds like recovering from this requires standing up a brand new organization in real time. I hope someone is watching the trouble ticket system, imagine that going down...

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.

"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

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.

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!

> 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

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)

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

While this would be an excellent justification for not being able to schedule everything, it's not much of a justification for not being able to schedule 2/3 of your flights on a day with clear weather...

I don't get to exercise my dusty algorithms knowledge nearly enough to follow this nearly as well as I'd like. Are we talking about the bin packing problem and approximation ratios? So, is the intuition here that when the ratio of bins to objects goes up, the worst-case performance for the algorithm goes down into the toilet?

Maybe there are many crews who are not able to fly because they hit the FAA hour limit? If so, then this cascade of failure was predictable.

Predictable, assuming they knew which crews in which cities were close to their limit, which it seems like they don't now that the system is down, which is most of the problem.

Reply on news.ycombinator.com