Hacker News Reader

Comment by flerchin | Hacker News Reader

Crew scheduling is complex. At the large airline I used to work for (not AA), they ran network solvers that took months to optimally resolve. Intermediate solutions were available, but the constraints of union contracts, labor laws, the location of people, and the changing schedule of flights meant that optimally solving for minimum labor costs, and impact to our crews' lives, was not trivial.

View on HN

I too have worked on airline crew scheduling. The merging of union contracts, federal regulations, company policies and, like you said, the changing flight schedule, created insane complexity.

The fact that the whole system at all airlines is essentially auction-based with seniority being the currency of the realm is pretty interesting. The low-rank crew seeing time off available those days had to be pretty shocking.

No kidding - I worked on a project for a large airline optimizing reserve levels for flight crews and it was pretty fascinating work. The complexity explodes once you scratch past the surface.

I've always wondered how the algorithms behind scheduling different events work given certain constraints. Are there resources (papers, articles, etc.) where I can learn about these algorithms, or even just a search query I can try that will point me in the right direction?

EDIT: spelling

clrs has plenty on it.

thanks, but I was looking for the specific name of the algorithm. I don't even know what to call it, a dependency graph solving algorithm or something?

A basic start would be looking at network flow problems. While they don't extend to the complexity of real world airline scheduling, you can construct a simplified airline scheduling problem with it. Additionally, one of the methods to solve these problems, linear programming, does extend to integer linear programming which can be used to solve the more complicated cases (in non-deterministic polynomial time).

I imagine you could encode the problem as a CSP with each of the legal/contractual factors as a constraint. Despite NP-hardness of CSPs in general, CSP solvers are pretty efficient if the constraints are sparse enough and not chosen adversarially.

a constraint solver, they're used heavily in CAD as well

I wonder how far away we are from self flying planes? Whilst there is the added problem of the third dimension over cars, perhaps this domain suffers less from the problem of lots of disorderly users in the same space?

It'll never happen. Modern planes are mostly self-flying, but you must have a human expert able to intervene if something goes wrong.

https://99percentinvisible.org/episode/children-of-the-magen...

Actually, let me correct that. We already have self-flying planes. They're called drones! We don't use them to transport anything as valuable as humans though.

Wait, how does the article support your statement? The article concludes with this bit from it’s quoted “expert”:

“Langewiesche thinks that we are ultimately heading toward pilotless planes. And by the time that happens, the automation will be so good and so reliable that humans, with all of their fallibility, will really just be in the way.”

Also, I don’t have a hard number for this, but most commercial aviation crashes (like the Air France one, Colgan Air in 2009, AirAsia a few years ago) are due to pilot error or factors that don’t have to do with automation vs pilots (Malaysian Air that was shot down over Ukraine, TWA 800, and others)

You can't just look at the crashes without giving offsetting credit for crashes avoided by human intervention. (USAir 1549 or United 232 as possible examples.)

True, those are good counter examples, thanks for sharing.

Here’s a reference from the BBC (sourcing a Boeing report from 2003) that states that approximately 80% of commercial aviation accidents were caused by pilot error (when the study was performed in 2003).

http://www.bbc.com/travel/story/20130521-how-human-error-can...

Just because they are Pilot error doesn't necessarily mean that the machine would have done better.

Very true

Blaming the dead pilots is easy as my Uncle (ex Merchant Marine) said about the Concordia sinking - they always crucify the captain.

You mean that guy who brought the ship dangerously close to an island (300m vs the planned 8km), because he watned to impress his girlfriend and then "accidentaly" fell into a lifeboat and left the sinking ship?

Not the best example IMHO.

True My Uncle had met him when the concordias captain went to Warsash (one of the Uk's training colleges) and wasn't impressed.

I think his point was they always crucify the captain even if its not their direct fault

Langewiesche thinks that, and I think he's wrong. The only craft we've ever managed to automate well enough to eliminate the human operator is the elevator.

In a generation, we'll probably add fighter pilots to that list. Commercial pilots? Nah. Not with the current paradigm of passenger planes.

Interesting, so the purpose of linking the article wasn’t to support your point?

Regarding the elevator comment - what about light rail at airports? Terminal to terminal “air trains” don’t have human drivers.

Also, how would you counter the statistic that 80% of commercial aviation crashes are caused by pilot error (see my above comment for source)? This would seem to suggest that continuing to improve automation with the goal of removing the human altogether would reduce the number of crashes, assuming the automation wouldn’t make the same mistakes as the human.

The story I linked had a lot of information about automation. I've taken the information from that story and combined it with my interactions with computer programmers, business executives, and pilots to synthesize the opinion that fully automated commercial airplanes aren't viable.

"Air trains" and some subway lines/systems are automated. Interesting that the only systems that have successfully been automated are literally on rails, and are generally enclosed.

It's a fair assumption that the automation won't make the same mistakes as a human, but it's quite a stretch to assume it won't make it's own special flavor of mistake.

Also, you've pointed out the crashes that humans caused, but not the crashes that were avoided by humans. This is getting far from my field of expertise, but you've got to be careful to avoid selection bias.

Very good points, thank you for taking the time to respond so clearly and in detail!

Not only light rail at airports - there are whole subway lines and systems that are fully automated (e.g. Copenhagen)

> you must have a human expert able to intervene if something goes wrong

Similar things were said about cars. Humans make mistakes at certain rates, in predictable as well as novel situations. When the autopilot performs, on average, better, humans will become a safety liability.

The autopilot has to outperform trained experts with hundreds of flight hours and an exceptionally high code of personal conduct.

Self driving cars have to outperform the average person who drives like a 100-year-old blind dog who’s texting while driving and drinking a smoothie. Also, their failure mode is easier and much less expensive.

It’s a difficult problem that we have not solved. But you said “must”. That’s a strict word to use for a problem that can be solved within a decade or two.

As someone who isn't afraid of flying (except in the case where the pilot has to suddenly drop the airplane due to turbulence) I still wouldn't trust a pilotless airplane until it's safer then with a pilot, which will be very difficult to prove. I feel also that I'm not alone and many people who fly would be extremely wary of a pilotless system. On the other hand, I would be much more likely to trust a self driving car. The main reason is that, if a self driving car malfunctions, the risk of my death is present but not absolutely guaranteed and with all of the safety features in a car it's likely I would still be alive after a crash, even at high speeds. A plane that has an autopilot malfunction, with no human present, without changes to the safety during a crash, would be essentially guaranteed to kill everyone on board. Until a plane can crash from the sky without killing all passengers in most scenarios, I wouldn't fly in a pilotless airplane.

Agreed, my primary gripe with the original comment was that the OP used the word “must.”

Airline passengers don't generally care about it being safer on average. If the autopilot can't make a landing in a 30 kt crosswind all of the time people won't fly on that plane. People have much higher standards for acceptable safety with aircraft than cars. Also, autopilot isn't really designed to replace the pilot. Its designed to reduce workloads during departure and approach and make cruise less shitty. Autopilots are entirely unable to handle even simple failures and even in many cases do simple things like climb at a specific airspeed or do wind drift corrections. Car are just much simpler, have fewer consequences, and have lower expectations of safety. Until we get more versatile autopilots, aircrew acceptance, and/or lower expectations of safety, I don't see self-flying airliners anytime soon.

Similar things were said about cars.

What an excellent counterexample, with all of the driverless cars that actually exist in real life.

The main reason we don't have them is that people don't want them. Autopilots date back to 1912 (yep, you read that right) and the first flight off an aircraft controlled 100% by autopilot happened in 1947. US Navy carriers and aircraft have been capable of automatic landings since the 1960s. IIRC today most larger airliners have autopilots capable of handling the entire flight after take off (they don't bother to include auto takeoff, because no one uses it).

Aircraft are downright trivial to automate compared to cars, at least until something goes wrong. The vast majority of the time a car can drop into a fairly reasonable failsafe mode of "steer straight and apply brakes." Aircraft, not so much.

> people don't want them

The one thing American travellers are consistent on is choosing the cheapest flight. Autopiloted flights, at a discount, would sell tickets. That said, I don’t think we there yet technologically.

Pilots just aren’t that expensive, to be honest. Assuming your flight crew is costing $400 per hour combined (on the high side according to some googling) and you have a 6 hour flight with 300 passengers, eliminating the crew only drops prices by $8 per ticket.

The most common commercial plane in America is the Boeing 737 [1]. It seats 100 to 200 passengers [2].

Delta officers and first captains make $320 and $200 thousand, respectively, and fly about 1,000 hours a year [3]. So 520 per hour, between the two of them.

A main-cabin ticket to New York from San Jose, California about 2 months out costs $146. (Its SJC to MSP leg happens to be on a 737.) Flight time is about 6 hours.

Assuming 175 (one-class 737-800 configuration) paying passengers we have about $25,000 in revenues. The captain and first officer’s pay is roughly 12% of that. That’s a lot.

[1] http://www.fi-aeroweb.com/US-Commercial-Aircraft-Fleet.html

[2] https://en.m.wikipedia.org/wiki/Boeing_737

[3] http://onemileatatime.boardingarea.com/2016/12/01/delta-pilo...

Even that 12% figure only works out to about $17 per ticket. If you offered passengers that discount (clearly communicating that it meant flying totally on autopilot), I'd be absolutely shocked if even 10-20% took the offer. Of course realistically, I feel sure that automated planes would be required to fly with a human backup pilot, so the potential savings are even less.

TBH I think it will take the success of self driving cars, trucks, etc. before the public becomes comfortable with the idea of self flying planes. Ironic since cars are overall the more challenging application, but I guess that's human nature.

Isn't cargo an important revenue stream?

People overestimate what an Autopilot does. Autopilots don't make decisions, they don't look at weather charts, they don't look at other traffic, they don't talk on the radio with towers. They're basic computers that are programmed by the pilots to take off/land/change flightlevel/change heading. You still need the pilots there to decide what to do and program the autopilot with tasks to perform.

When someone can say with a straight face that the passengers of US Airlines flight 1549 and Qantas flight QF32 would be alive without the heroes they had up front.

QF32 is tricky, but I don't see why a computer couldn't have easily landed US Air 1549. It would have known exactly whether it was capable or not of returning to the airport and immediately deciding on an alternative landing location if not. Handling an engine failure during takeoff and landing on water are both textbook training scenarios for all airline pilots, they would surely be handled by any self flying plane designed to operate without a human pilot.

in the NTSB investigation, it appeared that there was literally only about 30 seconds at the outset to evaluate returning, and even then, with immediate returns, pilots were only able to return 7 out of 13 tests. Textbook and theory doesn't always supercede knowledge of the area and novel thinking.

I assume for that to happen, we'd have to have mostly self-automated air control operations. Besides the technological improvements (which might be relatively minor), there would likely be the "human" delay, e.g. you can't just fire the vast majority (assuming towers will always have some human help) of air control operators within a few years or even a decade.

Reagan did. https://www.history.com/this-day-in-history/reagan-fires-113...

Reply on news.ycombinator.com